教材：《离散数学》第2版 屈婉玲 耿素云 张立昂 高等教育出版社
源文档高清截图在最后

未完待续

14.3 图的连通性

1、设无向图G(V, E)，若u，v∈V之间存在通路，就称u，v是连通的，记作u ~ v。规定：对任意v∈V，v ~ v。如果无向图G是平凡图（只含一个顶点的图）或者G中任意两个顶点都是连通的，则G为连通图，否则为非连通图。无向图中，顶点之间的连通关系 ~ 是等价关系：具有自反性、对称性、传递性。

2、设无向图G(V, E)，Vi是V关于顶点连通关系 ~ 的一个等价类，称导出子图G[Vi]为G的一个连通分支（连通分量）。简单来说，一个图被分成几个小块，每个小块是连通的，但小块之间不联通，这些小块称为连通分支。一个孤立点也是一个联通分支。G的连通分支数记作p(G)。若G为连通图，p(G) = 1；否则，p(G) > 1。所有的n阶无向图中，n阶零图（不含任何边）是连通分支最多的，数量达到p(Nn) = n。

3、设无向图G的任意两个顶点u ~ v，u、v之间长度最短的通路称为u、v之间的短程线，短程线的长度称作u、v的距离，记作d(u, v)（和顶点v的度数d(v)要区分开）。当u、v不连通时，d(u, v) = ∞。
距离具有以下性质：任意u，v，w∈G，
（1）d(u, v)≥0，仅u = v时等号成立。
（2）对称性：d(u, v) = d(v, u)。
（3）满足三角不等式d(u, v) + d(v, w)≥d(u, w)。

4、设无向图G(V, E)。若存在使p(G－V’) > p(G)，且对任意的均有p(G－V’’) = p(G)，则称V’是G的点割集。若V’ = {v}，称v为割点。若存在使p(G－E’) > p(G)，且对任意的均有p(G－E’’) = p(G)，则称V’是G的点割集，简称割集。若E’ = {e}，称e为割边或桥。去掉点割集中的点和连接的边后，原来的连通图会变成非连通图；如果图已经是非连通的，就会分裂成更多的互相不连通的子图。对边割集也可以类似理解。

5、设无向连通非完全图G，记κ(G) = min(|V’| | V’为G的点割集)为G的点连通度，简称连通度。κ(G)可以简记为κ。点连通度就是所含元素最少的点割集的元素数量。完全图Kn的点连通度为n－1，因为必须去掉n－1个顶点后才能令原完全图不再是连通图，此时这个图也不再剩下任何边。非连通图的点连通度为0。因为无论去掉哪些点都无法再使原图变成更多的不连通的子图。若κ(G)≥k，就称G为k-连通图。k为非负整数。若κ(G1)≥κ(G2)，就说G1比G2的点连通程度高。

6、设无向连通非完全图G，记λ(G) = min(|E’| | E’为G的边割集)为G的边连通度。λ(G)可以简记为λ。非连通图的边连通度为0。若λ(G)≥r，则称G是r边-连通图。由定义，若G是r边-连通图，则从G中任意删除r－1条边后，G仍然是连通的。完全图Kn的边连通度为n－1。若λ(G1)≥λ(G2)，就说G1比G2的边连通程度高。

7、设有向图D(V, E)，对任意vi，vj∈V，若从vi到vj存在通路，则称vi可达vj，记作vi→vj。规定：vi→vi。若vi→vj且vj→vi，就称vi和vi是相互可达的，记作vi↔vj。规定：vi↔vi。

8、设有向图D(V, E)，对任意vi，vj∈V，若vi→vj，则称vi到vj长度最短的通路为vi到vj的短程线。短程线的长度是vi到vj的距离，记作d<vi, vj>。与无向图中的d(vi, vj)相比，除了无对称性外，d<vi, vj>具有d(vi, vj)的一切性质。

9、若有向图D(V, E)的基图（将有向图的各有向边改成无向边后得到的无向图）是连通图，则D为弱连通图，简称连通图。对任意vi，vj∈V，若vi→vj或vj→vi至少成立一个，则称D为单向连通图；若均有vi↔vj，则D为强连通图。可见，强连通图一定是单向连通图，单向连通图一定是弱连通图。

10、有向图D(V, E)是强连通图，当且仅当D中存在经过每个顶点至少一次的回路。
证明 充分性（右推左）显然。下面证明必要性（左推右）。设V = {v1，v2，……，vn}，由D的强连通性，vi→vi+1，i = 1，2，……，n－1。设Γi为的vi到vi+1的通路，又因为vn→v1，设设Γn为的vn到v1的通路。依次连接Γ1到Γn，就得到了经过每个顶点至少1次的回路。

11、有向图D是单向连通图，当且仅当D中存在经过每个顶点至少一次的通路。
证明 略。

12、一种涉及路径和圈的构造性证明中常用的方法是：设G(V, E)为n阶图，Γ为一条路径。若Γ的起点和终点都不与Γ外的顶点相邻，就称Γ为极大路径。“极大”的意思是：这条路径不能再向两端延长。任给一条路径，如果它的起点或终点仍然与路径外的一个顶点相连，就将它延伸到这个顶点，直到不能再延伸为止。最后得到的路径就是极大路径。这个方法为扩大路径法。

13、设无向图G(V, E)，如果顶点V能划分成V1、V2（V1∪V2 = V，V1∩V2 = ∅，且V1、V2≠∅），使G中每条边的两个端点分别属于V1、V2，就称G为二分图（二部图、偶图）。称V1、V2为互补顶点子集。常将二分图记作G(V1，V2，E)。对简单二分图G，若V1中的每个顶点都与V2中的全部顶点相邻，就说G为完全二分图Kr,s。其中r = |V1|，s = |V2|。显然完全二分图是完全图。二阶或以上的零图都是二分图。为了体现一个图是二分图，绘制这个图时常常把两个互补顶点子集各自的顶点画在两边。