离散数学讲义-图论

点、边连通度

定义：设G为无向连通图且不含Kn为生成子图，则称k(G)=min{|V’||V’为G的点割集}为G的点连通度，简称连通度，规定完全图Kn的点连通度为n-1, n≥1。又规定非连通图的点连通度为0。如果k(G) ≥k，则称G为k-连通图。

定义：设G为无向连通图，称λ(G)=min{|E’||E’是G的边割集}为G的边连通度。规定非连通图的边连通度为0。如果λ(G) ≥k。则称G为k边-连通图。

在不引起混淆的情况下，图G的点连通度k(G)，边连通度λ(G)，可分别记为k和λ。

2013-7-22

图论

41

Whitney定理

定理：对于任意图G，均有下面不等式成立：

k≤λ≤δ

其中k,λ, δ分别为G的点连通度、边连通度和最小度。

2013-7-22图论42

定理

设v为无向连通图G的一个顶点，v为割点当且仅当存在与v不同的两个顶点u, w，使v处在每一条从u到w的路径上。

2013-7-22图论43

有向图的连通性

1)设G＝是一个有向图，若略去G中所有有

向边的方向后所得到的无向图G1是一个无向连通图，则称该有向图G是一个连通图或称为弱连通图，否则，则称G是一个非连通图；

2)设G＝是一个有向图，若G中任意两个结

点之间至少单方向可达的，则称该有向图G是一个单向连通图；

3)设G＝是一个有向图，若G中任意两个结

点之间都是相互可达的，则称该有向图G是一个强连通图。

2013-7-22

图论

44