离散数学第八章 (第2讲)

（2）连通分支 若无向图G的每个子图都是连通图，称为G的连通分支。 G的分支数记作p(G) 。
（3）强连通，单向连通，弱连通
简单有向图G：
如果G的任何两结点间均是互相可达的，则称图G是强连通的。
如果G的任何两结点间至少有一个结点到另一结点是可达的。则 称G是单向连通的。
如果忽略边的方向，将它看成无向图后，图是连通的，则称该图 为弱连通的。
连通，而对于E1的任何一个非空真子集E2， G－ E2 是连通的，
则称E1 是G的边割集。 若某一条边构成一个边割集，则称该条边为割边或桥。 在下图中, { e5 }, { e6 }, { e2, e3 }, { e1, e2 }, { e3, e4 }, { e1, e4 }, { e1, e3 }, { e2, e4 }都是边割集, 其中e5和e6是桥。
例：
G的强分图为：{1,2,3}，{4}，{5}，{6} G的单侧图为：{1,2,3,4,5}，{5,6} G的弱分图为：{1,2,3,4,5,6}
定理：在任一简单有向图Ｇ＝＜Ｖ，Ｅ＞中，有向 图的每一个结点位于且只位于一个强分图之中。
4 1
3 2
5
定义 设无向图G = <V, E>是连通无向图, V1V, 若G－ V1 不 连通或是平凡图,而对于V1的任何一个非空真子集V2， G－ V2 是连通的，则称V1 是G的点割集。
e3 e2
e4
v2
e5
e6
e7
e8
v3
v4
路的表示方法：
(a)结点表示法： (v1, v2 vk ) (b)边表示法： (e1, e2 ek )例：给出有向图Ｇ，求起始于１，终 Nhomakorabea于4的路。
练习：
在下图中， ADEBCF；ADEBCEF这两条路，哪个是通路， 哪个是迹？
A
B
C
D
E
F
练习：
在下图中，求v1到v4长度分别为1，2，3的路分别有哪些？
一个有向图，忽略边的方向后得到的无向图若是连通 的，则称该有向图为连通图，否则称非连通图。
a
c
a
c
b
d
b
d
（a）
（b）
练习：已知关于人员A,B,C,D,E的下述事实： A说英语； B说英语和西班牙语； C说英语，意大利语和俄语； D说日语和西班牙语； E说法语，日语和俄语。 试问，上述五个人中是否任意两人都能交谈。 （如果必要，可由其余3人所组成的译员链帮忙）
定义 设G为无向连通图且为非平凡图, 则称 (G) = min{ |E1| | E1 为G的边割集 } 为G的边连通度。 规定:非连通图和平凡图的边连通度为(G) = 0；完全 图Kn(n 1)的边连通度(Kn) =n-1.
练习： 下图的点连通度为
，边连通度为______.
练习： 分别求出n阶完全无向图Kn的点连通度和边连通度。 解：
8.2 路与图的连通性
1、路的定义：在图G =<V，E>中，设v0，v1，…vn∈V, e1 ,e2 … en ∈E ， 其中ei是关联于结点vi-1,vi的边，结
点与边的交替序列v0 e1 v1 … en vn称为联结v0到vn的路。
v10
e1 v21
e3 e2
e4
v32
e5
e6
e7
e8
v43
v54
v2
e5
e6
e7
e8
v3
v4
路的其它概念
（5）在路 v0 e1 v1 … en vn 中，若v0= vn 则路称作回路。
（6）除v0= vn 外，其余结点和所有边均不相同的回路，称作圈
(基本回路)。
v0
（7） 所有边均不相同的回路，称作简单回路。 e1
v1
显然：基本回路必为简单回路，反之，则不然。
D.{v2,v3}
定义：设G为无向连通图且为非完全图, 则称 (G) = min{ |V1| | V1 为G的点割集 } 为G的点连通度, 简称连通度。(G)简记为 。
完全图Kn(n 1)的点连通度为n-1；规定非连通图和 平凡图的点连通度为0；
定义 设无向图G = <V, E>是连通无向图, E1E, 若G － E1 不
若某一个结点构成一个点割集，则称该结点为割点。
在下图中, { v2, v4 }, { v3 }和{ v5 }都是点割集, v3和v5都是割点。
练习：
设图G=<V,E>的结点集为V={v1,v2,v3},边集为 E={<v1,v2>,<v1,v3>},则G的割点是( )
A.{v1}
B.{v2}
C.{v3}
v1
v4
v2
v3
解 ：v1到v4长度分别为1和2的路：没有。 v1到v4长度为3的路一条：v1 v2 v3 v4。
定理1：在一个 n 阶图中，如果从结点u到结点v存在一 条路，则从从结点u到结点v必存在一条长度小于等于 n-1条边的通路。
定理2：在一个 n 阶图中，若存在v到自身的简单回路， 则必存在v到自身长度小于等于n的基本回路。
若G是强连通的，则G是单向连通的。若G是单向连通的，则G是 弱连通的。 反之，不成立。
A
A
A
B
C
(a)
B
C
(b)
B
C
(c)
练习：
下列各有向图是强连通图的是（
）.
定理 ：一个有向图是强连通的充要条件是：它包含 一个回路，该回路至少包含每个结点一次。
A
D
B
C
定义：设Ｇ＝＜Ｖ，Ｅ＞为一简单有向图，且Ｇ’是Ｇ 的子图。 具有强连通性质的极大子图Ｇ’称为强分图； 具有单侧连通性质的极大子图Ｇ’称为单侧图； 具有弱连通性质的极大子图Ｇ’称为弱分图。
v1
v4
v2
v3
无向图的结点连通性 定义：设图Ｇ为无向图，且 u , v∈V ，若从u到v存在任
何一条路径 ，则称u到v是连通的。
有向图的结点可达性 定义：设图Ｇ为简单有向图，且u , v∈V,若从u到v存在任
何一条路径，则称u到v是可达的。
图的连通性： （1）连通性与非连通性：
若无向图G是平凡图，或G中任意两结点间都是连通的， 则称图G是连通图，否则称G是是非连通图。
(K n ) n 1
(K N ) n 1
定理： 对于任何无向图G, 有: (G) (G) (G)。 例 (1) 给出一些无向简单图, 使得: = = ； 无向完全图Kn和零图Nn都满足要求。
路的其它概念
（1）在路 v0 e1 v1 … en vn 中，v0和vn分别称作路的起点与终点。 （2）一条路中所有的边的数目称作路的长度。
（3）一条路中所有的边均不相同，则此路称作迹。
（4）一条路中所有的结点均不相同，则此路称作通路。
显然：通路必为迹，而迹不一定是通路。
v0
e1
e3 e2
v1
e4