点、边连通度
定义：设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＝
向边的方向后所得到的无向图G1是一个无向连通图，则称该有向图G是一个连通图或称为弱连通图，否则，则称G是一个非连通图；
2)设G＝
点之间至少单方向可达的，则称该有向图G是一个单向连通图；
3)设G＝
点之间都是相互可达的，则称该有向图G是一个强连通图。
2013-7-22
图论
44