离散数学讲义-图论 下载本文

点、边连通度

定义:设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