第 8章 图的基本概念第 8章 图的基本概念
8.1 图的定义及相关术语
8.2 通路回路图的连通性
8.3 图的矩阵表示
8.4 例题选解习 题 八第 8章 图的基本概念
8.1 图的定义及相关术语
1.图图论作为数学的分支给出了图的严格的数学定义,
为此我们首先给出无序积的概念 。
A,B是任意两个非空集合,A与 B的无序积记为
A&B,即
A&B={（ a,b） |a∈ A,b∈ B}
性质,（ a,b） =（ b,a）
第 8章 图的基本概念
【 例 8.1.1】 A={a,b,c},B={1,2}，求 A&B、
B&A和 B&B。
解 A&B={（ a,1）,（ a,2）,（ b,1）,
（ b,2）,（ c,1）,（ c,3） }=B&A
B&B={（ 1,1）,（ 1,2）,（ 2,2） }
第 8章 图的基本概念定义 8.1.1 图是一个二元组 G=〈 V,E〉,其中 V
（ V≠ ） 是顶点集,E是边集 。 当 E是无序积 V&V的多重子集时,其元素为无向边,图 G为无向图 。 当 E是有序积 V× V的多重子集时,其元素为有向边,图 G为有向图 。
所谓多重子集是指集中元素可以重复 。
第 8章 图的基本概念
【 例 8.1.2】 图 8.1.1中 （ a）,（ b） 是无向图,图
（ c） 是有向图 。
图 8.1.1（ b） 的 v1,v2,v3,v4,v5,这样的图称为标定图 。 同时也可对边进行标定,这里 e1=（ v1,v2）,
e2=（ v1,v4）,e3=（ v1,v5）,e4=（ v2,v5）,
e5=（ v2,v5）,e6=（ v4,v5） 。 当 ei=（ vj,vk） 时,称
vj和 vk是 ei的端点,并称 ei与 vj和 vk相关联,当 ei=〈 vj,vk〉
是有向边时,又称 vj是 ei的起点,vk是 ei的终点 。 如果图的顶点集 V和边集 E均是有穷集,则称图为有限图,本书所讨论的均是有限图 。
第 8章 图的基本概念图 8.1.1
( a )
( b ) ( c )
e
1
e
2
e
3
e
4
e
5
e
6
1 2
4 3
5
第 8章 图的基本概念下面介绍一些图的基本概念和常用术语 。
邻接点 同一条边的两个端点 。
孤立顶点 没有边与之关联的顶点 。
零图 顶点集 V非空但边集 E为空集的图 。
平凡图 |V|=1,|E|=m=0的图 。
邻接边 关联同一个顶点的两条边 。
环 关联同一个顶点的一条边 （（ v,v） 或 〈 v,v〉 ） 。
第 8章 图的基本概念平行边 关联一对顶点的 m条边 （ m≥2,称重数,若是有向边则应方向相同 ） 。
多重图 含有平行边 （ 无环 ） 的图 。
简单图 不含平行边和环的图 。
完全图 每对顶点间均有边相连的无向简单图 。 n阶完全图记作 Kn。
竞赛图 在 Kn的每条边上任取一个方向的有向图 。
有向完全图 每对顶点间均有一对方向相反的边相连的有向图 。
第 8章 图的基本概念由完全图的定义易知，无向完全图 Kn的边数为
2 1( ) ( 1 )
2nnE K C n n
有向完全图 G的边数为
( ) ( 1 )E G n n
第 8章 图的基本概念顶点的度数 顶点所关联的边数。顶点 v的度数记作 d（ v）。在有向图中，以顶点 v为起点的边数称顶点
v的出度，记作 d+（ v） ;以顶点 v为终点的边数称顶点 v
的入度，记作 d-（ v）。
第 8章 图的基本概念图 G的最大度 Δ(G） =max{d（ v） |v∈ V（ G)}
图 G的最小度 δ（ G） =min{d（ v） |v∈ V（ G） }
有向图 G的最大出度 Δ+（ G） =max{d+（ v） |v∈ V（ G） }
有向图 G的最小出度 δ+（ G） =min{d+（ v） |v∈ V（ G） }
有向图 G的最大入度 Δ-（ G） =max{d-（ v） |v∈ V（ G） }
有向图 G的最小入度 δ-（ G） =min{d-（ v） |v∈ V（ G） }
k-正则图 每个顶点的度数均是 k的无向图 。
另外,我们称度数为 1的顶点为悬挂点,称与悬挂点关联的边为悬挂边 。
第 8章 图的基本概念定理 8.1.1（ 握手定理 ） 任一图中,顶点的度数的总和等于边数的二倍,即
( ) 2
V
dE
证明 因为在任一图中,每一条边均关联着两个顶点
（ 或二点重合 ）,所以在计算度数时要计算两次,故顶点的度数的总和等于边数的二倍 。
第 8章 图的基本概念推论 任一图中,奇度数顶点必有偶数个 。
证明 设 V1={v|d（ v） 为奇数 },V2=V-V1,则
12
( ) ( ) ( ) 2
V V V
d d d m
因为
2
()
V
d
是偶数，
()
V
d
也是偶数，
1
()
V
d
所以必是偶数 。 而 d（ v） 为奇数,故 |V1|是偶数 。
第 8章 图的基本概念定理 8.1.2 若 G=〈 V,E〉 是有向图,则
( ) ( )
VV
d d m
证明请读者自己完成。
第 8章 图的基本概念假设 V={v1,v2,…,vn}是 n阶图 G的顶点集，称 d
（ v1）,d（ v2）,…,d（ vn）为 G的度数列。如例 8.1.2
中图 8.１,1（ a）的度数列为 2,2,2,3,3。例 8.1.2中图
8.1.1（ c）的度数列为 1,2,2,3,3，其中出度数列为 0，
2,0,2,1，入度数列为 1,0,2,1,2。
第 8章 图的基本概念
【 例 8.1.3】 求解下列各题,
（ 1） 无向完全图 Kn有 28条边,则它的顶点数 n为多少？
（ 2） 图 G的度数列为 2,2,3,5,6,则边数 m为多少?
（ 3） 图 G有 12条边,度数为 3的顶点有 6个,余者度数均小于 3,问 G至少由几个顶点？
第 8章 图的基本概念解 （ 1）因为无向完全图 Kn的边数 m=1/2 n(n-1)=28，
所以 n=8。
（ 2）由握手定理 2m=∑d(v)=2+2+3+5+6=18，知
m=9。
（ 3） 由握手定理 ∑d(v)=2m=24,度数为 3的顶点有
6个占去 18度,还有 6度由其余顶点占有,而由题意,
其余顶点的度数可为 0,1,2,当均为 2时所用顶点数最少,所以应有 3个顶点占有此 6度,即 G中至少有 9个顶点 。
第 8章 图的基本概念
【 例 8.1.4】 证明在 n（ n≥2） 个人的团体中,总有两个人在此团体中恰好有相同个数的朋友 。
解 以顶点代表人,二人如果是朋友,则在代表他们的顶点间连上一条边,这样可得无向简单图 G,每个人的朋友数即图中代表它的顶点的度数,于是问题转化为,n阶无向简单图 G中必有两个顶点的度数相同 。
用反证法,设 G中各顶点的度数均不相同,则度数列为 0,1,2,…,n-1,说明图中有孤立顶点,这与有
n-1度顶点相矛盾 （ 因为是简单图 ）,所以必有两个顶点的度数相同 。
第 8章 图的基本概念
2.子图在深入研究图的性质及图的局部性质时,子图的概念是非常重要的 。 所谓子图,就是适当的去掉一些顶点或一些边后所形成的图,子图的顶点集和边集是原图的顶点集和边集的子集 。
定义 8.1.2 设 G=〈 V,E〉,G′=〈 V′,E′〉 均是图 （ 同为有向或无向 ） 。
第 8章 图的基本概念
（ 1）若 V′V,E′E，则称 G′是 G的子图，记作 G′G。
（ 2） 若 V′ V或 E′ E,则称 G′是 G的真子图,记作
G′ G。
（ 3） 若 V′=V,E′E,则称 G′是 G的生成子图 。
设 G1=〈 V1,E1〉 是 G的子图，若 V′V且 V′≠,E1由端点均在 V1中的所有边组成，则称 G1是由 V1导出的导出子图，记作 G［ V1］。若 E1 E且 E1≠,V1由 E1中边所关联的所有顶点组成，则称 G1是由 E1导出的导出子图，记作 G［ E1］。
第 8章 图的基本概念
【 例 8.1.5】 在图 8.1.2中,G1,G2,G3均是 G的真子图，其中 G1是 G的由 E1={e1,e2,e3,e4}导出的导出子图 G［ E1］； G2,G均是 G的生成子图； G3是 G的由
V3={a,d,e}导出的导出子图 G［ V3］，同时也是由
E3={e4,e5}导出的导出子图 G［ E3］。
第 8章 图的基本概念图 8.1.2
e
3
e
2
e
1
e
4
e
5
e
7e
6
a
b
d e
G
e
3
e
2
e
1
e
4
a
b
d
G
1
c
c
e
3
e
4
e
6
a
b
d e
G
2
c
e
4
e
5
a
d e
G
3
第 8章 图的基本概念
3.补图定义 8.1.3 G为 n阶简单图,由 G的所有顶点和能使
G成为完全图的添加边所构成的图称为 G的相对于完全图的补图,简称 G的补图,记作 。
【 例 8.1.6】 图 8.1.3中 是 G相对于 Kn的补图 。
对于补图,显然有以下结论：
G
G
第 8章 图的基本概念图 8.1.3
G G K
5
第 8章 图的基本概念
（ 1） G与 互为补图,即 =G。
（ 2） E（ G） ∪ E（ ） =E（完全图）且 E（ G） ∩E（ ）
= 。
（ 3） 完全图与 n阶零图互为补图 。
（ 4） G与 均是完全图的生成子图 。
G G
G G
G
第 8章 图的基本概念
4.同构由于在画图的图形时，顶点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是一个图。为了判断不同的图形是否反映同一个图形的性质，我们给出图的同构的概念。
第 8章 图的基本概念定义 8.1.4 设有两个图 G1=〈 V1,E1〉,G2=〈 V2，
E2〉,如果存在着双射 f,V1→ V2，使得（ vi,vj） ∈ E1
当且仅当（ f（ vi）,f（ vj）） ∈ E2（或者 〈 vi,vj〉
∈ E1当且仅当 〈 f（ vi）,f（ vj） 〉 ∈ E2）且它们的重数相同，则称图 G1与 G2同构，记作 G1 G2。
例如,图 8.1.4中 G1 G2,其中
f,V1→ V2,f（ vi） =ui（ i=1,2,…,6）。 G3 G4，其中 f,V1→ V2,f（ v1） =u3,f（ v2） =u1,f（ v3） =u2。
第 8章 图的基本概念图 8.1.4
G
1
G
2
G
3
G
4
u
1
u
3
u
5
u
2
u
4
u
6
u
1
u
2
u
3
1
2
3
4
5
6
1
2 3
第 8章 图的基本概念容易看出,两个同构的图必定满足：顶点数相同,
边数相同,度数列相同 。 但这是二图同构的必要条件而非充分条件,如图 8.1.5中的 （ a）,（ b） 均为 6阶 3-
正则图,满足上述三个条件,但因为对于图 （ a） 中的任一顶点,与该点关联的三个顶点间彼此不邻接,而对于图 （ b） 中的任一顶点,与该点关联的三个顶点中有两个是邻接点,所以它们不同构 。 同样可以看出图
（ c）,（ d） 也是不同构的 。
第 8章 图的基本概念图 8.1.5
( a ) ( b ) ( c ) ( d )
第 8章 图的基本概念在图的集合上定义二元关系 R：对于图 G1,G2，
G1RG2当且仅当 G1和 G2同构，称 R为图的同构关系，也记作。容易证明，图的同构关系是一种等价关系。按同构关系将图的集合划分成等价类，等价类的代表认为是一个非标定图，且可通过它所属的等价类中任一标定图来给出它的图形，但不必对顶点标以名称。
第 8章 图的基本概念
【 例 8.1.7】 画出 K4的所有非同构的生成子图 。
解 K4的所有非同构的生成子图如图 8.1.6所示 。
【 例 8.1.8】 设 G1,G2,G3,G4均是 4阶 3条边的无向简单图,则它们之间至少有几个是同构的？
解 由图 8.1.6知,4阶 3条边非同构的无向简单图共有 3个,因此 G1,G2,G3,G4中至少有 2个是同构的 。
第 8章 图的基本概念图 8.1.6
第 8章 图的基本概念
8.2 通路、回路、图的连通性定义 8.2.1 给定图 G=〈 V,E〉,图中的一条通路是一个点,边交替的序列,
v i1 e i1 v i2 e i2 …v ip-1 e ip-1 v ip
其中 v ik ∈ V,e ik ∈ E（其中 e ik =（ v ik,v ik+1）或者
e ik =〈 v ik,v ik+1 〉 ）,v i1,v ip分别称为通路的起点和终点，当其重合时通路称为回路。
第 8章 图的基本概念一条通路中所包含的边数称为此路的长度 。
由定义可知,一条通路即是 G的一个子图,且通路允许经过的顶点或边重复,因此根据不同要求通路可以作如下的划分：
简单通路 （ 迹 ） 顶点可重复但边不可重复的通路 。
初级通路 （ 路径 ） 顶点不可重复的通路 。
简单回路 （ 闭迹 ） 边不重复的回路 （ 顶点数大于等于 3） 。
初级回路（圈） 顶点不可重复（仅起点、终点重复）的回路。
第 8章 图的基本概念一般称长度为奇数的圈为奇圈,称长度为偶数的圈为偶圈 。 显然,初级通路必是简单通路,非简单通路称为复杂通路 。 在应用中,常常只用边的序列表示通路,对于简单图亦可用顶点序列表示通路,这样更方便 。
第 8章 图的基本概念定理 8.2.1 在一个 n阶图中，若从顶点 u到顶点 v
（ u≠v）存在通路，则必存在从 u到 v的初级通路且路长小于等于 n-1。
证明 设 L=ue1v1e2v2…epv是图中从 u到 v的通路,若其中顶点没有重复,则 L是一条初级通路 。 否则必有 t、
s（ 1≤t＜ s≤p-1）,使得 vt=vs,此时从 L中去掉从 vt到 vs之间的一段路后,所得仍为从 u到 v的通路,重复上述动作直到顶点无重复为止,所得通路即为由 u到 v的初级通路 。 因为长度为 k的初级通路上顶点数必为 k+1个,
所以 n阶图中的初级通路长度至多为 n-1。
推论 n阶图中,任何初级回路的长度不大于 n。
第 8章 图的基本概念
【 例 8.2.1】 一个人带着一只狼,一只羊和一捆草要渡河,由于船太小,人做摆渡者一次只能运送一个
,乘客,,很显然,如果人不在,狼要吃羊,羊要吃草,问人怎样才能把它们平安地渡过河去？
第 8章 图的基本概念解 这是通路问题的一个典型实例 。 用 f表示人,w
表示狼,s表示羊,h表示草 。
集合 {f,w,s,h}中能平安在一起的子集有,{f，
w,s,h},{f,w,s},{f,s,h},{f,w,h},{f,w}，
{f,s},{f,h},{w,h},{f},{w},{s},{h}。 用顶点表示渡河过程中的状态,状态是二元组：第一元素是集合 {f,w,s,h}在渡河过程中留在原岸的子集,
第二元素是在彼岸的子集,将一次渡河后代表状态变化的顶点间连边,得图 8.2.1。 容易看出,一条路径就是一种渡河方案 。
第 8章 图的基本概念图 8.2.1
<{ w },{ f,s,h }> < { f,w,s },{ h }>
<{ f,w,h },{ s }> <{ s },{ f,w,h }>
<{ h },{ f,w,s }> <{ f,s,h },{ w }>
<{ f,s },{ w,h }>
<{ },{ f,w,s,h }>
<{ w,h },{ f,s }>
<{ f,w,s,h },{ }>
第 8章 图的基本概念
【 例 8.2.2】 设 G是无向连通简单图,已知
δ（ G） ≥2,证明,G中存在长度大于等于 3的初级回路 。
证明 设 G中的一条长度最长的初级路是
L,v i1,v i2,v i3,…,v ip 。 所以 v i1 不再与路外的顶点邻接 （ 否则与 L最长矛盾 ）,因为 δ（ G） ≥2,所以 v
i1 必与路内的某点邻接,而 G是简单图,故 v i1 只能再邻接于 v ik （ k≥3）,因此,G中存在长度大于等于 3的初级回路 。
第 8章 图的基本概念
1.无向图的连通性定义 8.2.2 在无向图 G中,若顶点 u与 v之间存在通路,则称 u与 v是连通的,规定任何顶点自身是连通的 。
若 G是平凡图或 G中任二顶点均连通,则称 G是连通图,
否则称 G是非连通图或分离图 。
如果我们在 G的顶点集 V上定义一个二元关系 R：
R={〈 u,v〉 |u,v∈ V且 u与 v是连通的 }
第 8章 图的基本概念容易证明,R是自反的、对称的、传递的，即 R是一个等价关系，于是 R可将 V划分成若干个非空子集：
V1,V2,…,Vk，它们的导出子图 G［ V1］，
G［ V2］,…,G［ Vk］构成 G的连通分支，其连通分支的个数记作 P（ G）。显然,G是连通图，当且仅当 P
（ G） =1。
例如,图 8.2.2所示的图 G1是连通图,P（ G1） =1,图 G2
是一个非连通图,P（ G2） =3。
第 8章 图的基本概念图 8.2.2
G
1
G
2
第 8章 图的基本概念
【 例 8.2.3】 求证：若图中只有两个奇度数顶点,
则二顶点必连通 。
证明 用反证法来证明 。
设二顶点不连通,则它们必分属两个不同的连通分支,而对于每个连通分支,作为 G的子图只有一个奇度数顶点,余者均为偶度数顶点,与握手定理推论矛盾,因此,若图中只有两个奇度数顶点,则二顶点必连通 。
第 8章 图的基本概念
【 例 8.2.4】 在一次国际会议中,由七人组成的小组 {a,b,c,d,e,f,g}中,a会英语,阿拉伯语； b会英语,西班牙语； c会汉语,俄语； d会日语,西班牙语； e会德语,汉语和法语； f会日语,俄语； g会英语,法语和德语 。 问：他们中间任何二人是否均可对话 （ 必要时可通过别人翻译 ）？
第 8章 图的基本概念图 8.2.3
d
a b
f g
c
e
第 8章 图的基本概念解 用顶点代表人,如果二人会同一种语言,则在代表二人的顶点间连边,于是得到图 8.2.3。 问题归结为：在这个图中,任何两个顶点间是否都存在着通路？
由于图 8.2.3是一个连通图,因此,必要时通过别人翻译,他们中间任何二人均可对话 。
在连通图中,如果删去一些顶点或边,则可能会影响图的连通性 。 所谓从图中删去某个顶点 v,就是将顶点 v和与 v关联的所有的边均删去,我们用 G-v记之,
并用 G-V′表示从 G中删去 V的子集 V′。 用 G-e表示删去边
e,用 G-E′表示从 G中删去 E的子集 E′。
第 8章 图的基本概念例如,在例 8.2.3中,任何一人请假,图 G-v还连通,
小组对话仍可继续进行,但如果 f,g二人同时不在,
G-{f,g}是分离图,则小组中的对话无法再继续进行 。
定义 8.2.3 设无向图 G=〈 V,E〉,若存在顶点集 V′
V,使得 P（ G-V′） ＞ P（ G）,而对于任意的 V″ V，
均有 P（ G-E″） =P（ G） （ 即扩大图的连通分支数,E′
具有极小性 ）,则称是 G的一个点割集 。 如果 G的某个点割集中只有一个顶点,则称该点为割点 。
第 8章 图的基本概念定义 8.2.4 设无向图 G=〈 V,E〉,若存在边集
E′ E,使得 P（ G-E′） ＞ P（ G）,而对于任意的 V″
E,均有 P（ G-E″） =P（ G） （ 即扩大图的连通分支数,
E′具有极小性 ）,则称 E′是 G的一个边割集 。 如果 G的某个边割集中只有一条边,则称该边为割边或桥 。
第 8章 图的基本概念例如在图 8.2.3中,{f,g},{d,g},{a,c,d}，
{b,e}等等均是点割集； {(c,f),(e,g)},{(d,f),(e,g)}
等等均是边割集,并且在图 8.2.3中,不存在割点和桥 。
由定义容易得到下面结论：
（ 1） n阶零图既无点割集也无边割集 。
（ 2） 完全图 Kn无点割集 。
（ 3） 若 G是连通图,则 P（ G-V′） ≥2。
（ 4） 若 G是连通图,则 P（ G-E′） =2。
第 8章 图的基本概念一个连通图 G,若存在点割集和边割集,一般并不唯一,且各个点 （ 边 ） 割集中所含的点 （ 边 ） 的个数也不尽相同 。 我们用含元素个数最少的点割集和边割集来刻画它的连通度 。
第 8章 图的基本概念定义 8.2.5 设 G是一无向连通图,称 (（ G） 为 G的点连通度,
κ（ G） =min{|V′||V′
是 G的点割集或 V′使 G-V′成平凡图 ｝
称 λ（ G） 为 G的边连通度,
λ（ G） =min{|E′||E′是 G的边割集 }
第 8章 图的基本概念由定义容易得到下面结论：
（ 1） 若 G是平凡图,则 V′=E′=,
κ（ G） =λ（ G） =0。
（ 2） 若 G是非连通图,κ（ G） =λ（ G） =0。
（ 3） 对于无向完全图 Kn,κ（ Kn） =n-1。
（ 4） 若 G中有割点,则 κ（ G） =1。
（ 5） 若 G中有桥,则 λ（ G） =κ（ G） =1。
第 8章 图的基本概念
【 例 8.2.5】 图 8.2.4中的两个连通图都是 n=8，
e=16，其中,κ（ G1） =4,λ(G1） =4,κ（ G2） =1,λ
（ G2） =3。假设 n个顶点代表 n个站,e条边表示铁路或者桥梁或者电话线,e≥n-1。为了使 n个站之间的连接不容易被破坏，必须构造一个具有 n个顶点 e条边的连通图，并使其具有最大的点连通度和边连通度。按图
8.2.4中 G1的连接法，如果 3个站被破坏，或者 3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。但按图 8.2.4中 G2的连接法，如果 (站被破坏，
余下的站就不能保持连通。
第 8章 图的基本概念图 8.2.4
G
1
G
2
第 8章 图的基本概念关于点连通度,边连通度与最小顶点度数有如下一个不等式 。
定理 8.2.2 对于任何一个图 G，
κ（ G） ≤λ（ G） ≤λ（ G） 。
证明 若 G是非连通图或是平凡图,则必有
κ（ G） =λ（ G） =0≤δ(G） 。
若 G是完全图 Kn,则
κ（ G） =λ（ G） =δ（ G） =n-1。
对于其他情况,首先证明 λ（ G） ≤δ（ G） 。
第 8章 图的基本概念因为图中存在顶点 v,d（ v） =δ（ G），删去 (的所有关联边，得到的图必定不连通，所以，至多删去 δ
（ G）条边即可破坏 G的连通性，故必有 λ（ G） ≤δ
（ G）。下面再证明 κ（ G） ≤δ（ G）。
第 8章 图的基本概念当在 G中删去构成割集的 λ（ G）条边时，将产生 G
的两个子图 G1,G2，而这 λ（ G）条边的两个端点显然分别在 G1和 G2中，在 G1（或 G2）中这 λ（ G）条边至多关联着 λ（ G）个顶点，删去这些顶点同样可使 G不连通，故必有 κ（ G） ≤λ（ G）。
第 8章 图的基本概念例如，图 8.2.5中的 κ（ G） =2,λ（ G） =3，
δ（ G） =4。
定义 8.2.6 若图 G的 κ（ G） ≥k，则称 G是 k-连通的。
例如图 8.2.5的点连通度是 2，所以它是 2-连通的，也是
1-连通的，但不是 3-连通的。非平凡的连通图均是 1-连通的。非连通图是 0-连通的。
第 8章 图的基本概念定义 8.2.7 若图 G的 λ（ G） ≥k,则称 G是 k― 边连通的 。
例如图 8.2.5的边连通度是 3,所以它是 3― 边连通的,也是 2― 边连通的和 1-边连通的,但不是 4― 边连通的 。 非连通图是 0― 边连通的 。 由定理 8.1.1易知：若
G是 k― 连通图,则 G必是 k― 边连通图 。
第 8章 图的基本概念图 8.2.5
第 8章 图的基本概念
2.有向图的连通性定义 8.2.8 设 G=〈 V,E〉 是一有向图,u,v∈ V，
若从 u到 v存在通路,则称 u可达 v,规定 u到自身总是可达的；
若 u可达 v,同时 v可达 u,则称 u与 v相互可达 。 若 u
可达 v,其长度最短的通路称 u到 v的短程线,短程线的长度称 u到 v的距离,记作 d〈 u,v〉 。
第 8章 图的基本概念有向图中顶点间的可达关系是自反的,传递的,
但不一定是对称的,所以不是等价关系 。 通常
d〈 u,v〉 ≥0（ 其中 d〈 u,v〉 =0）
d〈 u,v〉 +d〈 v,w〉 ≥d〈 u,w〉
如果从 u到 v不可达,记 d〈 u,v〉 =∞。
注意,即使 u与 v是相互可达的,也可能
d〈 u,v〉 ≠d〈 v,u〉 。
第 8章 图的基本概念定义 8.2.9 在简单有向图 G中,若任二顶点间均相互可达,则称 G为强连通图；若任二顶点间至少从一个顶点到另一个顶点是可达的,则称 G是单向连通图；若在忽略 G中各边的方向时 G是无向连通图,则称 G是弱连通图 。
例如在图 8.2.6中,图 （ a） 是强连通图,图 （ b）
是单向连通图,图 （ c） 是弱连通图 。
第 8章 图的基本概念图 8.2.6
( a ) ( b ) ( c )
第 8章 图的基本概念定理 8.2.3 有向图 G是强连通的,当且仅当 G中有一条包含每个顶点至少一次的回路 。
证明 设 G中有一回路,它至少包含每个顶点一次,
则在此路上 G的任意两个顶点都是相互可达的,G是强连通图 。 反之,若 G是强连通图,则任意两个顶点是相互可达的,因此必可作一条回路经过 G中所有各个顶点 。
否则会出现一回路不包含某个顶点 v,这样 v就与回路上的顶点不是相互可达的,与假设 G是强连通图矛盾 。
第 8章 图的基本概念定理 8.2.4 有向图 G是单向连通的,当且仅当 G中有一条包含每个顶点至少一次的通路 。 证明略 。
定义 8.2.10 在简单有向图 G中,具有极大强连通性的子图,称为 G的一个强分图；具有极大单向连通性的子图,称为 G的一个单向分图；具有极大弱连通性的子图,称为 G的一个弱分图 。 强分图的定义中,极大,的含义是：对该子图再加入其他顶点,它便不再具有强连通性 。 对单向分图,弱分图也类似 。
第 8章 图的基本概念图 8.2.7
3
4 5 6
1 2
第 8章 图的基本概念
【 例 8.2.6】 求图 8.2.7中 G的所有强分图,单向分图和弱分图 。
解 V1={v1,v3,v4},V2={v2,v6},V3={v3}的导出子图 G［ V1］,G［ V2］,G［ V3］ 均是 G的强分图 （ 见图 8.2.8（ a） G1,G2,G3） ； V4={v1,v2,v3,v4,v6}、
V5={v2,v3,v6}的导出子图
G［ V4］,G［ V5］ 均是 G的单向分图 （ 见图 8.2.8（ b）
G4,G5） ； G是弱连通的,故 G的弱分图就是 G自身 。
第 8章 图的基本概念图 8.2.8
G
1
G
2
G
3
G
4
G
5
( a ) ( b )
1 2 3
4 5 6
1 2 32
654 6
第 8章 图的基本概念定理 8.2.5 有向图 G=〈 V,E〉 中,每个顶点在且仅在一个强分图中 。
证明 在顶点集 V中定义一个二元关系 R：
R={〈 u,v〉 |u与 v同在一个强分图中 }
显然,R是自反的,对称的,传递的,即 R是一个等价关系 。 因此构成 V的划分,由于 V的每个划分块构成的导出子图是一强分图,所以每个顶点在且仅在一个强分图中 。
第 8章 图的基本概念在计算机系统中,如果我们用顶点来表示资源,
若有一程序 p1占有资源 s1,而对资源 s2提出申请,则用从 s1引向 s2的有向边表示,并标定边 〈 s1,s2〉 为 p1,那么任一瞬间计算机资源的状态图,就是由顶点集 {s1，
s2,…,sn}和边集 {p1,p2,…,pm}构成的有向图 G,图
G的强分图反映一种死锁现象 。 最简单的死锁现象如：
程序 p1占有 s1对 s2提出申请； p2占有 s2对 s3提出申请；而
p3占有 s3对 s1提出申请 （ 如图 8.２,8的 G1）,结果只能是,你等我,我等你,,互相等待,这就是死锁现象 。
这是操作系统要避免出现的事件 。
第 8章 图的基本概念
8.3 图的矩阵表示
1.有向图的邻接矩阵定义 8.3.1 设 G=〈 V,E〉 是一有向图，
V={a1,a2,…,an}，构造一矩阵 A （ G）：
( 1 )( ) ( )i j n nA G a
其中 a (1) ij 是顶点 vi邻接到顶点 vj的条数,称 A
（ G） 为图 G的邻接矩阵 。
第 8章 图的基本概念图 8.3.1
2 3
4
1
第 8章 图的基本概念
【 例 8.3.1】 求图 G（ 如图 8.3.1所示 ） 的邻接矩阵 。
解
1 2 0 0
0 0 1 0
()
1 0 0 1
0 0 1 0
AG
给出了图 G的邻接矩阵,就等于给出了图 G的全部信息 。 图的性质可以由矩阵 A通过运算而获得 。
第 8章 图的基本概念有向图的邻接矩阵有如下性质：
(1)
1
( 1 ) ( ),1,2,,,
n
ij i
j
a d i n
于是
(1)
1 1 1
()
n n n
i j i
i i i
a a m
(1)
1
( 2 ) ( ),1,2,,,
n
i j i
j
a d i n
于是
1
2 ( 1,2,,)
n
ij
i
m j m
第 8章 图的基本概念
（ 3）由（ 1）、（ 2）不难看出,A （ G）中所有元素的和为 G中长度为 1的通路个数，而 为 G
中长度为 1的回路（环）的个数。
（ 4）令 A2=A× A= （ a (2) ij ） n× n,其中则 a (2) ij 表示从顶点 vi两步到达顶点 vj的通路条数,而
a (2) ii 表示从顶点 vi两步回到顶点 vi的回路数目。利用数学归纳法可得 (5)。
(1)
1
n
ij
i
a
( 2 ) ( 1 ) ( 1 )
1
n
ij ik k j
k
a a a
第 8章 图的基本概念
（ 5）若令 As=A× A=(a (s) ij ) n× n,则 a (s) ij 表示从顶点 vi到顶点 vj长度为 s的通路条数，而 a (s) ii 表示从顶点
vi回到顶点 vi的长度为 s的回路数目。于是有 (6)。
（ 6） 表示 G中长度为 s的通路总数,其中表示 G中长度为 s的回路总数 。 进一步可得 (7)。
（ 7） 若令 B=A+A2+…+As=（ b ij ） n× n,则 b ij 表示从顶点 vi到顶点 vj长度小于或等于 s的通路总数 。
()
11
nn
s
ij
ji
a
()
1
n
s
ii
i
a
第 8章 图的基本概念
【 例 8.3.2】 对于图 8.3.1，因为
2
34
1 2 0 0 1 2 0 0 1 2 2 0
0 0 1 0 0 0 1 0 1 0 0 1
1 0 0 1 1 0 0 1 1 2 1 0
0 0 1 0 0 0 1 0 1 0 0 1
3 2 2 2 5 6 4 2
1 2 1 0 2 2 2 1
2 2 2 1 4 4 3 2
1 2 1 0 2 2 2 1
A
AA
第 8章 图的基本概念所以，由 v1到 v3长度为 1,2,3,4的通路分别有 0、
2,2,4条,G中共有长度为 4的通路 43条，其中回路 11
条，长度小于等于 4的通路共有 87条，其中回路 22条。
注 无向图也有相应的邻接矩阵,一般只考虑简单图,无向图的邻接矩阵是对称的,其性质基本与有向图邻接矩阵的性质相同 。
第 8章 图的基本概念
2.有向图的可达矩阵定义 8.3.2 设 G=〈 V,E〉 是一有向图,
V={v1,v2,…,vn},令
1
0ij
p
vi可达 vj
否则称 （ p ij ） n× n 为 G的可达矩阵,记作 P （ G） 。
第 8章 图的基本概念例如,记图 8.3.1的可达矩阵为 P （ G），则
1111
1111
()
1111
1111
PG
第 8章 图的基本概念可达矩阵具有如下性质：
（ 1） p ii =1 （ 因为规定任何顶点自身可达 ） 。
（ 2） 所有元素均为 1的可达矩阵对应强连通图 。 如果经过初等行列变换后,P （ G） 可变形为
1
2
()
()
()
l
PG
PG
PG
第 8章 图的基本概念主对角线上的分块矩阵 P （ Gi） （ i=1,2,…,l）
元素均为 1,则每个 Gi是 G的一个强分图 。
（ 3） 根据定理 8.2.1及推论可知,可达矩阵可通过计算邻接矩阵得到,令
B=E+A+A2+…+A n-1 =(b ij ) n× n
其中 E 是单位矩阵 。 则
10
00
ij
ij
ij
b
p
b
第 8章 图的基本概念
3.无向图的关联矩阵定义 8.3.3 设无向图 G=〈 V,E〉,
V={v1,v2,…,vn},E={e1,e2,…,em},令
0
1
2
ijm
若 vi与 ej不关联若 vi是 ej的一个端点若 ej是关联 vi的一个环则称（ m ij ） n× m 为 G的关联矩阵，记作 M （ G）。
第 8章 图的基本概念
【 例 8.3.3】 求图 G（ 如图 8.3.2所示 ） 的关联矩阵 。
1
2
3
4
2 1 0 0 0
0 1 1 1 0
()
0 0 1 1 1
0 0 0 0 1
MG
1 2 3 4 5e e e e e
第 8章 图的基本概念图 8.3.2
e
1
e
2
e
3
e
4
e
5
1
2
3
4
第 8章 图的基本概念无向图的关联矩阵的特性是很明显的：
（ 1）,即 M （ G）每列元素之和为 2，因为每条边恰有两个端点（若是简单图则每列恰有两个 1）。
（ 2）,因而全为 0的行所对应的顶点是孤立顶点。
1
2 ( 1,2,,)
n
ij
i
m j m
1
()
n
ij i
i
md?
第 8章 图的基本概念
（ 3）若图 G有连通分支 G1,G2,…,Gs，那么存在
G的关联矩阵 M （ G）形如
1
2
( ) 0 0
0 ( ) 0
()
0 0 ( )
s
MG
MG
MG
MG
其中 M （ G1）,M （ G2）,…,M （ Gs） 分别是
G1,G2,…,Gs的关联矩阵,0是零矩阵 。 对于连通简单图的关联矩阵还有下面重要事实 。
第 8章 图的基本概念定理 8.3.1 若 G为（ n,m）连通简单图，则 M （ G）
的秩为 n-1（即其最大非零行列式的值为 n-1）。
我们只给出直观解释：令
1
2
()
n
M
M
MG
M
第 8章 图的基本概念其中 M1,M2,…,M n为行向量 。 由于 M中各列中恰有两个 1,因此
M1+M2+…+M n=（ 2,2,…,2）
适当更换上式中的,+”为,-”,便可使其代数和为
（ 0,0,…,0）
这说明向量 M1,M2,…,M n是线性相关的,因而
M的秩不超过 n-1。
第 8章 图的基本概念另一方面,由于 G连通,所以 M （ G） 的每一行均不全为 0,也不能表成分块矩阵
1
2
( ) 0
0 ( )
MG
MG
否则 G为具有连通分支 G1,G2的非连通图,因此
M （ G） 中任意 k（ k≤n-1） 行向量之代数和 （ m1,m2,…，
mm） 中至少有一个元素为 1,因而是线性无关的 。 这表明
M （ G） 的秩至少为 n-1。
第 8章 图的基本概念综上所述,无向连通简单图的关联矩阵 M （ G）
的秩为 n-1。
推论 （ n,m） 图 G为有 k个连通分支的简单图,当且仅当 M （ G） 的秩为 n-k。
第 8章 图的基本概念
4.有向无环图的关联矩阵定义 8.3.4 设 G=〈 V,E〉 是有向无环图，
V={v1,v2,…,vn},E={e1,e2,…,em}，令
1
0
1
ij
m
vi是 ej的起点
vi与 ej不关联
vi是 ej的终点则称（ m ij ） n× n 为 G的关联矩阵，记作 M （ G）。
第 8章 图的基本概念
【 例 8.3.4】 求图 G（ 如图 8.3.3所示 ） 的关联矩阵 。
1
2
3
4
5
1 0 0 0 0 0
1 1 1 1 0 0
() 0 1 1 0 1 1
0 0 0 1 1 1
000000
MG
1 2 3 4 5 6e e e e e e
第 8章 图的基本概念图 8.3.3
e
5
e
6
e
3
e
2
e
1
e
4 5
3
41
2
第 8章 图的基本概念
M （ G）的特性：
（ 1） （一条边关联两个点：一个起点，
一个终点），从而有 。
（ 2） 每一行中 1的数目是该点的出度,-1的数目是该点的入度 。
（ 3） 二列相同,当且仅当对应的边是平行边 （ 同向 ） 。
（ 4） 全为 0的行对应孤立顶点 。
1
0
n
ij
i
m
11
0
mn
ij
ji
m
第 8章 图的基本概念
8.4 例 题 选 解
【 例 8.4.1】 判断下列各命题是否是真命题 。
（ 1） n阶无向完全图 Kn是 n-正则图 。
（ 2） 任何有相同顶点数和边数的无向图都同构 。
（ 3） 图中的初级回路均是简单回路 。
（ 4） 在有向图中顶点间的可达关系是等价关系 。
（ 5） 任一图 G的最大度数 Δ（ G） 必小于 G的顶点数 。
（ 6） 在 n（ n≥2） 个人中,不认识另外奇数个人的有偶数个人 。
第 8章 图的基本概念解答与分析
（ 1） 假命题 。 由无向完全图的定义可知,Kn的每个顶点的度数均是 n-1,所以 Kn是 n-1-正则图 。
（ 2） 假命题 。 两个图有相同顶点数和边数是二图同构的必要条件,而非充分条件 。
（ 3） 真命题 。 由初级回路和简单回路的定义可知 。
（ 4） 假命题 。 可达关系不满足对称性 。
（ 5） 假命题 。 当 G非简单图时,Δ（ G） 可大于顶点数 。
第 8章 图的基本概念
（ 6）真命题。将 n个人抽象成 n个顶点，若两个人不认识，则在他们的对应顶点之间画一条边，得到无向图 G。 G中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数，由握手定理的推论可知,G中奇度数的顶点必有偶数个。故在 n个人中，不认识另外奇数个人的有偶数个人。
第 8章 图的基本概念
【 例 8.4.2】 在六个人的团体中,至少有三个人彼此认识或彼此不认识 。
分析 将六个人抽象成六个顶点,若两个人认识,
则在他们的对应顶点之间画一条边,得到无向图 G,则
G是 6阶无向简单图,中的边则表示他们关联的两个顶点代表的人彼此不认识,本题即：证明 G或它的补图 中存在 3个顶点彼此邻接 。
G
G
第 8章 图的基本概念图 8.4.1
b
c
a
第 8章 图的基本概念解 因为 K6是 5- v∈ V（ G）（ v∈
（ ））,d（ v）在 G中或在 中大于等于 3。不妨设在 G中 d（ v） ≥3，则 v在 G中至少关联三个顶点设为 a、
b,c（见图 8.4.1），若此三顶点在 G中彼此不邻接，则必有三边（ a,b）、（ a,c）、（ b,c）均在 中
（图中虚线），亦即 a,b,c三点在 中彼此邻接，
否则三顶点至少有两个在 G中邻接，不妨设（ a,b）
∈ E（ G），则 v,a,b为在 G中彼此邻接的三顶点，故在 G或 中存在 3个顶点彼此邻接。G
G
GG
G
第 8章 图的基本概念
【 例 8.4.3】 证明无向图 G与其补图 至少有一个是连通图 。
分析 是 G的补图,即 G∪ 是一个无向完全图 。 对 G
中任一边 e,若 e∈ E（ G）,则 e E（ ） ；反之若
e∈ E（ ）,则 e E（ G） 。 又 G与 有相同的顶点集,故只需考虑 G中的任意二顶点 。 若 G是连通图,则命题已成立,所以不妨设 G不是连通图 。
G
G
G
G
第 8章 图的基本概念解 假设 G不是连通图，则 G至少有两个连通分支，
不妨设为 G1,G2。对于 G中的任意二顶点 u,v，设
u∈ G1，此时若 v∈ G2，则必有边（ u,v） ∈,所以
u,v在 中连通。此时若 v G2，即 v∈ G1,则必存在顶点 w∈ G2，使得（ u,w） ∈ 且（ v,w） ∈,所以 u,v仍在 中连通。故 是连通图。所以,G与其补图 至少有一个是连通图。
G
G
G G
GG
G
第 8章 图的基本概念习 题 八
1,顶点度数列为 1,1,2,3,3的无向简单图有几个？
2,证明,1,3,3,4,5,6,6不是简单图的度数列 。
3,设图 G有 n个顶点,n+1条边,证明 G中至少有一个顶点的度数大于等于 3。
4,在简单图中若顶点数大于等于 2,则至少有两个顶点的度数相同 。
5,证明定理 8.1.2。
第 8章 图的基本概念图 8.1
( c )
( d )( b )( a )
第 8章 图的基本概念
6,G是 n阶无向简单图,n＞ 2为奇数,则 G与 G所含的奇度数顶点数相等 。
7,证明图 8.1中,图 （ a） 与 （ b） 同构,图 （ c）
与 （ d） 不同构 。
8,画出 4阶无向完全图 K4的所有非同构的子图,
并指出哪些是生成子图和生成子图的互补情况 。
9,画出 3阶有向完全图的所有非同构的生成子图,
指出每个图的补图和生成子图的互补情况 。
第 8章 图的基本概念
10,如果一个图 G同构于自己的补图 G,则称该图为自补图 。
（ 1） 有几个非同构的 4阶和 5阶的自补图？
（ 2） 是否有 3阶和 6阶的自补图？
11,G是 n（ n≥3） 阶连通图,G没有桥,当且仅当对 G的每一对顶点和每一条边,有一条连接这两个顶点而不含这条边的通路 。
12,一个连通无向图 G中的顶点 (是割点的充分必要条件是存在两个顶点 u和 w,使得顶点 u和 w之间的每一条路都通过 v。
第 8章 图的基本概念
13,试求图 8.2中有向图的所有强分图,单分图和弱分图 。
14,图 8.2中有向图所对应的二元关系是否是可传递的？ 若不是,试求此图的传递闭包 。
第 8章 图的基本概念图 8.2
1 2
4 5 6 7
3
第 8章 图的基本概念
15,证明：图的每一个顶点和每一条边都只包含在一个弱分图中 。
16,有向图 G如图 8.3所示,计算 G的邻接矩阵的前
4次幂,回答下列问题 。
（ 1） G中 v1到 v4的长度为 4的通路有几条？
（ 2） G中 v1到 v1的长度为 4的回路有几条？
第 8章 图的基本概念
（ 3） G中长度为 4的通路总数是多少？ 其中有多少条是回路？
（ 4） G中长度小于等于 4的通路有几条？ 其中有多少条是回路？
（ 5） 写出 G的可达矩阵 。
第 8章 图的基本概念图 8.3
1
2
4
3
8.1 图的定义及相关术语
8.2 通路回路图的连通性
8.3 图的矩阵表示
8.4 例题选解习 题 八第 8章 图的基本概念
8.1 图的定义及相关术语
1.图图论作为数学的分支给出了图的严格的数学定义,
为此我们首先给出无序积的概念 。
A,B是任意两个非空集合,A与 B的无序积记为
A&B,即
A&B={（ a,b） |a∈ A,b∈ B}
性质,（ a,b） =（ b,a）
第 8章 图的基本概念
【 例 8.1.1】 A={a,b,c},B={1,2}，求 A&B、
B&A和 B&B。
解 A&B={（ a,1）,（ a,2）,（ b,1）,
（ b,2）,（ c,1）,（ c,3） }=B&A
B&B={（ 1,1）,（ 1,2）,（ 2,2） }
第 8章 图的基本概念定义 8.1.1 图是一个二元组 G=〈 V,E〉,其中 V
（ V≠ ） 是顶点集,E是边集 。 当 E是无序积 V&V的多重子集时,其元素为无向边,图 G为无向图 。 当 E是有序积 V× V的多重子集时,其元素为有向边,图 G为有向图 。
所谓多重子集是指集中元素可以重复 。
第 8章 图的基本概念
【 例 8.1.2】 图 8.1.1中 （ a）,（ b） 是无向图,图
（ c） 是有向图 。
图 8.1.1（ b） 的 v1,v2,v3,v4,v5,这样的图称为标定图 。 同时也可对边进行标定,这里 e1=（ v1,v2）,
e2=（ v1,v4）,e3=（ v1,v5）,e4=（ v2,v5）,
e5=（ v2,v5）,e6=（ v4,v5） 。 当 ei=（ vj,vk） 时,称
vj和 vk是 ei的端点,并称 ei与 vj和 vk相关联,当 ei=〈 vj,vk〉
是有向边时,又称 vj是 ei的起点,vk是 ei的终点 。 如果图的顶点集 V和边集 E均是有穷集,则称图为有限图,本书所讨论的均是有限图 。
第 8章 图的基本概念图 8.1.1
( a )
( b ) ( c )
e
1
e
2
e
3
e
4
e
5
e
6
1 2
4 3
5
第 8章 图的基本概念下面介绍一些图的基本概念和常用术语 。
邻接点 同一条边的两个端点 。
孤立顶点 没有边与之关联的顶点 。
零图 顶点集 V非空但边集 E为空集的图 。
平凡图 |V|=1,|E|=m=0的图 。
邻接边 关联同一个顶点的两条边 。
环 关联同一个顶点的一条边 （（ v,v） 或 〈 v,v〉 ） 。
第 8章 图的基本概念平行边 关联一对顶点的 m条边 （ m≥2,称重数,若是有向边则应方向相同 ） 。
多重图 含有平行边 （ 无环 ） 的图 。
简单图 不含平行边和环的图 。
完全图 每对顶点间均有边相连的无向简单图 。 n阶完全图记作 Kn。
竞赛图 在 Kn的每条边上任取一个方向的有向图 。
有向完全图 每对顶点间均有一对方向相反的边相连的有向图 。
第 8章 图的基本概念由完全图的定义易知，无向完全图 Kn的边数为
2 1( ) ( 1 )
2nnE K C n n
有向完全图 G的边数为
( ) ( 1 )E G n n
第 8章 图的基本概念顶点的度数 顶点所关联的边数。顶点 v的度数记作 d（ v）。在有向图中，以顶点 v为起点的边数称顶点
v的出度，记作 d+（ v） ;以顶点 v为终点的边数称顶点 v
的入度，记作 d-（ v）。
第 8章 图的基本概念图 G的最大度 Δ(G） =max{d（ v） |v∈ V（ G)}
图 G的最小度 δ（ G） =min{d（ v） |v∈ V（ G） }
有向图 G的最大出度 Δ+（ G） =max{d+（ v） |v∈ V（ G） }
有向图 G的最小出度 δ+（ G） =min{d+（ v） |v∈ V（ G） }
有向图 G的最大入度 Δ-（ G） =max{d-（ v） |v∈ V（ G） }
有向图 G的最小入度 δ-（ G） =min{d-（ v） |v∈ V（ G） }
k-正则图 每个顶点的度数均是 k的无向图 。
另外,我们称度数为 1的顶点为悬挂点,称与悬挂点关联的边为悬挂边 。
第 8章 图的基本概念定理 8.1.1（ 握手定理 ） 任一图中,顶点的度数的总和等于边数的二倍,即
( ) 2
V
dE
证明 因为在任一图中,每一条边均关联着两个顶点
（ 或二点重合 ）,所以在计算度数时要计算两次,故顶点的度数的总和等于边数的二倍 。
第 8章 图的基本概念推论 任一图中,奇度数顶点必有偶数个 。
证明 设 V1={v|d（ v） 为奇数 },V2=V-V1,则
12
( ) ( ) ( ) 2
V V V
d d d m
因为
2
()
V
d
是偶数，
()
V
d
也是偶数，
1
()
V
d
所以必是偶数 。 而 d（ v） 为奇数,故 |V1|是偶数 。
第 8章 图的基本概念定理 8.1.2 若 G=〈 V,E〉 是有向图,则
( ) ( )
VV
d d m
证明请读者自己完成。
第 8章 图的基本概念假设 V={v1,v2,…,vn}是 n阶图 G的顶点集，称 d
（ v1）,d（ v2）,…,d（ vn）为 G的度数列。如例 8.1.2
中图 8.１,1（ a）的度数列为 2,2,2,3,3。例 8.1.2中图
8.1.1（ c）的度数列为 1,2,2,3,3，其中出度数列为 0，
2,0,2,1，入度数列为 1,0,2,1,2。
第 8章 图的基本概念
【 例 8.1.3】 求解下列各题,
（ 1） 无向完全图 Kn有 28条边,则它的顶点数 n为多少？
（ 2） 图 G的度数列为 2,2,3,5,6,则边数 m为多少?
（ 3） 图 G有 12条边,度数为 3的顶点有 6个,余者度数均小于 3,问 G至少由几个顶点？
第 8章 图的基本概念解 （ 1）因为无向完全图 Kn的边数 m=1/2 n(n-1)=28，
所以 n=8。
（ 2）由握手定理 2m=∑d(v)=2+2+3+5+6=18，知
m=9。
（ 3） 由握手定理 ∑d(v)=2m=24,度数为 3的顶点有
6个占去 18度,还有 6度由其余顶点占有,而由题意,
其余顶点的度数可为 0,1,2,当均为 2时所用顶点数最少,所以应有 3个顶点占有此 6度,即 G中至少有 9个顶点 。
第 8章 图的基本概念
【 例 8.1.4】 证明在 n（ n≥2） 个人的团体中,总有两个人在此团体中恰好有相同个数的朋友 。
解 以顶点代表人,二人如果是朋友,则在代表他们的顶点间连上一条边,这样可得无向简单图 G,每个人的朋友数即图中代表它的顶点的度数,于是问题转化为,n阶无向简单图 G中必有两个顶点的度数相同 。
用反证法,设 G中各顶点的度数均不相同,则度数列为 0,1,2,…,n-1,说明图中有孤立顶点,这与有
n-1度顶点相矛盾 （ 因为是简单图 ）,所以必有两个顶点的度数相同 。
第 8章 图的基本概念
2.子图在深入研究图的性质及图的局部性质时,子图的概念是非常重要的 。 所谓子图,就是适当的去掉一些顶点或一些边后所形成的图,子图的顶点集和边集是原图的顶点集和边集的子集 。
定义 8.1.2 设 G=〈 V,E〉,G′=〈 V′,E′〉 均是图 （ 同为有向或无向 ） 。
第 8章 图的基本概念
（ 1）若 V′V,E′E，则称 G′是 G的子图，记作 G′G。
（ 2） 若 V′ V或 E′ E,则称 G′是 G的真子图,记作
G′ G。
（ 3） 若 V′=V,E′E,则称 G′是 G的生成子图 。
设 G1=〈 V1,E1〉 是 G的子图，若 V′V且 V′≠,E1由端点均在 V1中的所有边组成，则称 G1是由 V1导出的导出子图，记作 G［ V1］。若 E1 E且 E1≠,V1由 E1中边所关联的所有顶点组成，则称 G1是由 E1导出的导出子图，记作 G［ E1］。
第 8章 图的基本概念
【 例 8.1.5】 在图 8.1.2中,G1,G2,G3均是 G的真子图，其中 G1是 G的由 E1={e1,e2,e3,e4}导出的导出子图 G［ E1］； G2,G均是 G的生成子图； G3是 G的由
V3={a,d,e}导出的导出子图 G［ V3］，同时也是由
E3={e4,e5}导出的导出子图 G［ E3］。
第 8章 图的基本概念图 8.1.2
e
3
e
2
e
1
e
4
e
5
e
7e
6
a
b
d e
G
e
3
e
2
e
1
e
4
a
b
d
G
1
c
c
e
3
e
4
e
6
a
b
d e
G
2
c
e
4
e
5
a
d e
G
3
第 8章 图的基本概念
3.补图定义 8.1.3 G为 n阶简单图,由 G的所有顶点和能使
G成为完全图的添加边所构成的图称为 G的相对于完全图的补图,简称 G的补图,记作 。
【 例 8.1.6】 图 8.1.3中 是 G相对于 Kn的补图 。
对于补图,显然有以下结论：
G
G
第 8章 图的基本概念图 8.1.3
G G K
5
第 8章 图的基本概念
（ 1） G与 互为补图,即 =G。
（ 2） E（ G） ∪ E（ ） =E（完全图）且 E（ G） ∩E（ ）
= 。
（ 3） 完全图与 n阶零图互为补图 。
（ 4） G与 均是完全图的生成子图 。
G G
G G
G
第 8章 图的基本概念
4.同构由于在画图的图形时，顶点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是一个图。为了判断不同的图形是否反映同一个图形的性质，我们给出图的同构的概念。
第 8章 图的基本概念定义 8.1.4 设有两个图 G1=〈 V1,E1〉,G2=〈 V2，
E2〉,如果存在着双射 f,V1→ V2，使得（ vi,vj） ∈ E1
当且仅当（ f（ vi）,f（ vj）） ∈ E2（或者 〈 vi,vj〉
∈ E1当且仅当 〈 f（ vi）,f（ vj） 〉 ∈ E2）且它们的重数相同，则称图 G1与 G2同构，记作 G1 G2。
例如,图 8.1.4中 G1 G2,其中
f,V1→ V2,f（ vi） =ui（ i=1,2,…,6）。 G3 G4，其中 f,V1→ V2,f（ v1） =u3,f（ v2） =u1,f（ v3） =u2。
第 8章 图的基本概念图 8.1.4
G
1
G
2
G
3
G
4
u
1
u
3
u
5
u
2
u
4
u
6
u
1
u
2
u
3
1
2
3
4
5
6
1
2 3
第 8章 图的基本概念容易看出,两个同构的图必定满足：顶点数相同,
边数相同,度数列相同 。 但这是二图同构的必要条件而非充分条件,如图 8.1.5中的 （ a）,（ b） 均为 6阶 3-
正则图,满足上述三个条件,但因为对于图 （ a） 中的任一顶点,与该点关联的三个顶点间彼此不邻接,而对于图 （ b） 中的任一顶点,与该点关联的三个顶点中有两个是邻接点,所以它们不同构 。 同样可以看出图
（ c）,（ d） 也是不同构的 。
第 8章 图的基本概念图 8.1.5
( a ) ( b ) ( c ) ( d )
第 8章 图的基本概念在图的集合上定义二元关系 R：对于图 G1,G2，
G1RG2当且仅当 G1和 G2同构，称 R为图的同构关系，也记作。容易证明，图的同构关系是一种等价关系。按同构关系将图的集合划分成等价类，等价类的代表认为是一个非标定图，且可通过它所属的等价类中任一标定图来给出它的图形，但不必对顶点标以名称。
第 8章 图的基本概念
【 例 8.1.7】 画出 K4的所有非同构的生成子图 。
解 K4的所有非同构的生成子图如图 8.1.6所示 。
【 例 8.1.8】 设 G1,G2,G3,G4均是 4阶 3条边的无向简单图,则它们之间至少有几个是同构的？
解 由图 8.1.6知,4阶 3条边非同构的无向简单图共有 3个,因此 G1,G2,G3,G4中至少有 2个是同构的 。
第 8章 图的基本概念图 8.1.6
第 8章 图的基本概念
8.2 通路、回路、图的连通性定义 8.2.1 给定图 G=〈 V,E〉,图中的一条通路是一个点,边交替的序列,
v i1 e i1 v i2 e i2 …v ip-1 e ip-1 v ip
其中 v ik ∈ V,e ik ∈ E（其中 e ik =（ v ik,v ik+1）或者
e ik =〈 v ik,v ik+1 〉 ）,v i1,v ip分别称为通路的起点和终点，当其重合时通路称为回路。
第 8章 图的基本概念一条通路中所包含的边数称为此路的长度 。
由定义可知,一条通路即是 G的一个子图,且通路允许经过的顶点或边重复,因此根据不同要求通路可以作如下的划分：
简单通路 （ 迹 ） 顶点可重复但边不可重复的通路 。
初级通路 （ 路径 ） 顶点不可重复的通路 。
简单回路 （ 闭迹 ） 边不重复的回路 （ 顶点数大于等于 3） 。
初级回路（圈） 顶点不可重复（仅起点、终点重复）的回路。
第 8章 图的基本概念一般称长度为奇数的圈为奇圈,称长度为偶数的圈为偶圈 。 显然,初级通路必是简单通路,非简单通路称为复杂通路 。 在应用中,常常只用边的序列表示通路,对于简单图亦可用顶点序列表示通路,这样更方便 。
第 8章 图的基本概念定理 8.2.1 在一个 n阶图中，若从顶点 u到顶点 v
（ u≠v）存在通路，则必存在从 u到 v的初级通路且路长小于等于 n-1。
证明 设 L=ue1v1e2v2…epv是图中从 u到 v的通路,若其中顶点没有重复,则 L是一条初级通路 。 否则必有 t、
s（ 1≤t＜ s≤p-1）,使得 vt=vs,此时从 L中去掉从 vt到 vs之间的一段路后,所得仍为从 u到 v的通路,重复上述动作直到顶点无重复为止,所得通路即为由 u到 v的初级通路 。 因为长度为 k的初级通路上顶点数必为 k+1个,
所以 n阶图中的初级通路长度至多为 n-1。
推论 n阶图中,任何初级回路的长度不大于 n。
第 8章 图的基本概念
【 例 8.2.1】 一个人带着一只狼,一只羊和一捆草要渡河,由于船太小,人做摆渡者一次只能运送一个
,乘客,,很显然,如果人不在,狼要吃羊,羊要吃草,问人怎样才能把它们平安地渡过河去？
第 8章 图的基本概念解 这是通路问题的一个典型实例 。 用 f表示人,w
表示狼,s表示羊,h表示草 。
集合 {f,w,s,h}中能平安在一起的子集有,{f，
w,s,h},{f,w,s},{f,s,h},{f,w,h},{f,w}，
{f,s},{f,h},{w,h},{f},{w},{s},{h}。 用顶点表示渡河过程中的状态,状态是二元组：第一元素是集合 {f,w,s,h}在渡河过程中留在原岸的子集,
第二元素是在彼岸的子集,将一次渡河后代表状态变化的顶点间连边,得图 8.2.1。 容易看出,一条路径就是一种渡河方案 。
第 8章 图的基本概念图 8.2.1
<{ w },{ f,s,h }> < { f,w,s },{ h }>
<{ f,w,h },{ s }> <{ s },{ f,w,h }>
<{ h },{ f,w,s }> <{ f,s,h },{ w }>
<{ f,s },{ w,h }>
<{ },{ f,w,s,h }>
<{ w,h },{ f,s }>
<{ f,w,s,h },{ }>
第 8章 图的基本概念
【 例 8.2.2】 设 G是无向连通简单图,已知
δ（ G） ≥2,证明,G中存在长度大于等于 3的初级回路 。
证明 设 G中的一条长度最长的初级路是
L,v i1,v i2,v i3,…,v ip 。 所以 v i1 不再与路外的顶点邻接 （ 否则与 L最长矛盾 ）,因为 δ（ G） ≥2,所以 v
i1 必与路内的某点邻接,而 G是简单图,故 v i1 只能再邻接于 v ik （ k≥3）,因此,G中存在长度大于等于 3的初级回路 。
第 8章 图的基本概念
1.无向图的连通性定义 8.2.2 在无向图 G中,若顶点 u与 v之间存在通路,则称 u与 v是连通的,规定任何顶点自身是连通的 。
若 G是平凡图或 G中任二顶点均连通,则称 G是连通图,
否则称 G是非连通图或分离图 。
如果我们在 G的顶点集 V上定义一个二元关系 R：
R={〈 u,v〉 |u,v∈ V且 u与 v是连通的 }
第 8章 图的基本概念容易证明,R是自反的、对称的、传递的，即 R是一个等价关系，于是 R可将 V划分成若干个非空子集：
V1,V2,…,Vk，它们的导出子图 G［ V1］，
G［ V2］,…,G［ Vk］构成 G的连通分支，其连通分支的个数记作 P（ G）。显然,G是连通图，当且仅当 P
（ G） =1。
例如,图 8.2.2所示的图 G1是连通图,P（ G1） =1,图 G2
是一个非连通图,P（ G2） =3。
第 8章 图的基本概念图 8.2.2
G
1
G
2
第 8章 图的基本概念
【 例 8.2.3】 求证：若图中只有两个奇度数顶点,
则二顶点必连通 。
证明 用反证法来证明 。
设二顶点不连通,则它们必分属两个不同的连通分支,而对于每个连通分支,作为 G的子图只有一个奇度数顶点,余者均为偶度数顶点,与握手定理推论矛盾,因此,若图中只有两个奇度数顶点,则二顶点必连通 。
第 8章 图的基本概念
【 例 8.2.4】 在一次国际会议中,由七人组成的小组 {a,b,c,d,e,f,g}中,a会英语,阿拉伯语； b会英语,西班牙语； c会汉语,俄语； d会日语,西班牙语； e会德语,汉语和法语； f会日语,俄语； g会英语,法语和德语 。 问：他们中间任何二人是否均可对话 （ 必要时可通过别人翻译 ）？
第 8章 图的基本概念图 8.2.3
d
a b
f g
c
e
第 8章 图的基本概念解 用顶点代表人,如果二人会同一种语言,则在代表二人的顶点间连边,于是得到图 8.2.3。 问题归结为：在这个图中,任何两个顶点间是否都存在着通路？
由于图 8.2.3是一个连通图,因此,必要时通过别人翻译,他们中间任何二人均可对话 。
在连通图中,如果删去一些顶点或边,则可能会影响图的连通性 。 所谓从图中删去某个顶点 v,就是将顶点 v和与 v关联的所有的边均删去,我们用 G-v记之,
并用 G-V′表示从 G中删去 V的子集 V′。 用 G-e表示删去边
e,用 G-E′表示从 G中删去 E的子集 E′。
第 8章 图的基本概念例如,在例 8.2.3中,任何一人请假,图 G-v还连通,
小组对话仍可继续进行,但如果 f,g二人同时不在,
G-{f,g}是分离图,则小组中的对话无法再继续进行 。
定义 8.2.3 设无向图 G=〈 V,E〉,若存在顶点集 V′
V,使得 P（ G-V′） ＞ P（ G）,而对于任意的 V″ V，
均有 P（ G-E″） =P（ G） （ 即扩大图的连通分支数,E′
具有极小性 ）,则称是 G的一个点割集 。 如果 G的某个点割集中只有一个顶点,则称该点为割点 。
第 8章 图的基本概念定义 8.2.4 设无向图 G=〈 V,E〉,若存在边集
E′ E,使得 P（ G-E′） ＞ P（ G）,而对于任意的 V″
E,均有 P（ G-E″） =P（ G） （ 即扩大图的连通分支数,
E′具有极小性 ）,则称 E′是 G的一个边割集 。 如果 G的某个边割集中只有一条边,则称该边为割边或桥 。
第 8章 图的基本概念例如在图 8.2.3中,{f,g},{d,g},{a,c,d}，
{b,e}等等均是点割集； {(c,f),(e,g)},{(d,f),(e,g)}
等等均是边割集,并且在图 8.2.3中,不存在割点和桥 。
由定义容易得到下面结论：
（ 1） n阶零图既无点割集也无边割集 。
（ 2） 完全图 Kn无点割集 。
（ 3） 若 G是连通图,则 P（ G-V′） ≥2。
（ 4） 若 G是连通图,则 P（ G-E′） =2。
第 8章 图的基本概念一个连通图 G,若存在点割集和边割集,一般并不唯一,且各个点 （ 边 ） 割集中所含的点 （ 边 ） 的个数也不尽相同 。 我们用含元素个数最少的点割集和边割集来刻画它的连通度 。
第 8章 图的基本概念定义 8.2.5 设 G是一无向连通图,称 (（ G） 为 G的点连通度,
κ（ G） =min{|V′||V′
是 G的点割集或 V′使 G-V′成平凡图 ｝
称 λ（ G） 为 G的边连通度,
λ（ G） =min{|E′||E′是 G的边割集 }
第 8章 图的基本概念由定义容易得到下面结论：
（ 1） 若 G是平凡图,则 V′=E′=,
κ（ G） =λ（ G） =0。
（ 2） 若 G是非连通图,κ（ G） =λ（ G） =0。
（ 3） 对于无向完全图 Kn,κ（ Kn） =n-1。
（ 4） 若 G中有割点,则 κ（ G） =1。
（ 5） 若 G中有桥,则 λ（ G） =κ（ G） =1。
第 8章 图的基本概念
【 例 8.2.5】 图 8.2.4中的两个连通图都是 n=8，
e=16，其中,κ（ G1） =4,λ(G1） =4,κ（ G2） =1,λ
（ G2） =3。假设 n个顶点代表 n个站,e条边表示铁路或者桥梁或者电话线,e≥n-1。为了使 n个站之间的连接不容易被破坏，必须构造一个具有 n个顶点 e条边的连通图，并使其具有最大的点连通度和边连通度。按图
8.2.4中 G1的连接法，如果 3个站被破坏，或者 3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。但按图 8.2.4中 G2的连接法，如果 (站被破坏，
余下的站就不能保持连通。
第 8章 图的基本概念图 8.2.4
G
1
G
2
第 8章 图的基本概念关于点连通度,边连通度与最小顶点度数有如下一个不等式 。
定理 8.2.2 对于任何一个图 G，
κ（ G） ≤λ（ G） ≤λ（ G） 。
证明 若 G是非连通图或是平凡图,则必有
κ（ G） =λ（ G） =0≤δ(G） 。
若 G是完全图 Kn,则
κ（ G） =λ（ G） =δ（ G） =n-1。
对于其他情况,首先证明 λ（ G） ≤δ（ G） 。
第 8章 图的基本概念因为图中存在顶点 v,d（ v） =δ（ G），删去 (的所有关联边，得到的图必定不连通，所以，至多删去 δ
（ G）条边即可破坏 G的连通性，故必有 λ（ G） ≤δ
（ G）。下面再证明 κ（ G） ≤δ（ G）。
第 8章 图的基本概念当在 G中删去构成割集的 λ（ G）条边时，将产生 G
的两个子图 G1,G2，而这 λ（ G）条边的两个端点显然分别在 G1和 G2中，在 G1（或 G2）中这 λ（ G）条边至多关联着 λ（ G）个顶点，删去这些顶点同样可使 G不连通，故必有 κ（ G） ≤λ（ G）。
第 8章 图的基本概念例如，图 8.2.5中的 κ（ G） =2,λ（ G） =3，
δ（ G） =4。
定义 8.2.6 若图 G的 κ（ G） ≥k，则称 G是 k-连通的。
例如图 8.2.5的点连通度是 2，所以它是 2-连通的，也是
1-连通的，但不是 3-连通的。非平凡的连通图均是 1-连通的。非连通图是 0-连通的。
第 8章 图的基本概念定义 8.2.7 若图 G的 λ（ G） ≥k,则称 G是 k― 边连通的 。
例如图 8.2.5的边连通度是 3,所以它是 3― 边连通的,也是 2― 边连通的和 1-边连通的,但不是 4― 边连通的 。 非连通图是 0― 边连通的 。 由定理 8.1.1易知：若
G是 k― 连通图,则 G必是 k― 边连通图 。
第 8章 图的基本概念图 8.2.5
第 8章 图的基本概念
2.有向图的连通性定义 8.2.8 设 G=〈 V,E〉 是一有向图,u,v∈ V，
若从 u到 v存在通路,则称 u可达 v,规定 u到自身总是可达的；
若 u可达 v,同时 v可达 u,则称 u与 v相互可达 。 若 u
可达 v,其长度最短的通路称 u到 v的短程线,短程线的长度称 u到 v的距离,记作 d〈 u,v〉 。
第 8章 图的基本概念有向图中顶点间的可达关系是自反的,传递的,
但不一定是对称的,所以不是等价关系 。 通常
d〈 u,v〉 ≥0（ 其中 d〈 u,v〉 =0）
d〈 u,v〉 +d〈 v,w〉 ≥d〈 u,w〉
如果从 u到 v不可达,记 d〈 u,v〉 =∞。
注意,即使 u与 v是相互可达的,也可能
d〈 u,v〉 ≠d〈 v,u〉 。
第 8章 图的基本概念定义 8.2.9 在简单有向图 G中,若任二顶点间均相互可达,则称 G为强连通图；若任二顶点间至少从一个顶点到另一个顶点是可达的,则称 G是单向连通图；若在忽略 G中各边的方向时 G是无向连通图,则称 G是弱连通图 。
例如在图 8.2.6中,图 （ a） 是强连通图,图 （ b）
是单向连通图,图 （ c） 是弱连通图 。
第 8章 图的基本概念图 8.2.6
( a ) ( b ) ( c )
第 8章 图的基本概念定理 8.2.3 有向图 G是强连通的,当且仅当 G中有一条包含每个顶点至少一次的回路 。
证明 设 G中有一回路,它至少包含每个顶点一次,
则在此路上 G的任意两个顶点都是相互可达的,G是强连通图 。 反之,若 G是强连通图,则任意两个顶点是相互可达的,因此必可作一条回路经过 G中所有各个顶点 。
否则会出现一回路不包含某个顶点 v,这样 v就与回路上的顶点不是相互可达的,与假设 G是强连通图矛盾 。
第 8章 图的基本概念定理 8.2.4 有向图 G是单向连通的,当且仅当 G中有一条包含每个顶点至少一次的通路 。 证明略 。
定义 8.2.10 在简单有向图 G中,具有极大强连通性的子图,称为 G的一个强分图；具有极大单向连通性的子图,称为 G的一个单向分图；具有极大弱连通性的子图,称为 G的一个弱分图 。 强分图的定义中,极大,的含义是：对该子图再加入其他顶点,它便不再具有强连通性 。 对单向分图,弱分图也类似 。
第 8章 图的基本概念图 8.2.7
3
4 5 6
1 2
第 8章 图的基本概念
【 例 8.2.6】 求图 8.2.7中 G的所有强分图,单向分图和弱分图 。
解 V1={v1,v3,v4},V2={v2,v6},V3={v3}的导出子图 G［ V1］,G［ V2］,G［ V3］ 均是 G的强分图 （ 见图 8.2.8（ a） G1,G2,G3） ； V4={v1,v2,v3,v4,v6}、
V5={v2,v3,v6}的导出子图
G［ V4］,G［ V5］ 均是 G的单向分图 （ 见图 8.2.8（ b）
G4,G5） ； G是弱连通的,故 G的弱分图就是 G自身 。
第 8章 图的基本概念图 8.2.8
G
1
G
2
G
3
G
4
G
5
( a ) ( b )
1 2 3
4 5 6
1 2 32
654 6
第 8章 图的基本概念定理 8.2.5 有向图 G=〈 V,E〉 中,每个顶点在且仅在一个强分图中 。
证明 在顶点集 V中定义一个二元关系 R：
R={〈 u,v〉 |u与 v同在一个强分图中 }
显然,R是自反的,对称的,传递的,即 R是一个等价关系 。 因此构成 V的划分,由于 V的每个划分块构成的导出子图是一强分图,所以每个顶点在且仅在一个强分图中 。
第 8章 图的基本概念在计算机系统中,如果我们用顶点来表示资源,
若有一程序 p1占有资源 s1,而对资源 s2提出申请,则用从 s1引向 s2的有向边表示,并标定边 〈 s1,s2〉 为 p1,那么任一瞬间计算机资源的状态图,就是由顶点集 {s1，
s2,…,sn}和边集 {p1,p2,…,pm}构成的有向图 G,图
G的强分图反映一种死锁现象 。 最简单的死锁现象如：
程序 p1占有 s1对 s2提出申请； p2占有 s2对 s3提出申请；而
p3占有 s3对 s1提出申请 （ 如图 8.２,8的 G1）,结果只能是,你等我,我等你,,互相等待,这就是死锁现象 。
这是操作系统要避免出现的事件 。
第 8章 图的基本概念
8.3 图的矩阵表示
1.有向图的邻接矩阵定义 8.3.1 设 G=〈 V,E〉 是一有向图，
V={a1,a2,…,an}，构造一矩阵 A （ G）：
( 1 )( ) ( )i j n nA G a
其中 a (1) ij 是顶点 vi邻接到顶点 vj的条数,称 A
（ G） 为图 G的邻接矩阵 。
第 8章 图的基本概念图 8.3.1
2 3
4
1
第 8章 图的基本概念
【 例 8.3.1】 求图 G（ 如图 8.3.1所示 ） 的邻接矩阵 。
解
1 2 0 0
0 0 1 0
()
1 0 0 1
0 0 1 0
AG
给出了图 G的邻接矩阵,就等于给出了图 G的全部信息 。 图的性质可以由矩阵 A通过运算而获得 。
第 8章 图的基本概念有向图的邻接矩阵有如下性质：
(1)
1
( 1 ) ( ),1,2,,,
n
ij i
j
a d i n
于是
(1)
1 1 1
()
n n n
i j i
i i i
a a m
(1)
1
( 2 ) ( ),1,2,,,
n
i j i
j
a d i n
于是
1
2 ( 1,2,,)
n
ij
i
m j m
第 8章 图的基本概念
（ 3）由（ 1）、（ 2）不难看出,A （ G）中所有元素的和为 G中长度为 1的通路个数，而 为 G
中长度为 1的回路（环）的个数。
（ 4）令 A2=A× A= （ a (2) ij ） n× n,其中则 a (2) ij 表示从顶点 vi两步到达顶点 vj的通路条数,而
a (2) ii 表示从顶点 vi两步回到顶点 vi的回路数目。利用数学归纳法可得 (5)。
(1)
1
n
ij
i
a
( 2 ) ( 1 ) ( 1 )
1
n
ij ik k j
k
a a a
第 8章 图的基本概念
（ 5）若令 As=A× A=(a (s) ij ) n× n,则 a (s) ij 表示从顶点 vi到顶点 vj长度为 s的通路条数，而 a (s) ii 表示从顶点
vi回到顶点 vi的长度为 s的回路数目。于是有 (6)。
（ 6） 表示 G中长度为 s的通路总数,其中表示 G中长度为 s的回路总数 。 进一步可得 (7)。
（ 7） 若令 B=A+A2+…+As=（ b ij ） n× n,则 b ij 表示从顶点 vi到顶点 vj长度小于或等于 s的通路总数 。
()
11
nn
s
ij
ji
a
()
1
n
s
ii
i
a
第 8章 图的基本概念
【 例 8.3.2】 对于图 8.3.1，因为
2
34
1 2 0 0 1 2 0 0 1 2 2 0
0 0 1 0 0 0 1 0 1 0 0 1
1 0 0 1 1 0 0 1 1 2 1 0
0 0 1 0 0 0 1 0 1 0 0 1
3 2 2 2 5 6 4 2
1 2 1 0 2 2 2 1
2 2 2 1 4 4 3 2
1 2 1 0 2 2 2 1
A
AA
第 8章 图的基本概念所以，由 v1到 v3长度为 1,2,3,4的通路分别有 0、
2,2,4条,G中共有长度为 4的通路 43条，其中回路 11
条，长度小于等于 4的通路共有 87条，其中回路 22条。
注 无向图也有相应的邻接矩阵,一般只考虑简单图,无向图的邻接矩阵是对称的,其性质基本与有向图邻接矩阵的性质相同 。
第 8章 图的基本概念
2.有向图的可达矩阵定义 8.3.2 设 G=〈 V,E〉 是一有向图,
V={v1,v2,…,vn},令
1
0ij
p
vi可达 vj
否则称 （ p ij ） n× n 为 G的可达矩阵,记作 P （ G） 。
第 8章 图的基本概念例如,记图 8.3.1的可达矩阵为 P （ G），则
1111
1111
()
1111
1111
PG
第 8章 图的基本概念可达矩阵具有如下性质：
（ 1） p ii =1 （ 因为规定任何顶点自身可达 ） 。
（ 2） 所有元素均为 1的可达矩阵对应强连通图 。 如果经过初等行列变换后,P （ G） 可变形为
1
2
()
()
()
l
PG
PG
PG
第 8章 图的基本概念主对角线上的分块矩阵 P （ Gi） （ i=1,2,…,l）
元素均为 1,则每个 Gi是 G的一个强分图 。
（ 3） 根据定理 8.2.1及推论可知,可达矩阵可通过计算邻接矩阵得到,令
B=E+A+A2+…+A n-1 =(b ij ) n× n
其中 E 是单位矩阵 。 则
10
00
ij
ij
ij
b
p
b
第 8章 图的基本概念
3.无向图的关联矩阵定义 8.3.3 设无向图 G=〈 V,E〉,
V={v1,v2,…,vn},E={e1,e2,…,em},令
0
1
2
ijm
若 vi与 ej不关联若 vi是 ej的一个端点若 ej是关联 vi的一个环则称（ m ij ） n× m 为 G的关联矩阵，记作 M （ G）。
第 8章 图的基本概念
【 例 8.3.3】 求图 G（ 如图 8.3.2所示 ） 的关联矩阵 。
1
2
3
4
2 1 0 0 0
0 1 1 1 0
()
0 0 1 1 1
0 0 0 0 1
MG
1 2 3 4 5e e e e e
第 8章 图的基本概念图 8.3.2
e
1
e
2
e
3
e
4
e
5
1
2
3
4
第 8章 图的基本概念无向图的关联矩阵的特性是很明显的：
（ 1）,即 M （ G）每列元素之和为 2，因为每条边恰有两个端点（若是简单图则每列恰有两个 1）。
（ 2）,因而全为 0的行所对应的顶点是孤立顶点。
1
2 ( 1,2,,)
n
ij
i
m j m
1
()
n
ij i
i
md?
第 8章 图的基本概念
（ 3）若图 G有连通分支 G1,G2,…,Gs，那么存在
G的关联矩阵 M （ G）形如
1
2
( ) 0 0
0 ( ) 0
()
0 0 ( )
s
MG
MG
MG
MG
其中 M （ G1）,M （ G2）,…,M （ Gs） 分别是
G1,G2,…,Gs的关联矩阵,0是零矩阵 。 对于连通简单图的关联矩阵还有下面重要事实 。
第 8章 图的基本概念定理 8.3.1 若 G为（ n,m）连通简单图，则 M （ G）
的秩为 n-1（即其最大非零行列式的值为 n-1）。
我们只给出直观解释：令
1
2
()
n
M
M
MG
M
第 8章 图的基本概念其中 M1,M2,…,M n为行向量 。 由于 M中各列中恰有两个 1,因此
M1+M2+…+M n=（ 2,2,…,2）
适当更换上式中的,+”为,-”,便可使其代数和为
（ 0,0,…,0）
这说明向量 M1,M2,…,M n是线性相关的,因而
M的秩不超过 n-1。
第 8章 图的基本概念另一方面,由于 G连通,所以 M （ G） 的每一行均不全为 0,也不能表成分块矩阵
1
2
( ) 0
0 ( )
MG
MG
否则 G为具有连通分支 G1,G2的非连通图,因此
M （ G） 中任意 k（ k≤n-1） 行向量之代数和 （ m1,m2,…，
mm） 中至少有一个元素为 1,因而是线性无关的 。 这表明
M （ G） 的秩至少为 n-1。
第 8章 图的基本概念综上所述,无向连通简单图的关联矩阵 M （ G）
的秩为 n-1。
推论 （ n,m） 图 G为有 k个连通分支的简单图,当且仅当 M （ G） 的秩为 n-k。
第 8章 图的基本概念
4.有向无环图的关联矩阵定义 8.3.4 设 G=〈 V,E〉 是有向无环图，
V={v1,v2,…,vn},E={e1,e2,…,em}，令
1
0
1
ij
m
vi是 ej的起点
vi与 ej不关联
vi是 ej的终点则称（ m ij ） n× n 为 G的关联矩阵，记作 M （ G）。
第 8章 图的基本概念
【 例 8.3.4】 求图 G（ 如图 8.3.3所示 ） 的关联矩阵 。
1
2
3
4
5
1 0 0 0 0 0
1 1 1 1 0 0
() 0 1 1 0 1 1
0 0 0 1 1 1
000000
MG
1 2 3 4 5 6e e e e e e
第 8章 图的基本概念图 8.3.3
e
5
e
6
e
3
e
2
e
1
e
4 5
3
41
2
第 8章 图的基本概念
M （ G）的特性：
（ 1） （一条边关联两个点：一个起点，
一个终点），从而有 。
（ 2） 每一行中 1的数目是该点的出度,-1的数目是该点的入度 。
（ 3） 二列相同,当且仅当对应的边是平行边 （ 同向 ） 。
（ 4） 全为 0的行对应孤立顶点 。
1
0
n
ij
i
m
11
0
mn
ij
ji
m
第 8章 图的基本概念
8.4 例 题 选 解
【 例 8.4.1】 判断下列各命题是否是真命题 。
（ 1） n阶无向完全图 Kn是 n-正则图 。
（ 2） 任何有相同顶点数和边数的无向图都同构 。
（ 3） 图中的初级回路均是简单回路 。
（ 4） 在有向图中顶点间的可达关系是等价关系 。
（ 5） 任一图 G的最大度数 Δ（ G） 必小于 G的顶点数 。
（ 6） 在 n（ n≥2） 个人中,不认识另外奇数个人的有偶数个人 。
第 8章 图的基本概念解答与分析
（ 1） 假命题 。 由无向完全图的定义可知,Kn的每个顶点的度数均是 n-1,所以 Kn是 n-1-正则图 。
（ 2） 假命题 。 两个图有相同顶点数和边数是二图同构的必要条件,而非充分条件 。
（ 3） 真命题 。 由初级回路和简单回路的定义可知 。
（ 4） 假命题 。 可达关系不满足对称性 。
（ 5） 假命题 。 当 G非简单图时,Δ（ G） 可大于顶点数 。
第 8章 图的基本概念
（ 6）真命题。将 n个人抽象成 n个顶点，若两个人不认识，则在他们的对应顶点之间画一条边，得到无向图 G。 G中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数，由握手定理的推论可知,G中奇度数的顶点必有偶数个。故在 n个人中，不认识另外奇数个人的有偶数个人。
第 8章 图的基本概念
【 例 8.4.2】 在六个人的团体中,至少有三个人彼此认识或彼此不认识 。
分析 将六个人抽象成六个顶点,若两个人认识,
则在他们的对应顶点之间画一条边,得到无向图 G,则
G是 6阶无向简单图,中的边则表示他们关联的两个顶点代表的人彼此不认识,本题即：证明 G或它的补图 中存在 3个顶点彼此邻接 。
G
G
第 8章 图的基本概念图 8.4.1
b
c
a
第 8章 图的基本概念解 因为 K6是 5- v∈ V（ G）（ v∈
（ ））,d（ v）在 G中或在 中大于等于 3。不妨设在 G中 d（ v） ≥3，则 v在 G中至少关联三个顶点设为 a、
b,c（见图 8.4.1），若此三顶点在 G中彼此不邻接，则必有三边（ a,b）、（ a,c）、（ b,c）均在 中
（图中虚线），亦即 a,b,c三点在 中彼此邻接，
否则三顶点至少有两个在 G中邻接，不妨设（ a,b）
∈ E（ G），则 v,a,b为在 G中彼此邻接的三顶点，故在 G或 中存在 3个顶点彼此邻接。G
G
GG
G
第 8章 图的基本概念
【 例 8.4.3】 证明无向图 G与其补图 至少有一个是连通图 。
分析 是 G的补图,即 G∪ 是一个无向完全图 。 对 G
中任一边 e,若 e∈ E（ G）,则 e E（ ） ；反之若
e∈ E（ ）,则 e E（ G） 。 又 G与 有相同的顶点集,故只需考虑 G中的任意二顶点 。 若 G是连通图,则命题已成立,所以不妨设 G不是连通图 。
G
G
G
G
第 8章 图的基本概念解 假设 G不是连通图，则 G至少有两个连通分支，
不妨设为 G1,G2。对于 G中的任意二顶点 u,v，设
u∈ G1，此时若 v∈ G2，则必有边（ u,v） ∈,所以
u,v在 中连通。此时若 v G2，即 v∈ G1,则必存在顶点 w∈ G2，使得（ u,w） ∈ 且（ v,w） ∈,所以 u,v仍在 中连通。故 是连通图。所以,G与其补图 至少有一个是连通图。
G
G
G G
GG
G
第 8章 图的基本概念习 题 八
1,顶点度数列为 1,1,2,3,3的无向简单图有几个？
2,证明,1,3,3,4,5,6,6不是简单图的度数列 。
3,设图 G有 n个顶点,n+1条边,证明 G中至少有一个顶点的度数大于等于 3。
4,在简单图中若顶点数大于等于 2,则至少有两个顶点的度数相同 。
5,证明定理 8.1.2。
第 8章 图的基本概念图 8.1
( c )
( d )( b )( a )
第 8章 图的基本概念
6,G是 n阶无向简单图,n＞ 2为奇数,则 G与 G所含的奇度数顶点数相等 。
7,证明图 8.1中,图 （ a） 与 （ b） 同构,图 （ c）
与 （ d） 不同构 。
8,画出 4阶无向完全图 K4的所有非同构的子图,
并指出哪些是生成子图和生成子图的互补情况 。
9,画出 3阶有向完全图的所有非同构的生成子图,
指出每个图的补图和生成子图的互补情况 。
第 8章 图的基本概念
10,如果一个图 G同构于自己的补图 G,则称该图为自补图 。
（ 1） 有几个非同构的 4阶和 5阶的自补图？
（ 2） 是否有 3阶和 6阶的自补图？
11,G是 n（ n≥3） 阶连通图,G没有桥,当且仅当对 G的每一对顶点和每一条边,有一条连接这两个顶点而不含这条边的通路 。
12,一个连通无向图 G中的顶点 (是割点的充分必要条件是存在两个顶点 u和 w,使得顶点 u和 w之间的每一条路都通过 v。
第 8章 图的基本概念
13,试求图 8.2中有向图的所有强分图,单分图和弱分图 。
14,图 8.2中有向图所对应的二元关系是否是可传递的？ 若不是,试求此图的传递闭包 。
第 8章 图的基本概念图 8.2
1 2
4 5 6 7
3
第 8章 图的基本概念
15,证明：图的每一个顶点和每一条边都只包含在一个弱分图中 。
16,有向图 G如图 8.3所示,计算 G的邻接矩阵的前
4次幂,回答下列问题 。
（ 1） G中 v1到 v4的长度为 4的通路有几条？
（ 2） G中 v1到 v1的长度为 4的回路有几条？
第 8章 图的基本概念
（ 3） G中长度为 4的通路总数是多少？ 其中有多少条是回路？
（ 4） G中长度小于等于 4的通路有几条？ 其中有多少条是回路？
（ 5） 写出 G的可达矩阵 。
第 8章 图的基本概念图 8.3
1
2
4
3
