19 第十四章 图的基本概念

长沙民政职业技术学院教案一、问题引入引例1 有3个人A、B和C，3件工作D、E和F，假设A只能做工作D，B能做工作E和F，C能做工作D和E。

则这种情形可用图表示，在人和这个人能够做的工作之间画线，如图4-1所示。

图4-1 工作关系图图4-2 航行线路图引例2 考虑一张航线地图，图中用点表示城市，当两个城市间有直达航班时，就用一条线将相应的点连接起来。

这种航线地图的一部分如图4-2所示。

当然，这两个图也可以表示其它的含义。

例如，例1的图中，点A、B、C、D、E和F 可以分别表示6家企业，如果某两家企业有业务往来，则其对应的点之间用线连接起来，这时的图又反映了这6家企业间的业务关系。

事实上，生活中的许多问题如果用图来描述可能更加简洁清晰，这种图是由一些点以及这个点中的某些点对的连线构成。

二、新课讲授定义1 图G是一个包含有限个点（称之为顶点）和连接各对顶点的线段（称之为边）的图形，记作(V,E)G ，其中V,E分别为图G的顶点集和边集。

如果图G中的边有方向，则称图G为有向图，否则称图G为无向图。

在图的图形表示中，每个顶点用一个小圆点表示，每条边用顶点之间的连线段表示。

图4-1便是一个图的例子，它的顶点是A、B、C、D、E、F，连接它们的5条线段就是边。

一般情况下，我们用大写字母A、B、C等来标记这些顶点，如果只有一条边连接两个顶点，我们就用这两个顶点的字母连接起来表示这条边。

如果能确定一个对象集合里面的关系，可以按照下面的方式建立一个图论模型。

（1）用顶点代表每一个对象；（2）对于每一对有关系的对象，将相应的顶点用边连接起来。

案例1 (比赛图模型)甲、乙、丙、丁、戊5支球队进行比赛，各队之间的比赛胜负情况如表4-1所示，试用图表示他们的关系。

表4-1 比赛情况表解一个顶点表示一支球队，球队之间的胜负关系用有向边表示，如，甲击败了队，则顶点对(甲,乙)之间有一条从甲到乙的有向边。

图4-4表示了5支球队比赛情况的有向图模型。

图论是近数十年来得到蓬勃发展的一个数学分支，它的 理论与方法在许多领域中得到广泛的应用并取得了丰硕的 成果成为运筹学一个重要分支。
线性规划、整数规划、运输问题等等，有时也可以用图 论的方法来构造模型并求解，而且由于图的结构的直观性， 更有助于我们分析问题和描述问题，何况有些研究对象， 如交通网，它本身就是一个大网络，用图论的方法研究更 方便。
数学描述： （1）G={V,E}，V={v1,v2, ···vn},E={e1,e2, ···en}
（2）G={(eij,(vi,vj))|i,j=1···n}
根据边有没有方向，将图分为无向图和有向图，下面分别讲解：
1.1.1 无向图
一、无向图定义
v1 v2
v5 v3
1．无向图
v4
设V是一个有n个顶点的非空集合，V={v1 ,v2 ,…,vn },E是
v1
v5
v3 v2
v4
v1
v5
1.1.1 无向图
v3
v2
二、无向图术语
v4
平简行单边图（：多图重中边无）平：行两边边有一样的端点，如e15和e51 完备图：图中任意两个端点之间有且仅有一条边 链：两个端点之间的连接路径 一个链的起始端点不为同一个称为开链，否则为闭链（圈）
简单链：一个链中无重复的边。
图的可达性（有向图）：若图G中从顶点u 到v之 间存在单向路径，则称u可达v。
强连通图：若图G内任两点之间相互可达，则称 图G为强连通图。
v1 v2
v1
v5
v4
v6
e3
e1 e4
e6
v3
v3
v2 v5
e5
e7 v4
e8
1.1.3 其它术语

为弧的始结点(Initial Vertex), 称为弧的终结点(Terminal Vertex), 统称为的端点
(Endpoint)。
5
无向图 & 有向图
• 【定义】在图G中,
①如果每条边都是有向边, 该图G称为有向图(Directed Graph)
②若每条边都是无向边, 该图G称为无向图(Undirected Graph)
(Edge)；
③称为关联函数, 是从E到V中的有序对或无序对的映射。
•
若边∈E与无序结点对(, )相联系, 则()=(, ), 这时边称为无向边, 有时简称为边；
•
若边∈E与有序结点对<, >相联系, 则()=<, >, 此时边称为有向边或弧(Arc), 称
③如果有些边是有向边, 另一些边是无向边, 图G称为混合图(Mixed Graph)
• 【定义】一个有向图中, 如果将每条有向边都改为无向边, 便得到该有向图的
底图(Underlying Undirected Graph)或基础图。
6
图的表示
• 一个图可以用几何图形表示，方法与二元关系的表示法相同。
多重图(Multiple Graph): 含有平行边的图；
•Leabharlann 线 图: 非多重图称为线图；•
简单图(Simple Graph): 不含平行边和自回环的图。
简单图是一
个非常重要
的概念
13
图的分类(续)
• 3.按G的边有序, 无序分为有向图, 无向图和混合图。
• 有向图(Directed Graph): 每条边都是有向边的图称为有向图
图的基本概念
图论的前世今生
• 1736年，欧拉（L.Eular）发表了第一篇关于图论的论文，解决了哥尼斯

无向图 <V,E> (2) 若|V(G)| 、|E(G)|均为有限数，则称G为有限图。
一个 为A与B的无序积，记作A&B.
是一个有序的二元组
，记作G， 其中
1 , vi可达vj
第十四章 图的(基1本)概念V≠φ称为顶点集，其元素称为顶点或结点。
第十四章 图的基本概念
第十四章 图的(基2本)概念E称为边集，它是无序积V&V的多重子集，其元素称为
所有边互不相同），则称此回路为基本回路或者初级 则V1∪ V2 =V, V1∩V2= φ,由握手定理知
若回路中的所有边e1，e2，…，ek互不相同，则称此回路为简单回路或一条闭迹；
回路、圈。 26 设有向图D=<V,E>中无环, V={v1,v2,…,vn}, E={e1,e2,…,em}, 令aij(1)为顶点vi与邻接到顶点vj边的条数，称(aij(1))n×n为D的邻接矩
第十四章 图的基本概念
例14.1 画出下列 图形。
v1。
。v2
(1) G=<V,E>,其中
V={v1,v2,v3,v4,v5},
v3
。
(1)
E={(v1,v1), (v1,v2), (v2,v3),
v4 。
。v5
(v2,v3), (v1,v5),
(v2,v5), (v4,v5)}。
(2) D=<V,E>,其中
顶点的度数均小于3,问G中至少有多少个顶点?
第十四章 图的基本概念
定义14.5完全图
1. 设G＝<V,E>为一个具有n个结点的无向简单图，如 果G中任一个结点都与其余n-1个结点相邻接，则称 G为无向完全图，简称G为完全图，记为Kn。