离散数学图的基本概论

计算机科学广泛应用于运筹学，信息 论，控制论，网络理论，化学生物学，物理 学。原因在于这些学科的许多实际问题和理

论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际

中的应用。

8.1

无向图及有向图

一、基本图类及相关概念1. 无向图

称{{a,b} | a A b B} 无序积：设A,B为二集合，为A与B的无序积，记作：A&B。 习惯上，无序对{a,b}改记成(a, b) 有序组(a,b)均用< a,b >

无向图：无向图G是一个二元组< V,E >,其中

(1) V是一个非空集 ––– 顶点集V(G),每个元素为顶点或结点；

(2) E是无序积V & V的可重子集(元素可重复出

现),E ––– 边集E(G),E中元素称为无向边。

实际中，图是画出来的，画法：用小圆圈 表示V中的每一个元素，如果(a,b) E,则在顶

点a与b之间连线段。如：a e1 b e3 c e4 e1 e2 e6 e5 d e1 v2 v1

e2 v5e3 v3 e4 e5

e6

v4

2. 有向图有向图：有向图D是一个二元组< V,E >,其中 (1) V是非空集 ––– 顶点集 V(D)

(2) E是笛卡尔积V V的可重子集，其元素为有向边 实际中，画法同无向图，只是要根据E中 元素的次序，由第一元素用方向线段指向第 二元素。

3. 相关概念 有限图：V,E均为有穷集合

零 图：E 平凡图：E 且 |V| = 1 (n, m)图：|V| = n 且 |E| = m 顶与边关联：如果ek = (vi,vj) E,称ek与vi关联， 或ek与vj关联。

顶与顶相邻：如果ek = (vi,vj) E,称vi与vj相邻；

若ek为有向边，则称vi邻接到vj,vj邻接于vi 。 边与边相邻：如果ek和ei至少有一个公共顶点关联， 则称ek与ei相邻。 环： ek = < vi,vj > 中，若 vi = vj,则ek称为环。

孤立点：无边关联的顶点。

平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数； 有向图中，关联一对顶点的无向边

多于一条，且始、终点相同。 多重图：包含平行边的图。简单图：既不包含平行边又不包含环的图。

二、度

度：(1) 在无向图G = < V, E >中，与顶点v(v V)关联的边的数目(每个环计算两次),记 作：d(v)。

(2) 在有向图D = < V,E >中，以顶点v(v V)作为始点的边的数目，称为该顶点的出度，

记作： d+(v);以顶点v作为终点的边的数目，称为该顶点的入度，记作：d–(v)。

出度与入度之和，称为顶点v的度： d(v) = d+(v)+ d–(v)度是图的性质的重要判断依据。

最大度： (G) = max {d(v) | v V}最小度： (G) = min {d(v) | v V} 度与边数的关系：在任何图中，顶点度数的(握手定理)

总和等于边数之和的两倍。

即 d (v) 2 | E |v V

握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。

出度与入度的关系：在有向图中，各顶

点的 出度之和等于各顶点的入度之和。d (vi ) d (vi ) m i 1 i 1 n n

度数序列：设V = {v1,v2,…,vn}为图G的顶点集，

称(d(v1), d(v2),…, d(vn))为G的度数序列。 度数序列之和必为偶数(?)。

例8.1 (3,3,2,3),(5,2,3,1,4)能成为图的度数 序列吗？为什么？ 解：由于这两个序列中，奇数个数均为奇 数，由握手定理知，它们不能成为图 的度数序列。

例8.2 已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2,问G

中至少有多少个顶点？为什么？解：图中边数 m=10,由握手定理知，

G中各顶点度数之和为20,4个3度顶点占去12度，还剩8度， 若其余全是2度顶点, 则需要4个顶点 来占用8度，所以G至少有8个顶点。

三、正则图与完全图正则图：各顶点的度都相同的图为正则图； 各顶点的度均为k的图为k次正则图。 完全图：

(1) 设G = < V,E >是n阶的无向简单图，如果G中任何一个顶点都与其余n–1个顶点相邻，

则G为无向完全图，记作：Kn。