第 14章 图的基本概念离 散 数 学哈尔滨理工大学本科生课程计算机系本章内容
14.1 图
14.2 通路与回路
14.3 图的连通性
14.4 图的矩阵表示
14.5 图的运算基本要求作业
14.1 图的基本概念
图的定义
图的一些概念和规定
简单图和多重图
顶点的度数与握手定理
图的同构
完全图与正则图
子图与补图无序积与多重集合
设 A,B为任意的两个集合，称 {{a,b}|a∈A∧b∈B} 为 A与 B
的 无序积,记作 A&B。
可将无序积中的无序对 {a,b}记为 (a,b),并且允许 a＝ b。
无论 a,b是否相等，均有 (a,b)＝ (b,a),因而 A&B＝ B&A。
元素可以重复出现的集合称为 多重集合 或者 多重集,某元素重复出现的次数称为该元素的 重复度 。
例如 在多重集合 {a,a,b,b,b,c,d}中，
a,b,c,d的重复度分别为 2,3,1,1。
定义 14.1 一个 无向图 是一个有序的二元组 <V,E>,记作 G,其中
（ 1） V≠?称为 顶点集,其元素称为 顶点 或 结点 。
（ 2） E称为 边集,它是 无序积 V&V的多重子集，其元素称为 无向边,简称 边 。
定义 14.2 一个 有向图 是一个有序的二元组 <V,E>,记作 D,其中
（ 1） V≠?称为 顶点集,其元素称为 顶点 或 结点 。
（ 2） E为 边集,它是 笛卡儿积 V× V的多重子集，其元素称为 有向边,简称 边 。
无向图和有向图说明? 可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。
例 14.1
例 14.1 (1) 给定无向图 G＝ <V,E>,其中 V＝ {v1,v2,v3,v4,v5}，
E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)},
(2) 给定有向图 D=<V,E>,其中 V＝ {a,b,c,d}，
E＝ {<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。
画出 G与 D的图形。
图的一些概念和规定
G表示无向图，但有时用 G泛指图 (无向的或有向的 )。
D只能表示有向图。
V(G),E(G)分别表示 G的 顶点集 和 边集 。
若 |V(G)|＝ n,则称 G为 n阶图 。
若 |V(G)|与 |E(G)|均为有限数，则称 G为 有限图 。
若边集 E(G)＝?,则称 G为 零图,此时，又若 G为 n阶图，则称 G
为 n阶零图,记作 Nn,特别地，称 N1为 平凡图 。
在图的定义中规定顶点集 V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定 顶点集为空集的图 为空图,并将空图记为?。
标定图与非标定图、基图
将图的集合定义转化成图形表示之后，常用 ek表示 无向边
(vi,vj)（ 或 有向边 <vi,vj>）,并称 顶点或边用字母标定的图 为 标定图,否则称为 非标定图 。
将有向图各 有向边均改成无向边后的无向图 称为原来图的 基图 。
易知标定图与非标定图是可以相互转化的，任何无向图 G
的各边均加上箭头就可以得到以 G为基图的有向图。
关联与关联次数、环、孤立点
设 G＝ <V,E>为无向图,ek＝ (vi,vj)∈E,
称 vi,vj为 ek的端点,ek与 vi或 ek与 vj是彼此相 关联 的。
若 vi≠ vj,则称 ek与 vi或 ek与 vj的 关联次数为 1。
若 vi＝ vj,则称 ek与 vi的 关联次数为 2，并称 ek为 环 。
任意的 vl∈V,若 vl≠ vi且 vl≠ vj,则称 ek与 vl的 关联次数为 0。
设 D＝ <V,E>为有向图,ek＝ <vi,vj>∈E,
称 vi,vj为 ek的 端点。
若 vi＝ vj,则称 ek为 D中的 环 。
无论在无向图中还是在有向图中，无边关联的顶点均称为 孤立点 。
相邻与邻接
设无向图 G＝ <V,E>,vi,vj∈V,ek,el∈E 。
若?et∈E,使得 et＝ (vi,vj),则称 vi与 vj是 相邻的 。
若 ek与 el至少有一个公共端点,则称 ek与 el是 相邻的 。
设有向图 D＝ <V,E>,vi,vj∈V,ek,el∈E 。
若?et∈E,使得 et＝ <vi,vj>,则称 vi为 et的 始点,vj为 et的 终点,并称 vi邻接到 vj,vj邻接于 vi。
若 ek的终点为 el的始点，则称 ek与 el相邻 。
邻域
设无向图 G＝ <V,E>,?v∈ V，
称 {u|u∈ V∧( u,v)∈ E∧ u≠ v}为 v的 邻域,记做 NG(v)。
称 NG(v)∪{ v}为 v的 闭邻域,记做 NG(v)。
称 {e|e∈ E∧ e与 v相关联 }为 v的 关联集,记做 IG(v)。
设有向图 D＝ <V,E>,?v∈ V，
称 {u|u∈V∧ <v,u>∈E∧ u≠ v}为 v的 后继元集,记做 Г +D(v)。
称 {u|u∈V∧ <u,v>∈E∧ u≠ v}为 v的 先驱元集,记做 Г -D(v)。
称 Г +D(v)∪Г -D(v)为 v的 邻域,记做 ND(v)。
称 ND(v)∪{ v}为 v的 闭邻域,记做 ND(v)。
举例
NG(v1) ＝
Г +D(d ) ＝
{v2,v5}
NG(v1) ＝ {v1,v2,v5}
IG(v1) ＝ {e1,e2,e3}
{c}
Г -D(d ) ＝ {a,c}
ND(d ) ＝ {a,c}
ND(d ) ＝ {a,c,d}
简单图与多重图定义 14.3 在无向图中，关联一对顶点的无向边如果 多于 1条,
则称这些边为 平行边,平行边的条数称为 重数 。
在有向图中，关联一对顶点的有向边如果 多于 1条,并且这些边的 始点和终点相同 (也就是它们的方向相同 )，则称这些边为 平行边 。
含平行边的图称为 多重图 。
既不含平行边也不含环的图 称为 简单图 。
例如,在图 14.1中，
(a)中 e5与 e6是平行边，
(b)中 e2与 e3是平行边，但 e6与 e7不是平行边。
(a)和 (b)两个图都不是简单图。
顶点的度数定义 14.4 设 G＝ <V,E>为一无向图,?v∈V,称 v作为边的端点次数之和为 v的度数,简称为 度,记做 dG(v)。
在不发生混淆时，简记为 d(v)。
设 D＝ <V,E>为有向图,?v∈V,
称 v作为边的始点次数之和为 v的出度,记做 d+D(v),简记作
d+(v)。
称 v作为边的终点次数之和为 v的入度,记做 d -D(v),简记作
d-(v)。
称 d+(v)+d-(v)为 v的 度数,记做 d(v)。
图的度数的相关概念
在无向图 G中，
最大度 △ (G)＝ max{d(v)|v∈V(G)}
最小度 δ(G) ＝ min{d(v)|v∈V(G)}
在有向图 D中，
最大出度 △ +(D)＝ max{d+(v)|v∈V(D)}
最小出度 δ +(D)＝ min{d+(v)|v∈V(D)}
最大入度 △ -(D)＝ max{d-(v)|v∈V(D)}
最小入度 δ -(D)＝ min{d-(v)|v∈V(D)}
称度数为 1的顶点为 悬挂顶点,与它关联的边称为 悬挂边 。
度为偶数 (奇数 )的顶点称为 偶度 (奇度 )顶点 。
图的度数举例
d(v1)＝ 4(注意，环提供 2度 )，
△＝ 4,δ ＝ 1，
v4是悬挂顶点,e7是悬挂边。
d+(a)＝ 4,d-(a)＝ 1
(环 e1提供出度 1，提供入度 1)，
d(a)＝ 4+1＝ 5。△＝ 5,δ ＝ 3，
△ +＝ 4 (在 a点达到 )
δ +＝ 0(在 b点达到 )
△ -＝ 3(在 b点达到 )
δ -＝ 1(在 a和 c点达到 )
握手定理定理 14.1 设 G＝ <V,E>为任意无向图,V＝ {v1,v2,…,vn}，
|E|＝ m,则
n
1
2)(
i
i mvd
说明 任何无向图中，各顶点度数之和等于边数的两倍。
证明 G中每条边 (包括环 )均有两个端点，
所以在计算 G中各顶点度数之和时，
每条边均提供 2度，当然,m条边，共提供 2m度。
定理 14.2 设 D＝ <V,E>为任意有向图,V＝ {v1,v2,…,vn}，
|E|＝ m,则
n nn
1 11
)()(,2)(
i i
ii
i
i mvdvdmvd 且握手定理的推论推论 任何图 (无向的或有向的 )中，奇度顶点的个数是偶数。
证明 设 G＝ <V,E>为任意一图，令
V1＝ {v|v∈V∧ d(v)为奇数 }
V2＝ {v|v∈V∧ d(v)为偶数 }
则 V1∪V 2＝ V,V1∩V 2＝?,由握手定理可知
Vv
vdm )(2
21
)()(
VvVv
vdvd
由于 2m和
2
)(
Vv
vd
，所以
1
)(
Vv
vd
为偶数,
但因 V1中顶点度数为奇数,所以 |V1|必为偶数。
问题研究问题,在一个部门的 25个人中间，由于意见不同，是否可能每个人恰好与其他 5个人意见一致？
解答,不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。
说明：
(1)很多离散问题可以用图模型求解。
(2)为了建立一个图模型，需要决定顶点和边分别代表什么。
(3)在一个图模型中，边经常代表两个顶点之间的关系。
度数列设 G＝ <V,E>为一个 n阶无向图,V＝ {v1,v2,…,vn},称 d(v1)，
d(v2),…,d(vn)为 G的 度数列 。
对于顶点标定的无向图，它的度数列是唯一的。
反之，对于给定的非负整数列 d＝ {d1,d2,…,dn},若存在 V＝
{v1,v2,…,vn}为顶点集的 n阶无向图 G,使得 d(vi)＝ di,则称
d是 可图化的 。
特别地，若所得图是简单图，则称 d是 可简单图化的 。
类似地，设 D＝ <V,E>为一个 n阶有向图,V＝ {v1,v2,…,vn},称
d(v1),d(v2),…,d(vn)为 D的 度数列,另外称 d+(v1)，
d+(v2),…,d+(vn)与 d-(v1),d-(v2),…,d-(vn)分别为 D的出度列 和 入度列 。
度数列举例按顶点的标定顺序，度数列为
4,4,2,1,3。
按字母顺序，度数列，出度列，入度列分别为
5,3,3,3
4,0,2,1
1,3,1,2
可图化的充要条件定理 14.3 设非负整数列 d＝ (d1,d2,…,dn),则 d是可图化的当且仅当
n
1
)2(m o d0
i
id
证明 必要性。 由握手定理显然得证。
充分性。 由已知条件可知,d中有偶数个奇数度点。
奇数度点两两之间连一边，剩余度用环来实现。
5 3
3 1
定理 14.3的证明由握手定理可知必然性显然。
下面证明充分性。
由已知条件可知,d中有 2k(0≤k≤[n/2]) 个奇数，
不妨设它们为 d1,d2,…,dk,dk+1,dk+2,…,d2k。
可用多种方法做出 n阶无向图 G＝ <V,E>,V＝ {v1,v2,… vn}。
比如边集如下产生：在顶点 vr与 vr+k之间连边,r＝ 1,2,…,k。
若 di为偶数，令 d?i＝ di,若 di为奇数，令 d?i＝ di-1，
得 d?＝ (d?1,d?2,…,d?n),则 d?i均为偶数。
再在 vi处做出 d?i/2条环,i＝ 1,…,n，
将所得各边集合在一起组成 E,则 G的度数列为 d。
其实,di为偶数时,d(vi)＝ 2· d?i/2＝ 2· di/2＝ di，
当 di为奇数时,d(vi)＝ 1+2· d?i/2＝ 1+d?i＝ 1+di-1＝ di，
这就证明了 d是可图化的。
可图化举例由定理 14.3立即可知，
(3,3,2,1),(3,2,2,1,1)等是不可图化的，
(3,3,2,2),(3,2,2,2,1)等是可图化的。
定理 14.4
定理 14.4 设 G为任意 n阶无向简单图，则△ (G)≤ n-1。
证明 因为 G既无平行边也无环，
所以 G中任何顶点 v至多与其余的 n-1个顶点均相邻，
于是 d(v)≤ n-1,由于 v的任意性，所以△ (G)≤ n-1。
例 14.2 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？
(1) (5,5,4,4,2,1)
不可图化。
(2) (5,4,3,2,2)
可图化，不可简单图化。若它可简单图化，
设所得图为 G,则 (G)＝ max{5,4,3,2,2}＝ 5，
这与定理 14.4矛盾。
例 14.2
(3) (3,3,3,1)
可图化，不可简单图化。假设该序列可以简单图化，
设 G＝ <V,E>以该序列为度数列。
不妨设 V＝ {v1,v2,v3,v4}
且 d(v1)＝ d(v2)＝ d(v3)＝ 3,d(v4)＝ 1，
由于 d(v4)＝ 1,因而 v4只能与 v1,v2,v3之一相邻，
于是 v1,v2,v3不可能都是 3度顶点，这是矛盾的，
因而 (3)中序列也不可简单图化。
(4) (d1,d2,… dn),d1>d2>… >dn≥1 且 为偶数。
n
1i
id
可图化，不可简单图化。
例 14.2
(5) (4,4,3,3,2,2)
可简单图化。下图中两个 6阶无向简单图都以 (5)中序列为度数列。
图的同构定义 14.5 设 G1＝ <V1,E1>,G2＝ <V2,E2>为两个无向图，
若存在双射函数 f,V1→V 2,对于 vi,vj∈V 1,(vi,vj)∈E 1
当且仅当 (f(vi),f(vj))∈E 2，
并且 (vi,vj)与 (f(vi),f(vj))的重数相同，
则称 G1与 G2是同构的,记做 G1≌ G2。
说明 (1) 类似地，可以定义两个有向图的同构。
(2) 图的同构关系看成全体图集合上的二元关系。
(3) 图的同构关系是等价关系。
(4) 在图同构的意义下，图的数学定义与图形表示是一一对应的。
图的同构举例彼得森 (Petersen)图完全图定义 14.6 设 G为 n阶无向简单图，若 G中 每个顶点均与其余的 n-1
个顶点相邻,则称 G为 n阶无向完全图,简称 n阶完全图,记做
Kn(n≥1) 。
设 D为 n阶有向简单图，若 D中每个顶点都邻接到其余的 n-1个顶点，又邻接于其余的 n-1个顶点，则称 D是 n阶有向完全图 。
设 D为 n阶有向简单图，若 D的基图为 n阶无向完全图 Kn,则称 D
是 n阶竞赛图 。
完全图举例
n阶无向完全图的边数为,n(n-1)/2
n阶有向完全图的边数为,n(n-1)
n阶竞赛图的边数为,n(n-1)/2
K5 3阶有向完全图 4阶竞赛图正则图定义 14.7 设 G为 n阶无向简单图，若 v∈V(G),均有 d(v)＝ k，
则称 G为 k-正则图 。
举例 n阶零图是 0-正则图
n阶无向完全图是 (n-1)-正则图彼得森图是 3-正则图说明 n阶 k-正则图中，边数 m＝ kn/2。
当 k为奇数时,n必为偶数。
子图定义 14.8 设 G＝ <V,E>,G?＝ <V?,E?>为两个图 (同为无向图或同为有向图 )，若 VV且 EE,则称 G?是 G的 子图,G为 G?
的 母图,记作 GG。
若 VV或 EE,则称 G?为 G的 真子图 。
若 V?＝ V,则称 G?为 G的 生成子图 。
设 G＝ <V,E>为一图,V1?V且 V1≠?,称以 V1为顶点集，以
G中 两个端点都在 V1中的边 组成边集 E1的图为 G的 V1导出的子图,记作 G[V1]。
设 E1?E且 E1≠?,称以 E1为边集，以 E1中边关联的顶点为顶点集 V1的图 为 G的 E1导出的子图,记作 G[E1]。
导出子图举例在上图中，设 G为 (1)中图所表示，
取 V1＝ {a,b,c},则 V1的导出子图 G[V1]为 (2)中图所示。
取 E1＝ {e1,e3},则 E1的导出子图 G[E1]为 (3)中图所示。
例 14.3
(1) 画出 4阶 3条边的所有非同构的无向简单图。
由握手定理可知，所画的无向简单图各顶点度数之和为 2× 3＝
6，最大度小于或等于 3。于是所求无向简单图的度数列应满足的条件是，将 6分成 4个非负整数，每个整数均大于或等于 0且小于或等于 3，并且 奇数的个数为偶数 。将这样的整数列排出来只有下面三种情况：
(1) 2,2,1,1
(2) 3,1,1,1
(3) 2,2,2,0
将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。
对于给定的正整数 n和 m(m≤ n(n-1)/2)，
构造出所有非同构的 n阶 m条边的所有非同构的无向 (有向 )简单图，这是目前还没有解决的难题。
例 14.3
(2) 画出 3阶 2条边的所有非同构的有向简单图。
由握手定理可知，所画有向简单图各顶点度数之和为 4，最大出度和最大入度均小于或等于 2。度数列及入度出度列为
1,2,1 入度列为 0,1,1 或 0,2,0 或 1,0,1出度列为 1,1,0 或 1,0,1 或 0,2,0
2,2,0 入度列为 1,1,0出度列为 1,1,0
定义 14.9
定义 14.9 设 G＝ <V,E>为 n阶无向简单图,以 V为顶点集,以所有 使 G成为完全图 Kn的添加边组成的集合 为边集的图，称为 G的 补图,记作 G。
若图 G≌ G,则称为 G是 自补图 。
(1)为自补图
(2)和 (3)互为补图定义 14.10
定义 14.10 设 G＝ <V,E>为无向图。
(1)设 e∈ E,用 G-e表示从 G中去掉边 e,称为 删除 e。
设 EE,用 G-E?表示从 G中删除 E?中所有的边，称为 删除 E?。
(2)设 v∈ V,用 G-v表示从 G中去掉 v及所关联的一切边，称为 删除顶点 v。
设 VV,用 G-V?表示从 G中删除 V?中所有顶点，称为 删除 V?。
(3)设边 e＝ (u,v)∈ E,用 G\e表示从 G中删除 e后，将 e的两个端点
u,v用一个新的顶点 w(或用 u或 v充当 w)代替，使 w关联除 e外 u,v
关联的所有边，称为 边 e的收缩 。
(4)设 u,v∈ V(u,v可能相邻，也可能不相邻 ),用 G∪( u,v)(或
G+(u,v))表示在 u,v之间加一条边 (u,v),称为 加新边 。
说明 在收缩边和加新边过程中可能产生环和平行边。
举例
G G－ e5 G－ {e1,e4}
G－ v5 G－ {v4,v5} G\e5
14.2 通路与回路定义 14.11 设 G为无向标定图,G中顶点与边的交替序列 Г＝
vi0ej1vi1ej2vi2… ejivil称为 vi0到 vil的 通路,其中,vir-1,vir为 ejr的 端点
,r ＝ 1,2,…,l,vi0,vil分别称为 Г的 始点 与 终点,Г中边的条数称为它的 长度 。
若 vi0＝ vil,则称通路为 回路 。
若 Г的 所有边各异,则称 Г为 简单通路,
又若 vi0＝ vil,则称 Г为 简单回路 。
若 Г的所有 顶点 (除 vi0与 vij可能相同外 )各异,所有 边也各异,则称 Г为 初级通路 或 路径,
又若 vi0＝ vil,则称 Г为 初级回路 或 圈 。
将长度为奇数的圈称为 奇圈,长度为偶数的圈称为 偶圈 。
关于通路与回路的说明
在初级通路与初级回路的定义中，仍将初级回路看成初级通路 (路径 )的特殊情况，只是在应用中初级通路 (路径 )都是始点与终点不相同的,长为 1的圈只能由环生成,长为 2
的圈只能由平行边生成,因而在 简单无向图中，圈的长度至少为 3。
若 Г 中有 边重复 出现，则称 Г 为 复杂通路,
又若 vi0＝ vil,则称 Г 为 复杂回路 。
在有向图中,通路、回路及分类的定义与无向图中非常相似，只是 要注意有向边方向的一致性 。
在以上的定义中，将回路定义成通路的特殊情况，即 回路也是通路,又 初级通路 (回路 )是简单通路 (回路 )，但反之不真。
通路和回路的简单表示法
(1)只用边的序列表示通路 (回路 )。定义 14.11中的 Г 可以表示成 ej1,ej2,…,ejl。
(2)在简单图中也可以只用顶点序列表示通路 (回路 )。定义中的 Г 也可以表示成 vi0,vi2,…,vil。
(3)为了写出非标定图中的通路 (回路 )，可以先将非标定图标成标定图，再写出通路与回路。
(4)在非简单标定图中，当只用顶点序列表示不出某些通路 (
回路 )时，可在顶点序列中加入一些边 (这些边是平行边或环 )，可称这种表示法为 混合表示法 。
定理 14.5
定理 14.5 在 n阶图 G中,若从顶点 vi到 vj（ vi≠ vj） 存在通路,则从
vi到 vj存在长度小于或等于 n-1的通路 。
证明设 Г＝ v0e1v1e2… elvl(v0＝ vi,vl＝ vj)为 G中一条长度为 l的通路，
若 l≤ n-1,则 Г满足要求，
否则必有 l+1>n,即 Г上的顶点数大于 G中的顶点数，
于是必存在 k,s,0≤ k<s≤ l,使得 vs＝ vk,
即在 Г上存在 vs到自身的回路 Csk,
在 Г上删除 Csk上的一切边及除 vs外的一切顶点，
得 Г?＝ v0e1v1e2… vkes+1 … elvl,Г?仍为 vi到 vj的通路，
且长度至少比 Г 减少 1。
若 Г?还不满足要求，则重复上述过程，由于 G是有限图，经过有限步后，必得到 vi到 vj长度小于或等于 n-1的通路。
定理 14.6
推论 在 n阶图 G中，若从顶点 vi到 vj（ vi≠ vj） 存在通路，则 vi到
vj一定存在长度小于或等于 n-1的初级通路（路径）。
定理 14.6 在一个 n阶图 G中，若存在 vi 到自身的回路，则一定存在 vi 到自身长度小于或等于 n的回路。
推论 在一个 n阶图 G中，若存在 vi 到自身的简单回路，则一定存在 vi 到自身长度小于或等于 n的初级回路。
例 14.4
例 14.4 无向完全图 Kn(n≥3) 中有几种非同构的圈？
解答 长度相同的圈都是同构的，
因而只有长度不同的圈才是非同构的，
易知 Kn(n≥3) 中含长度为 3,4,…,n的圈，
所以 Kn(n≥3) 中有 n-2种非同构的圈。
例 14.5
例 14.5 无向完全图 K3的顶点依次标定为 a,b,c。 在定义意义下
K3中有多少个不同的圈？
解答 在同构意义下,K3中只有一个长度为 3的圈。
但在定义意义下，不同起点 (终点 )的圈是不同的，
顶点间排列顺序不同的圈也看成是不同的，
因而 K3中有 6个不同的长为 3的圈：
abca,acba,bacb,bcab,cabc,cbac
如果只考虑起点 (终点 )的差异，
而不考虑顺时针逆时针的差异，应有 3种不同的圈，
当然它们都是同构的，画出图来只有一个。
14.3 图的连通性
无向图的连通性
无向图中顶点之间的短程线及距离
无向图的连通程度：点割集、割点、边割集、割边、连通度
有向图的连通性及判别方法
扩大路径法与极大路径
二部图及其判别方法无向图的连通性定义 14.12 设无向图 G＝ <V,E>,u,v∈ V,若 u,v之间存在通路,则称 u,v是 连通的,记作 u～ v。
v∈ V,规定 v～ v。
无向图中顶点之间的连通关系
～＝ {（ u,v） | u,v∈V 且 u与 v之间有通路 }
是自反的、对称的、传递的，因而 ～是 V上的等价关系 。
连通图与连通分支定义 14.13 若无向图 G是平凡图或 G中任何两个顶点都是连通的，则称 G为 连通图,否则称 G是 非连通图 或 分离图 。
说明,完全图 Kn(n≥1) 都是连通图零图 Nn(n≥2) 都是分离图。
定义 14.14 设无向图 G＝ <V,E>,V关于顶点之间的连通关系
～的 商集 V/～ ＝ {V1,V2,…,Vk},Vi为等价类，称导出子图
G[Vi](i＝ 1,2,…,k)为 G的 连通分支,连通分支数 k常记为
p(G)。
说明 若 G为连通图，则 p(G)＝ 1。
若 G为非连通图，则 p(G)≥2 。
在所有的 n阶无向图中,n阶零图是连通分支最多的，
p(Nn)＝ n。
无向图中顶点之间的短程线及距离定义 14.15 设 u,v为无向图 G中任意两个顶点，若 u～ v,称 u,v之间长度最短的通路 为 u,v之间的 短程线,短程线的长度称为 u,v之间的 距离,记作 d(u,v)。
当 u,v不连通时，规定 d(u,v)＝ ∞ 。
距离有以下性质：
(1)d(u,v)≥0,u＝ v时，等号成立。
(2)具有对称性,d(u,v)＝ d(v,u)。
(3)满足三角不等式,?u,v,w∈ V(G),则
d(u,v)+d(v,w)≥ d(u,w)
说明,在完全图 Kn(n≥2) 中，任何两个顶点之间的距离都是 1。
在 n阶零图 Nn(n≥2) 中，任何两个顶点之间的距离都为 ∞ 。
如何定义连通度
问题,如何定量地比较无向图的连通性的强与弱？
点连通度,为了破坏连通性，至少需要删除多少个顶点？
边连通度,为了破坏连通性，至少需要删除多少条边？
,破坏连通性,是指,变得更加不连通,。
无向图的点 割 集定义 14.16 设无向图 G＝ <V,E>,若存在 VV,且 V?≠?,使得
p(G-V?)>p(G),而对于任意的 VV?,均有 p(G-V)＝
p(G),则称 V?是 G的 点割集 。
若 V?是单元集，即 V?＝ {v},则称 v为 割点 。
{v2,v4},{v3},{v5}都是点割集
v3,v5都是割点
v1与 v6不在任何割集中。
无向图的边割集定义 14.17 设无向图 G＝ <V,E>,若存在 EE,且 E?≠?,使得 p(G-E?)>p(G),而对于任意的 EE?,均有 p(G-E)＝
p(G),则称 E?是 G的 边割集,或简称为 割集 。
若 E?是单元集，即 E?＝ {e},则称 e为 割边 或 桥 。
{e6},{e5},{e2,e3},{e1,e2},{e3
,e4},{e1,e4},{e1,e3},{e2,e4}
都是割集，
e6,e5是桥。
点连通度定义 14.18 设 G为无向连通图且为非完全图，则称
K(G)＝ min{|V?||V?为 G的点割集 }
为 G的 点连通度,简称 连通度 。
说明 连通度是为了产生一个不连通图需要删去的点的最少数目。
规定完全图 Kn(n≥1) 的点连通度为 n-1，
规定 非连通图的点连通度为 0，
若 K(G)≥ k,则称 G是 k-连通图,k为非负整数。
说明 K(G)有时简记为 K。
上例中图的点连通度为 1，此图为 1-连通图。
K5的点连通度 K＝ 4,所以 K5是 1-连通图,2-连通图,3-连通图
,4-连通图。
若 G是 k-连通图（ k≥1 ） 则在 G中删除任何 k-1个顶点后，所得图一定还是连通的。
边连通度定义 14.19 设 G是无向连通图，称
λ( G )＝ min{|E?|| E?是 G的点割集 }
为 G的 边连通度 。
规定非连通图的边连通度为 0。
若 λ( G)≥ r,则称 G是 r边 -连通图 。
说明 λ( G)也可以简记为 λ 。
若 G是 r 边 -连通图，则在 G中任意删除 r-1条边后，所得图依然是连通的。
完全图 Kn的边连通度为 n-1,因而 Kn是 r边 -连通图,0≤ r≤ n-1。
图 14.8中图的边连通度 λ ＝ 1,它只能是 1边 -连通图。
例 14.6
求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。
K＝ λ ＝ 4 K＝ λ ＝ 3 K＝ λ ＝ 2 K＝ λ ＝ 1
K=1 λ=2 K＝ λ ＝ 2 K＝ λ ＝ 0 K＝ λ ＝ 0
例 14.6的解答设第 i个图的点连通度为 Ki,边连通度为 λ i,I＝ 1,2,…,8。
容易看出,K1＝ λ 1＝ 4,K2＝ λ 2＝ 3,K3＝ λ 3＝ 2,K4＝ λ 4＝ 1，
K5=1 λ 5=2,K6＝ λ 6＝ 2,K7＝ λ 7＝ 0,K8＝ λ 8＝ 0。
(1)是 k-连通图,k边 -连通图,k＝ 1,2,3,4。
(2)是 k-连通图,k边 -连通图,k＝ 1,2,3。
(3)是 k-连通图,k边 -连通图,k＝ 1,2。
(4)是 1-连通图,1边 -连通图。
(5)是 1-连通图,k边 -连通图,k＝ 1,2。
(6)是 k-连通图,k边 -连通图,k＝ 1,2。
(7)是 0-连通图,0边 -连通图。
(8)是 0-连通图,0边 -连通图。
点连通程度为 (1)>(2)>(3)＝ (6)>(4)＝ (5)>(7)＝ (8)。
边连通程度为 (1)>(2)>(3)＝ (5)＝ (6)>(4)>(7)＝ (8)。
定理 14.7
定理 14.7 对于任何无向图 G,有
K(G)≤λ( G)≤δ( G)
例 14.7 (1)给出一些无向简单图，使得 K＝ λ ＝ δ 。
(2)给出一些无向简单图，使得 K<λ<δ 。
解答 (1) n阶无向完全图 Kn和 n阶零图 Nn都满足要求。
(2)在两个 Kn(n≥4) 之间放置一个顶点 v,使 v与两个 Kn中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。
因为这样的图中有一个割点，所以点连通度为 1，
又因为无桥，而有两条边组成的边割集，所以边连通度为 2，
当 n＝ 4时,δ ＝ 3,当 n≥5 时,δ ＝ 4。
有向图的连通性定义 14.20 设 D＝ <V,E>为一个有向图 。 vi,vj∈ V,若从 vi到 vj存在通路,则称 vi可达 vj,记作 vi→ vj，
规定 vi总是可达自身的,即 vi→ vi。
若 vi→ vj且 vj→ vi,则称 vi与 vj是 相互可达 的,记作 vi?vj。
规定 vi?vi。
说明 → 与?都是 V上的二元关系，并且不难看出?是 V上的等价关系。
定义 14.21 设 D＝ <V,E>为有向图,vi,vj∈V,若 vi→ vj,称 vi到 vj
长度最短的通路 为 vi到 vj的 短程线,
短程线的长度为 vi到 vj的距离，记作 d <vi,vj>。
说明 与无向图中顶点 vi与 vj之间的距离 d(vi,vj)相比,d<vi,vj>除无对称性外，具有 d(vi,vj)所具有的一切性质。
连通图定义 14.22 设 D＝ <V,E>为一个有向图。若 D的基图是连通图，则称 D是 弱连通图,简称为 连通图 。
若 vi,vj∈ V,vi→ vj与 vj→ vi至少成立其一，则称 D是 单向连通图 。
若均有 vi? vj,则称 D是 强连通图 。
说明 强连通图一定是单向连通图，
单向连通图一定是弱连通图。
强连通图 单向连通图 弱连通图强连通图与单向连通图的判定定理定理 14.8 设有向图 D＝ <V,E>,V＝ {v1,v2,…,vn}。 D是强连通图当且仅当 D中存在经过每个顶点至少一次的回路 。
证明 充分性 显然。
下面证明 必要性 。
由 D的强连通性可知,vi→ vi+1,i＝ 1,2,…,n-1。
设 Г i为 vi到 vi+1的通路。
又因为 vn→ v1,设 Г n为 vn到 v1的通路，则 Г 1,Г 2,…,Г n-1,Г n
所围成的回路经过 D中每个顶点至少一次。
定理 14.9 设 D是 n阶有向图,D是单向连通图当且仅当 D中存在经过每个顶点至少一次的通路。
证明 略。
问题 设有向图 D是单向连通图，但不是强连通图，问在 D中至少加几条边所得图 D?就能成为强连通图？
扩大路径法
设 G＝ <V,E>为 n阶无向图,E≠?,设 Г l为 G中一条路径，
若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来 。
继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。
设最后得到的路径为 Гl+k(长度为 l的路径扩大成了长度为 l+k
的路径 )，称 Гl+k为,极大路径,,
称使用此种方法证明问题的方法为,扩大路径法,。
有向图中可以类似地讨论，只须注意，在每步扩大中保持有向边方向的一致性。
关于极大路径的说明
由某条路经扩大出的极大路径不唯一。
极大路径不一定是图中最长的路径。
例 14.8
例 14.8 设 G为 n（ n≥4 ） 阶无向简单图,δ( G)≥3 。
证明 G中存在长度大于或等于 4的圈。
证明 不妨设 G是连通图，否则，因为 G的各连通分支的最小度也都大于或等于 3，因而可对它的某个连通分支进行讨论。
设 u,v为 G中任意两个顶点，由 G是连通图，因而 u,v之间存在通路，由定理 14.5的推论可知,u,v之间存在路径，用,扩大路径法,扩大这条路径，设最后得到的,极大路径,为 Г l＝
v0v1… vl,易知 l≥3 。
若 v0与 vl相邻，则 Г l∪( v0,vl)为长度大于或等于 4的圈。
否则，由于 d(v0)≥δ( G)≥3,因而 v0除与 Г l上的 v1相邻外，
还存在 Г l上的顶点 vk(k≠1) 和 vt(k＜ t ＜ l )与 v0相邻，则
v0v1… vk… vtv0为一个圈且长度大于或等于 4，见图。
二部图定义 14.23 设 G＝ <V,E>为一个无向图,若能将 V分成 V1和
V2(V1∪ V2＝ V,V1∩ V2＝?),使得 G中的每条边的两个端点都是一个属于 V1,另一个属于 V2,则称 G为 二部图 （ 或称 二分图,偶图 等 ）,称 V1和 V2为 互补顶点子集 。
常将二部图 G记为 <V1,V2,E>。
若 G是简单二部图,V1中每个顶点均与 V2中所有顶点相邻,
则称 G为 完全二部图,记为 Kr,s,其中 r＝ |V1|,s＝ |V2|。
说明 n阶零图为二部图。
二部图举例
K6的子图 K6的子图 K3,3
K2,3 K3,3 K2,3
二部图的判定定理定理 14.10 一个无向图 G＝ <V,E>是二部图当且仅当 G中无奇数长度的回路。
证明 必要性 。
若 G中无回路，结论显然成立。
若 G中有回路，只需证明 G中无奇圈。
设 C为 G中任意一圈，令 C＝ vi1vi2… vilvi1,易知 l≥2 。
不妨设 vi1∈ V1,则必有 vil∈ V-V1=V2，
而 l必为偶数，于是 C为偶圈，
由 C的任意性可知结论成立。
二部图的判定定理充分性 。
不妨设 G为连通图，否则可对每个连通分支进行讨论。
设 v0为 G中任意一个顶点，令
V1＝ {v|v∈ V(G)∧ d(v0,v)为偶数 }
V2＝ {v|v∈ V(G)∧ d(v0,v)为奇数 }
易知,V1≠?,V2≠?,V1∩ V2＝?,V1∪ V2＝ V(G)。
下面只要证明 V1中任意两顶点不相邻,V2中任意两点也不相邻。
若存在 vi,vj∈ V1相邻，令 (vi,vj)＝ e，
设 v0到 vi,vj的短程线分别为 Г i,Г j，
则它们的长度 d(v0,vi),d(v0,vj)都是偶数，
于是 Г i∪Г j∪ e中一定含奇圈，这与已知条件矛盾。
类似可证,V2中也不存在相邻的顶点，于是 G为二部图。
14.4 图的矩阵表示定义 14.24 设无向图 G＝ <V,E>,V＝ {v1,v2,…,vn},E＝
{e1,e2,…,em},令 mij为顶点 vi与边 ej的关联次数，则称
(mij)n× m为 G的 关联矩阵,记作 M(G)。
10000
11000
00110
01112
M ( G )
有向图的关联矩阵定义 14.25 设有向图 D＝ <V,E>中无环,V＝ {v1,v2,…,vn},E
＝ {e1,e2,…,em},令
的终点为不关联为的始点为
ji
ji
ji
ij
ev
ev
ev
m
1
0
1
则称 (mij)n× m为 D的 关联矩阵,记作 M(D)。
1-1-1-00
11000
0011-1
00011-
M ( D )
有向图的邻接矩阵定义 14.26 设有向图 D＝ <V,E>,V＝ {v1,v2,…,vn},E＝
{e1,e2,…,em},令 aij(1)为顶点 vi邻接到顶点 vj边的条数，称
(aij(1))n× n为 D的 邻接矩阵,记作 A(D),或简记为 A。
110
100
010
012
0
0
0
0
A
有向图的可达矩阵定义 14.27 设 D＝ <V,E>为有向图。 V＝ {v1,v2,…,vn},令
pij＝ 1 vi 可达 vj0 否则称 (pij)n× n为 D的 可达矩阵,记作 P(D),简记为 P。
110
110
111
111
0
0
0
1
P
14.5 图的运算定义 14.28 设 G1＝ <V1,E1>,G2＝ <V2,E2>为两个图。
若 V1∩ V2＝?,则称 G1与 G2是不交的 。
若 E1∩ E2＝?,则称 G1与 G2是 边不交的 或 边不重的 。
说明,不交的图，必然是边不交的，但反之不真。
图的运算定义 14.29 设 G1＝ <V1,E1>,G2＝ <V2,E2>为不含孤立点的两个图（它们同为无向图或同为有向图）。
(1)称以 E1∪ E2为边集，以 E1∪ E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 并图,记作 G1∪ G2。
(2)称以 E1-E2为边集，以 E1-E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 差图,记作 G1-G2。
(3)称以 E1∩ E2为边集，以 E1∩ E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 交图,记作 G1∩ G2。
(4)称以 E1⊕ E2为边集（为集合之间的对称差运算），以 E1⊕ E2
中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 环和,
记作 G1⊕ G2。
定义 14.29的说明
(1)若 G1＝ G2,则
G1∪ G2＝ G1∩ G2＝ G1(G2)
G1-G2＝ G2-G1＝ G1⊕ G2＝?
这就是在图的定义中给出空图概念的原因。
(2)当 G1与 G2边不重时，
G1∩ G2＝? G1-G2＝ G1
G2-G1＝ G2 G1?G2＝ G1∪ G2
(3)图之间环和的定义也可以用并、交、差给出，即
G1⊕ G2＝ (G1∪ G2)-(G1∩ G2)
基本要求
理解与图的定义有关的诸多概念，以及它们之间的相互关系。
深刻理解握手定理及其推论的内容，并能熟练地应用它们。
深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。
深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。
理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。
理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。
作业习题十四
6,10,19,20,21,29,30,32,33,49
14.1 图
14.2 通路与回路
14.3 图的连通性
14.4 图的矩阵表示
14.5 图的运算基本要求作业
14.1 图的基本概念
图的定义
图的一些概念和规定
简单图和多重图
顶点的度数与握手定理
图的同构
完全图与正则图
子图与补图无序积与多重集合
设 A,B为任意的两个集合，称 {{a,b}|a∈A∧b∈B} 为 A与 B
的 无序积,记作 A&B。
可将无序积中的无序对 {a,b}记为 (a,b),并且允许 a＝ b。
无论 a,b是否相等，均有 (a,b)＝ (b,a),因而 A&B＝ B&A。
元素可以重复出现的集合称为 多重集合 或者 多重集,某元素重复出现的次数称为该元素的 重复度 。
例如 在多重集合 {a,a,b,b,b,c,d}中，
a,b,c,d的重复度分别为 2,3,1,1。
定义 14.1 一个 无向图 是一个有序的二元组 <V,E>,记作 G,其中
（ 1） V≠?称为 顶点集,其元素称为 顶点 或 结点 。
（ 2） E称为 边集,它是 无序积 V&V的多重子集，其元素称为 无向边,简称 边 。
定义 14.2 一个 有向图 是一个有序的二元组 <V,E>,记作 D,其中
（ 1） V≠?称为 顶点集,其元素称为 顶点 或 结点 。
（ 2） E为 边集,它是 笛卡儿积 V× V的多重子集，其元素称为 有向边,简称 边 。
无向图和有向图说明? 可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。
例 14.1
例 14.1 (1) 给定无向图 G＝ <V,E>,其中 V＝ {v1,v2,v3,v4,v5}，
E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)},
(2) 给定有向图 D=<V,E>,其中 V＝ {a,b,c,d}，
E＝ {<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。
画出 G与 D的图形。
图的一些概念和规定
G表示无向图，但有时用 G泛指图 (无向的或有向的 )。
D只能表示有向图。
V(G),E(G)分别表示 G的 顶点集 和 边集 。
若 |V(G)|＝ n,则称 G为 n阶图 。
若 |V(G)|与 |E(G)|均为有限数，则称 G为 有限图 。
若边集 E(G)＝?,则称 G为 零图,此时，又若 G为 n阶图，则称 G
为 n阶零图,记作 Nn,特别地，称 N1为 平凡图 。
在图的定义中规定顶点集 V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定 顶点集为空集的图 为空图,并将空图记为?。
标定图与非标定图、基图
将图的集合定义转化成图形表示之后，常用 ek表示 无向边
(vi,vj)（ 或 有向边 <vi,vj>）,并称 顶点或边用字母标定的图 为 标定图,否则称为 非标定图 。
将有向图各 有向边均改成无向边后的无向图 称为原来图的 基图 。
易知标定图与非标定图是可以相互转化的，任何无向图 G
的各边均加上箭头就可以得到以 G为基图的有向图。
关联与关联次数、环、孤立点
设 G＝ <V,E>为无向图,ek＝ (vi,vj)∈E,
称 vi,vj为 ek的端点,ek与 vi或 ek与 vj是彼此相 关联 的。
若 vi≠ vj,则称 ek与 vi或 ek与 vj的 关联次数为 1。
若 vi＝ vj,则称 ek与 vi的 关联次数为 2，并称 ek为 环 。
任意的 vl∈V,若 vl≠ vi且 vl≠ vj,则称 ek与 vl的 关联次数为 0。
设 D＝ <V,E>为有向图,ek＝ <vi,vj>∈E,
称 vi,vj为 ek的 端点。
若 vi＝ vj,则称 ek为 D中的 环 。
无论在无向图中还是在有向图中，无边关联的顶点均称为 孤立点 。
相邻与邻接
设无向图 G＝ <V,E>,vi,vj∈V,ek,el∈E 。
若?et∈E,使得 et＝ (vi,vj),则称 vi与 vj是 相邻的 。
若 ek与 el至少有一个公共端点,则称 ek与 el是 相邻的 。
设有向图 D＝ <V,E>,vi,vj∈V,ek,el∈E 。
若?et∈E,使得 et＝ <vi,vj>,则称 vi为 et的 始点,vj为 et的 终点,并称 vi邻接到 vj,vj邻接于 vi。
若 ek的终点为 el的始点，则称 ek与 el相邻 。
邻域
设无向图 G＝ <V,E>,?v∈ V，
称 {u|u∈ V∧( u,v)∈ E∧ u≠ v}为 v的 邻域,记做 NG(v)。
称 NG(v)∪{ v}为 v的 闭邻域,记做 NG(v)。
称 {e|e∈ E∧ e与 v相关联 }为 v的 关联集,记做 IG(v)。
设有向图 D＝ <V,E>,?v∈ V，
称 {u|u∈V∧ <v,u>∈E∧ u≠ v}为 v的 后继元集,记做 Г +D(v)。
称 {u|u∈V∧ <u,v>∈E∧ u≠ v}为 v的 先驱元集,记做 Г -D(v)。
称 Г +D(v)∪Г -D(v)为 v的 邻域,记做 ND(v)。
称 ND(v)∪{ v}为 v的 闭邻域,记做 ND(v)。
举例
NG(v1) ＝
Г +D(d ) ＝
{v2,v5}
NG(v1) ＝ {v1,v2,v5}
IG(v1) ＝ {e1,e2,e3}
{c}
Г -D(d ) ＝ {a,c}
ND(d ) ＝ {a,c}
ND(d ) ＝ {a,c,d}
简单图与多重图定义 14.3 在无向图中，关联一对顶点的无向边如果 多于 1条,
则称这些边为 平行边,平行边的条数称为 重数 。
在有向图中，关联一对顶点的有向边如果 多于 1条,并且这些边的 始点和终点相同 (也就是它们的方向相同 )，则称这些边为 平行边 。
含平行边的图称为 多重图 。
既不含平行边也不含环的图 称为 简单图 。
例如,在图 14.1中，
(a)中 e5与 e6是平行边，
(b)中 e2与 e3是平行边，但 e6与 e7不是平行边。
(a)和 (b)两个图都不是简单图。
顶点的度数定义 14.4 设 G＝ <V,E>为一无向图,?v∈V,称 v作为边的端点次数之和为 v的度数,简称为 度,记做 dG(v)。
在不发生混淆时，简记为 d(v)。
设 D＝ <V,E>为有向图,?v∈V,
称 v作为边的始点次数之和为 v的出度,记做 d+D(v),简记作
d+(v)。
称 v作为边的终点次数之和为 v的入度,记做 d -D(v),简记作
d-(v)。
称 d+(v)+d-(v)为 v的 度数,记做 d(v)。
图的度数的相关概念
在无向图 G中，
最大度 △ (G)＝ max{d(v)|v∈V(G)}
最小度 δ(G) ＝ min{d(v)|v∈V(G)}
在有向图 D中，
最大出度 △ +(D)＝ max{d+(v)|v∈V(D)}
最小出度 δ +(D)＝ min{d+(v)|v∈V(D)}
最大入度 △ -(D)＝ max{d-(v)|v∈V(D)}
最小入度 δ -(D)＝ min{d-(v)|v∈V(D)}
称度数为 1的顶点为 悬挂顶点,与它关联的边称为 悬挂边 。
度为偶数 (奇数 )的顶点称为 偶度 (奇度 )顶点 。
图的度数举例
d(v1)＝ 4(注意，环提供 2度 )，
△＝ 4,δ ＝ 1，
v4是悬挂顶点,e7是悬挂边。
d+(a)＝ 4,d-(a)＝ 1
(环 e1提供出度 1，提供入度 1)，
d(a)＝ 4+1＝ 5。△＝ 5,δ ＝ 3，
△ +＝ 4 (在 a点达到 )
δ +＝ 0(在 b点达到 )
△ -＝ 3(在 b点达到 )
δ -＝ 1(在 a和 c点达到 )
握手定理定理 14.1 设 G＝ <V,E>为任意无向图,V＝ {v1,v2,…,vn}，
|E|＝ m,则
n
1
2)(
i
i mvd
说明 任何无向图中，各顶点度数之和等于边数的两倍。
证明 G中每条边 (包括环 )均有两个端点，
所以在计算 G中各顶点度数之和时，
每条边均提供 2度，当然,m条边，共提供 2m度。
定理 14.2 设 D＝ <V,E>为任意有向图,V＝ {v1,v2,…,vn}，
|E|＝ m,则
n nn
1 11
)()(,2)(
i i
ii
i
i mvdvdmvd 且握手定理的推论推论 任何图 (无向的或有向的 )中，奇度顶点的个数是偶数。
证明 设 G＝ <V,E>为任意一图，令
V1＝ {v|v∈V∧ d(v)为奇数 }
V2＝ {v|v∈V∧ d(v)为偶数 }
则 V1∪V 2＝ V,V1∩V 2＝?,由握手定理可知
Vv
vdm )(2
21
)()(
VvVv
vdvd
由于 2m和
2
)(
Vv
vd
，所以
1
)(
Vv
vd
为偶数,
但因 V1中顶点度数为奇数,所以 |V1|必为偶数。
问题研究问题,在一个部门的 25个人中间，由于意见不同，是否可能每个人恰好与其他 5个人意见一致？
解答,不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。
说明：
(1)很多离散问题可以用图模型求解。
(2)为了建立一个图模型，需要决定顶点和边分别代表什么。
(3)在一个图模型中，边经常代表两个顶点之间的关系。
度数列设 G＝ <V,E>为一个 n阶无向图,V＝ {v1,v2,…,vn},称 d(v1)，
d(v2),…,d(vn)为 G的 度数列 。
对于顶点标定的无向图，它的度数列是唯一的。
反之，对于给定的非负整数列 d＝ {d1,d2,…,dn},若存在 V＝
{v1,v2,…,vn}为顶点集的 n阶无向图 G,使得 d(vi)＝ di,则称
d是 可图化的 。
特别地，若所得图是简单图，则称 d是 可简单图化的 。
类似地，设 D＝ <V,E>为一个 n阶有向图,V＝ {v1,v2,…,vn},称
d(v1),d(v2),…,d(vn)为 D的 度数列,另外称 d+(v1)，
d+(v2),…,d+(vn)与 d-(v1),d-(v2),…,d-(vn)分别为 D的出度列 和 入度列 。
度数列举例按顶点的标定顺序，度数列为
4,4,2,1,3。
按字母顺序，度数列，出度列，入度列分别为
5,3,3,3
4,0,2,1
1,3,1,2
可图化的充要条件定理 14.3 设非负整数列 d＝ (d1,d2,…,dn),则 d是可图化的当且仅当
n
1
)2(m o d0
i
id
证明 必要性。 由握手定理显然得证。
充分性。 由已知条件可知,d中有偶数个奇数度点。
奇数度点两两之间连一边，剩余度用环来实现。
5 3
3 1
定理 14.3的证明由握手定理可知必然性显然。
下面证明充分性。
由已知条件可知,d中有 2k(0≤k≤[n/2]) 个奇数，
不妨设它们为 d1,d2,…,dk,dk+1,dk+2,…,d2k。
可用多种方法做出 n阶无向图 G＝ <V,E>,V＝ {v1,v2,… vn}。
比如边集如下产生：在顶点 vr与 vr+k之间连边,r＝ 1,2,…,k。
若 di为偶数，令 d?i＝ di,若 di为奇数，令 d?i＝ di-1，
得 d?＝ (d?1,d?2,…,d?n),则 d?i均为偶数。
再在 vi处做出 d?i/2条环,i＝ 1,…,n，
将所得各边集合在一起组成 E,则 G的度数列为 d。
其实,di为偶数时,d(vi)＝ 2· d?i/2＝ 2· di/2＝ di，
当 di为奇数时,d(vi)＝ 1+2· d?i/2＝ 1+d?i＝ 1+di-1＝ di，
这就证明了 d是可图化的。
可图化举例由定理 14.3立即可知，
(3,3,2,1),(3,2,2,1,1)等是不可图化的，
(3,3,2,2),(3,2,2,2,1)等是可图化的。
定理 14.4
定理 14.4 设 G为任意 n阶无向简单图，则△ (G)≤ n-1。
证明 因为 G既无平行边也无环，
所以 G中任何顶点 v至多与其余的 n-1个顶点均相邻，
于是 d(v)≤ n-1,由于 v的任意性，所以△ (G)≤ n-1。
例 14.2 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？
(1) (5,5,4,4,2,1)
不可图化。
(2) (5,4,3,2,2)
可图化，不可简单图化。若它可简单图化，
设所得图为 G,则 (G)＝ max{5,4,3,2,2}＝ 5，
这与定理 14.4矛盾。
例 14.2
(3) (3,3,3,1)
可图化，不可简单图化。假设该序列可以简单图化，
设 G＝ <V,E>以该序列为度数列。
不妨设 V＝ {v1,v2,v3,v4}
且 d(v1)＝ d(v2)＝ d(v3)＝ 3,d(v4)＝ 1，
由于 d(v4)＝ 1,因而 v4只能与 v1,v2,v3之一相邻，
于是 v1,v2,v3不可能都是 3度顶点，这是矛盾的，
因而 (3)中序列也不可简单图化。
(4) (d1,d2,… dn),d1>d2>… >dn≥1 且 为偶数。
n
1i
id
可图化，不可简单图化。
例 14.2
(5) (4,4,3,3,2,2)
可简单图化。下图中两个 6阶无向简单图都以 (5)中序列为度数列。
图的同构定义 14.5 设 G1＝ <V1,E1>,G2＝ <V2,E2>为两个无向图，
若存在双射函数 f,V1→V 2,对于 vi,vj∈V 1,(vi,vj)∈E 1
当且仅当 (f(vi),f(vj))∈E 2，
并且 (vi,vj)与 (f(vi),f(vj))的重数相同，
则称 G1与 G2是同构的,记做 G1≌ G2。
说明 (1) 类似地，可以定义两个有向图的同构。
(2) 图的同构关系看成全体图集合上的二元关系。
(3) 图的同构关系是等价关系。
(4) 在图同构的意义下，图的数学定义与图形表示是一一对应的。
图的同构举例彼得森 (Petersen)图完全图定义 14.6 设 G为 n阶无向简单图，若 G中 每个顶点均与其余的 n-1
个顶点相邻,则称 G为 n阶无向完全图,简称 n阶完全图,记做
Kn(n≥1) 。
设 D为 n阶有向简单图，若 D中每个顶点都邻接到其余的 n-1个顶点，又邻接于其余的 n-1个顶点，则称 D是 n阶有向完全图 。
设 D为 n阶有向简单图，若 D的基图为 n阶无向完全图 Kn,则称 D
是 n阶竞赛图 。
完全图举例
n阶无向完全图的边数为,n(n-1)/2
n阶有向完全图的边数为,n(n-1)
n阶竞赛图的边数为,n(n-1)/2
K5 3阶有向完全图 4阶竞赛图正则图定义 14.7 设 G为 n阶无向简单图，若 v∈V(G),均有 d(v)＝ k，
则称 G为 k-正则图 。
举例 n阶零图是 0-正则图
n阶无向完全图是 (n-1)-正则图彼得森图是 3-正则图说明 n阶 k-正则图中，边数 m＝ kn/2。
当 k为奇数时,n必为偶数。
子图定义 14.8 设 G＝ <V,E>,G?＝ <V?,E?>为两个图 (同为无向图或同为有向图 )，若 VV且 EE,则称 G?是 G的 子图,G为 G?
的 母图,记作 GG。
若 VV或 EE,则称 G?为 G的 真子图 。
若 V?＝ V,则称 G?为 G的 生成子图 。
设 G＝ <V,E>为一图,V1?V且 V1≠?,称以 V1为顶点集，以
G中 两个端点都在 V1中的边 组成边集 E1的图为 G的 V1导出的子图,记作 G[V1]。
设 E1?E且 E1≠?,称以 E1为边集，以 E1中边关联的顶点为顶点集 V1的图 为 G的 E1导出的子图,记作 G[E1]。
导出子图举例在上图中，设 G为 (1)中图所表示，
取 V1＝ {a,b,c},则 V1的导出子图 G[V1]为 (2)中图所示。
取 E1＝ {e1,e3},则 E1的导出子图 G[E1]为 (3)中图所示。
例 14.3
(1) 画出 4阶 3条边的所有非同构的无向简单图。
由握手定理可知，所画的无向简单图各顶点度数之和为 2× 3＝
6，最大度小于或等于 3。于是所求无向简单图的度数列应满足的条件是，将 6分成 4个非负整数，每个整数均大于或等于 0且小于或等于 3，并且 奇数的个数为偶数 。将这样的整数列排出来只有下面三种情况：
(1) 2,2,1,1
(2) 3,1,1,1
(3) 2,2,2,0
将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。
对于给定的正整数 n和 m(m≤ n(n-1)/2)，
构造出所有非同构的 n阶 m条边的所有非同构的无向 (有向 )简单图，这是目前还没有解决的难题。
例 14.3
(2) 画出 3阶 2条边的所有非同构的有向简单图。
由握手定理可知，所画有向简单图各顶点度数之和为 4，最大出度和最大入度均小于或等于 2。度数列及入度出度列为
1,2,1 入度列为 0,1,1 或 0,2,0 或 1,0,1出度列为 1,1,0 或 1,0,1 或 0,2,0
2,2,0 入度列为 1,1,0出度列为 1,1,0
定义 14.9
定义 14.9 设 G＝ <V,E>为 n阶无向简单图,以 V为顶点集,以所有 使 G成为完全图 Kn的添加边组成的集合 为边集的图，称为 G的 补图,记作 G。
若图 G≌ G,则称为 G是 自补图 。
(1)为自补图
(2)和 (3)互为补图定义 14.10
定义 14.10 设 G＝ <V,E>为无向图。
(1)设 e∈ E,用 G-e表示从 G中去掉边 e,称为 删除 e。
设 EE,用 G-E?表示从 G中删除 E?中所有的边，称为 删除 E?。
(2)设 v∈ V,用 G-v表示从 G中去掉 v及所关联的一切边，称为 删除顶点 v。
设 VV,用 G-V?表示从 G中删除 V?中所有顶点，称为 删除 V?。
(3)设边 e＝ (u,v)∈ E,用 G\e表示从 G中删除 e后，将 e的两个端点
u,v用一个新的顶点 w(或用 u或 v充当 w)代替，使 w关联除 e外 u,v
关联的所有边，称为 边 e的收缩 。
(4)设 u,v∈ V(u,v可能相邻，也可能不相邻 ),用 G∪( u,v)(或
G+(u,v))表示在 u,v之间加一条边 (u,v),称为 加新边 。
说明 在收缩边和加新边过程中可能产生环和平行边。
举例
G G－ e5 G－ {e1,e4}
G－ v5 G－ {v4,v5} G\e5
14.2 通路与回路定义 14.11 设 G为无向标定图,G中顶点与边的交替序列 Г＝
vi0ej1vi1ej2vi2… ejivil称为 vi0到 vil的 通路,其中,vir-1,vir为 ejr的 端点
,r ＝ 1,2,…,l,vi0,vil分别称为 Г的 始点 与 终点,Г中边的条数称为它的 长度 。
若 vi0＝ vil,则称通路为 回路 。
若 Г的 所有边各异,则称 Г为 简单通路,
又若 vi0＝ vil,则称 Г为 简单回路 。
若 Г的所有 顶点 (除 vi0与 vij可能相同外 )各异,所有 边也各异,则称 Г为 初级通路 或 路径,
又若 vi0＝ vil,则称 Г为 初级回路 或 圈 。
将长度为奇数的圈称为 奇圈,长度为偶数的圈称为 偶圈 。
关于通路与回路的说明
在初级通路与初级回路的定义中，仍将初级回路看成初级通路 (路径 )的特殊情况，只是在应用中初级通路 (路径 )都是始点与终点不相同的,长为 1的圈只能由环生成,长为 2
的圈只能由平行边生成,因而在 简单无向图中，圈的长度至少为 3。
若 Г 中有 边重复 出现，则称 Г 为 复杂通路,
又若 vi0＝ vil,则称 Г 为 复杂回路 。
在有向图中,通路、回路及分类的定义与无向图中非常相似，只是 要注意有向边方向的一致性 。
在以上的定义中，将回路定义成通路的特殊情况，即 回路也是通路,又 初级通路 (回路 )是简单通路 (回路 )，但反之不真。
通路和回路的简单表示法
(1)只用边的序列表示通路 (回路 )。定义 14.11中的 Г 可以表示成 ej1,ej2,…,ejl。
(2)在简单图中也可以只用顶点序列表示通路 (回路 )。定义中的 Г 也可以表示成 vi0,vi2,…,vil。
(3)为了写出非标定图中的通路 (回路 )，可以先将非标定图标成标定图，再写出通路与回路。
(4)在非简单标定图中，当只用顶点序列表示不出某些通路 (
回路 )时，可在顶点序列中加入一些边 (这些边是平行边或环 )，可称这种表示法为 混合表示法 。
定理 14.5
定理 14.5 在 n阶图 G中,若从顶点 vi到 vj（ vi≠ vj） 存在通路,则从
vi到 vj存在长度小于或等于 n-1的通路 。
证明设 Г＝ v0e1v1e2… elvl(v0＝ vi,vl＝ vj)为 G中一条长度为 l的通路，
若 l≤ n-1,则 Г满足要求，
否则必有 l+1>n,即 Г上的顶点数大于 G中的顶点数，
于是必存在 k,s,0≤ k<s≤ l,使得 vs＝ vk,
即在 Г上存在 vs到自身的回路 Csk,
在 Г上删除 Csk上的一切边及除 vs外的一切顶点，
得 Г?＝ v0e1v1e2… vkes+1 … elvl,Г?仍为 vi到 vj的通路，
且长度至少比 Г 减少 1。
若 Г?还不满足要求，则重复上述过程，由于 G是有限图，经过有限步后，必得到 vi到 vj长度小于或等于 n-1的通路。
定理 14.6
推论 在 n阶图 G中，若从顶点 vi到 vj（ vi≠ vj） 存在通路，则 vi到
vj一定存在长度小于或等于 n-1的初级通路（路径）。
定理 14.6 在一个 n阶图 G中，若存在 vi 到自身的回路，则一定存在 vi 到自身长度小于或等于 n的回路。
推论 在一个 n阶图 G中，若存在 vi 到自身的简单回路，则一定存在 vi 到自身长度小于或等于 n的初级回路。
例 14.4
例 14.4 无向完全图 Kn(n≥3) 中有几种非同构的圈？
解答 长度相同的圈都是同构的，
因而只有长度不同的圈才是非同构的，
易知 Kn(n≥3) 中含长度为 3,4,…,n的圈，
所以 Kn(n≥3) 中有 n-2种非同构的圈。
例 14.5
例 14.5 无向完全图 K3的顶点依次标定为 a,b,c。 在定义意义下
K3中有多少个不同的圈？
解答 在同构意义下,K3中只有一个长度为 3的圈。
但在定义意义下，不同起点 (终点 )的圈是不同的，
顶点间排列顺序不同的圈也看成是不同的，
因而 K3中有 6个不同的长为 3的圈：
abca,acba,bacb,bcab,cabc,cbac
如果只考虑起点 (终点 )的差异，
而不考虑顺时针逆时针的差异，应有 3种不同的圈，
当然它们都是同构的，画出图来只有一个。
14.3 图的连通性
无向图的连通性
无向图中顶点之间的短程线及距离
无向图的连通程度：点割集、割点、边割集、割边、连通度
有向图的连通性及判别方法
扩大路径法与极大路径
二部图及其判别方法无向图的连通性定义 14.12 设无向图 G＝ <V,E>,u,v∈ V,若 u,v之间存在通路,则称 u,v是 连通的,记作 u～ v。
v∈ V,规定 v～ v。
无向图中顶点之间的连通关系
～＝ {（ u,v） | u,v∈V 且 u与 v之间有通路 }
是自反的、对称的、传递的，因而 ～是 V上的等价关系 。
连通图与连通分支定义 14.13 若无向图 G是平凡图或 G中任何两个顶点都是连通的，则称 G为 连通图,否则称 G是 非连通图 或 分离图 。
说明,完全图 Kn(n≥1) 都是连通图零图 Nn(n≥2) 都是分离图。
定义 14.14 设无向图 G＝ <V,E>,V关于顶点之间的连通关系
～的 商集 V/～ ＝ {V1,V2,…,Vk},Vi为等价类，称导出子图
G[Vi](i＝ 1,2,…,k)为 G的 连通分支,连通分支数 k常记为
p(G)。
说明 若 G为连通图，则 p(G)＝ 1。
若 G为非连通图，则 p(G)≥2 。
在所有的 n阶无向图中,n阶零图是连通分支最多的，
p(Nn)＝ n。
无向图中顶点之间的短程线及距离定义 14.15 设 u,v为无向图 G中任意两个顶点，若 u～ v,称 u,v之间长度最短的通路 为 u,v之间的 短程线,短程线的长度称为 u,v之间的 距离,记作 d(u,v)。
当 u,v不连通时，规定 d(u,v)＝ ∞ 。
距离有以下性质：
(1)d(u,v)≥0,u＝ v时，等号成立。
(2)具有对称性,d(u,v)＝ d(v,u)。
(3)满足三角不等式,?u,v,w∈ V(G),则
d(u,v)+d(v,w)≥ d(u,w)
说明,在完全图 Kn(n≥2) 中，任何两个顶点之间的距离都是 1。
在 n阶零图 Nn(n≥2) 中，任何两个顶点之间的距离都为 ∞ 。
如何定义连通度
问题,如何定量地比较无向图的连通性的强与弱？
点连通度,为了破坏连通性，至少需要删除多少个顶点？
边连通度,为了破坏连通性，至少需要删除多少条边？
,破坏连通性,是指,变得更加不连通,。
无向图的点 割 集定义 14.16 设无向图 G＝ <V,E>,若存在 VV,且 V?≠?,使得
p(G-V?)>p(G),而对于任意的 VV?,均有 p(G-V)＝
p(G),则称 V?是 G的 点割集 。
若 V?是单元集，即 V?＝ {v},则称 v为 割点 。
{v2,v4},{v3},{v5}都是点割集
v3,v5都是割点
v1与 v6不在任何割集中。
无向图的边割集定义 14.17 设无向图 G＝ <V,E>,若存在 EE,且 E?≠?,使得 p(G-E?)>p(G),而对于任意的 EE?,均有 p(G-E)＝
p(G),则称 E?是 G的 边割集,或简称为 割集 。
若 E?是单元集，即 E?＝ {e},则称 e为 割边 或 桥 。
{e6},{e5},{e2,e3},{e1,e2},{e3
,e4},{e1,e4},{e1,e3},{e2,e4}
都是割集，
e6,e5是桥。
点连通度定义 14.18 设 G为无向连通图且为非完全图，则称
K(G)＝ min{|V?||V?为 G的点割集 }
为 G的 点连通度,简称 连通度 。
说明 连通度是为了产生一个不连通图需要删去的点的最少数目。
规定完全图 Kn(n≥1) 的点连通度为 n-1，
规定 非连通图的点连通度为 0，
若 K(G)≥ k,则称 G是 k-连通图,k为非负整数。
说明 K(G)有时简记为 K。
上例中图的点连通度为 1，此图为 1-连通图。
K5的点连通度 K＝ 4,所以 K5是 1-连通图,2-连通图,3-连通图
,4-连通图。
若 G是 k-连通图（ k≥1 ） 则在 G中删除任何 k-1个顶点后，所得图一定还是连通的。
边连通度定义 14.19 设 G是无向连通图，称
λ( G )＝ min{|E?|| E?是 G的点割集 }
为 G的 边连通度 。
规定非连通图的边连通度为 0。
若 λ( G)≥ r,则称 G是 r边 -连通图 。
说明 λ( G)也可以简记为 λ 。
若 G是 r 边 -连通图，则在 G中任意删除 r-1条边后，所得图依然是连通的。
完全图 Kn的边连通度为 n-1,因而 Kn是 r边 -连通图,0≤ r≤ n-1。
图 14.8中图的边连通度 λ ＝ 1,它只能是 1边 -连通图。
例 14.6
求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。
K＝ λ ＝ 4 K＝ λ ＝ 3 K＝ λ ＝ 2 K＝ λ ＝ 1
K=1 λ=2 K＝ λ ＝ 2 K＝ λ ＝ 0 K＝ λ ＝ 0
例 14.6的解答设第 i个图的点连通度为 Ki,边连通度为 λ i,I＝ 1,2,…,8。
容易看出,K1＝ λ 1＝ 4,K2＝ λ 2＝ 3,K3＝ λ 3＝ 2,K4＝ λ 4＝ 1，
K5=1 λ 5=2,K6＝ λ 6＝ 2,K7＝ λ 7＝ 0,K8＝ λ 8＝ 0。
(1)是 k-连通图,k边 -连通图,k＝ 1,2,3,4。
(2)是 k-连通图,k边 -连通图,k＝ 1,2,3。
(3)是 k-连通图,k边 -连通图,k＝ 1,2。
(4)是 1-连通图,1边 -连通图。
(5)是 1-连通图,k边 -连通图,k＝ 1,2。
(6)是 k-连通图,k边 -连通图,k＝ 1,2。
(7)是 0-连通图,0边 -连通图。
(8)是 0-连通图,0边 -连通图。
点连通程度为 (1)>(2)>(3)＝ (6)>(4)＝ (5)>(7)＝ (8)。
边连通程度为 (1)>(2)>(3)＝ (5)＝ (6)>(4)>(7)＝ (8)。
定理 14.7
定理 14.7 对于任何无向图 G,有
K(G)≤λ( G)≤δ( G)
例 14.7 (1)给出一些无向简单图，使得 K＝ λ ＝ δ 。
(2)给出一些无向简单图，使得 K<λ<δ 。
解答 (1) n阶无向完全图 Kn和 n阶零图 Nn都满足要求。
(2)在两个 Kn(n≥4) 之间放置一个顶点 v,使 v与两个 Kn中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。
因为这样的图中有一个割点，所以点连通度为 1，
又因为无桥，而有两条边组成的边割集，所以边连通度为 2，
当 n＝ 4时,δ ＝ 3,当 n≥5 时,δ ＝ 4。
有向图的连通性定义 14.20 设 D＝ <V,E>为一个有向图 。 vi,vj∈ V,若从 vi到 vj存在通路,则称 vi可达 vj,记作 vi→ vj，
规定 vi总是可达自身的,即 vi→ vi。
若 vi→ vj且 vj→ vi,则称 vi与 vj是 相互可达 的,记作 vi?vj。
规定 vi?vi。
说明 → 与?都是 V上的二元关系，并且不难看出?是 V上的等价关系。
定义 14.21 设 D＝ <V,E>为有向图,vi,vj∈V,若 vi→ vj,称 vi到 vj
长度最短的通路 为 vi到 vj的 短程线,
短程线的长度为 vi到 vj的距离，记作 d <vi,vj>。
说明 与无向图中顶点 vi与 vj之间的距离 d(vi,vj)相比,d<vi,vj>除无对称性外，具有 d(vi,vj)所具有的一切性质。
连通图定义 14.22 设 D＝ <V,E>为一个有向图。若 D的基图是连通图，则称 D是 弱连通图,简称为 连通图 。
若 vi,vj∈ V,vi→ vj与 vj→ vi至少成立其一，则称 D是 单向连通图 。
若均有 vi? vj,则称 D是 强连通图 。
说明 强连通图一定是单向连通图，
单向连通图一定是弱连通图。
强连通图 单向连通图 弱连通图强连通图与单向连通图的判定定理定理 14.8 设有向图 D＝ <V,E>,V＝ {v1,v2,…,vn}。 D是强连通图当且仅当 D中存在经过每个顶点至少一次的回路 。
证明 充分性 显然。
下面证明 必要性 。
由 D的强连通性可知,vi→ vi+1,i＝ 1,2,…,n-1。
设 Г i为 vi到 vi+1的通路。
又因为 vn→ v1,设 Г n为 vn到 v1的通路，则 Г 1,Г 2,…,Г n-1,Г n
所围成的回路经过 D中每个顶点至少一次。
定理 14.9 设 D是 n阶有向图,D是单向连通图当且仅当 D中存在经过每个顶点至少一次的通路。
证明 略。
问题 设有向图 D是单向连通图，但不是强连通图，问在 D中至少加几条边所得图 D?就能成为强连通图？
扩大路径法
设 G＝ <V,E>为 n阶无向图,E≠?,设 Г l为 G中一条路径，
若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来 。
继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。
设最后得到的路径为 Гl+k(长度为 l的路径扩大成了长度为 l+k
的路径 )，称 Гl+k为,极大路径,,
称使用此种方法证明问题的方法为,扩大路径法,。
有向图中可以类似地讨论，只须注意，在每步扩大中保持有向边方向的一致性。
关于极大路径的说明
由某条路经扩大出的极大路径不唯一。
极大路径不一定是图中最长的路径。
例 14.8
例 14.8 设 G为 n（ n≥4 ） 阶无向简单图,δ( G)≥3 。
证明 G中存在长度大于或等于 4的圈。
证明 不妨设 G是连通图，否则，因为 G的各连通分支的最小度也都大于或等于 3，因而可对它的某个连通分支进行讨论。
设 u,v为 G中任意两个顶点，由 G是连通图，因而 u,v之间存在通路，由定理 14.5的推论可知,u,v之间存在路径，用,扩大路径法,扩大这条路径，设最后得到的,极大路径,为 Г l＝
v0v1… vl,易知 l≥3 。
若 v0与 vl相邻，则 Г l∪( v0,vl)为长度大于或等于 4的圈。
否则，由于 d(v0)≥δ( G)≥3,因而 v0除与 Г l上的 v1相邻外，
还存在 Г l上的顶点 vk(k≠1) 和 vt(k＜ t ＜ l )与 v0相邻，则
v0v1… vk… vtv0为一个圈且长度大于或等于 4，见图。
二部图定义 14.23 设 G＝ <V,E>为一个无向图,若能将 V分成 V1和
V2(V1∪ V2＝ V,V1∩ V2＝?),使得 G中的每条边的两个端点都是一个属于 V1,另一个属于 V2,则称 G为 二部图 （ 或称 二分图,偶图 等 ）,称 V1和 V2为 互补顶点子集 。
常将二部图 G记为 <V1,V2,E>。
若 G是简单二部图,V1中每个顶点均与 V2中所有顶点相邻,
则称 G为 完全二部图,记为 Kr,s,其中 r＝ |V1|,s＝ |V2|。
说明 n阶零图为二部图。
二部图举例
K6的子图 K6的子图 K3,3
K2,3 K3,3 K2,3
二部图的判定定理定理 14.10 一个无向图 G＝ <V,E>是二部图当且仅当 G中无奇数长度的回路。
证明 必要性 。
若 G中无回路，结论显然成立。
若 G中有回路，只需证明 G中无奇圈。
设 C为 G中任意一圈，令 C＝ vi1vi2… vilvi1,易知 l≥2 。
不妨设 vi1∈ V1,则必有 vil∈ V-V1=V2，
而 l必为偶数，于是 C为偶圈，
由 C的任意性可知结论成立。
二部图的判定定理充分性 。
不妨设 G为连通图，否则可对每个连通分支进行讨论。
设 v0为 G中任意一个顶点，令
V1＝ {v|v∈ V(G)∧ d(v0,v)为偶数 }
V2＝ {v|v∈ V(G)∧ d(v0,v)为奇数 }
易知,V1≠?,V2≠?,V1∩ V2＝?,V1∪ V2＝ V(G)。
下面只要证明 V1中任意两顶点不相邻,V2中任意两点也不相邻。
若存在 vi,vj∈ V1相邻，令 (vi,vj)＝ e，
设 v0到 vi,vj的短程线分别为 Г i,Г j，
则它们的长度 d(v0,vi),d(v0,vj)都是偶数，
于是 Г i∪Г j∪ e中一定含奇圈，这与已知条件矛盾。
类似可证,V2中也不存在相邻的顶点，于是 G为二部图。
14.4 图的矩阵表示定义 14.24 设无向图 G＝ <V,E>,V＝ {v1,v2,…,vn},E＝
{e1,e2,…,em},令 mij为顶点 vi与边 ej的关联次数，则称
(mij)n× m为 G的 关联矩阵,记作 M(G)。
10000
11000
00110
01112
M ( G )
有向图的关联矩阵定义 14.25 设有向图 D＝ <V,E>中无环,V＝ {v1,v2,…,vn},E
＝ {e1,e2,…,em},令
的终点为不关联为的始点为
ji
ji
ji
ij
ev
ev
ev
m
1
0
1
则称 (mij)n× m为 D的 关联矩阵,记作 M(D)。
1-1-1-00
11000
0011-1
00011-
M ( D )
有向图的邻接矩阵定义 14.26 设有向图 D＝ <V,E>,V＝ {v1,v2,…,vn},E＝
{e1,e2,…,em},令 aij(1)为顶点 vi邻接到顶点 vj边的条数，称
(aij(1))n× n为 D的 邻接矩阵,记作 A(D),或简记为 A。
110
100
010
012
0
0
0
0
A
有向图的可达矩阵定义 14.27 设 D＝ <V,E>为有向图。 V＝ {v1,v2,…,vn},令
pij＝ 1 vi 可达 vj0 否则称 (pij)n× n为 D的 可达矩阵,记作 P(D),简记为 P。
110
110
111
111
0
0
0
1
P
14.5 图的运算定义 14.28 设 G1＝ <V1,E1>,G2＝ <V2,E2>为两个图。
若 V1∩ V2＝?,则称 G1与 G2是不交的 。
若 E1∩ E2＝?,则称 G1与 G2是 边不交的 或 边不重的 。
说明,不交的图，必然是边不交的，但反之不真。
图的运算定义 14.29 设 G1＝ <V1,E1>,G2＝ <V2,E2>为不含孤立点的两个图（它们同为无向图或同为有向图）。
(1)称以 E1∪ E2为边集，以 E1∪ E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 并图,记作 G1∪ G2。
(2)称以 E1-E2为边集，以 E1-E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 差图,记作 G1-G2。
(3)称以 E1∩ E2为边集，以 E1∩ E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 交图,记作 G1∩ G2。
(4)称以 E1⊕ E2为边集（为集合之间的对称差运算），以 E1⊕ E2
中边关联的顶点组成的集合为顶点集的图为 G1与 G2的 环和,
记作 G1⊕ G2。
定义 14.29的说明
(1)若 G1＝ G2,则
G1∪ G2＝ G1∩ G2＝ G1(G2)
G1-G2＝ G2-G1＝ G1⊕ G2＝?
这就是在图的定义中给出空图概念的原因。
(2)当 G1与 G2边不重时，
G1∩ G2＝? G1-G2＝ G1
G2-G1＝ G2 G1?G2＝ G1∪ G2
(3)图之间环和的定义也可以用并、交、差给出，即
G1⊕ G2＝ (G1∪ G2)-(G1∩ G2)
基本要求
理解与图的定义有关的诸多概念，以及它们之间的相互关系。
深刻理解握手定理及其推论的内容，并能熟练地应用它们。
深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。
深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。
理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。
理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。
作业习题十四
6,10,19,20,21,29,30,32,33,49
