3.1顶联通度
定义 3.1. 给定简单图G=(V(G),E(G))的一对不相邻的顶点u,v∈V(G),u=v。
若S⊆V(G)−u,v使得u与v在G−S中不连通,即分属于两个不同的连通片,则称S是一个**uv-顶割集**,简称uv-割集。也称S隔离了u与v。
含顶点最小的uv-割集被称为最小uv-割集,其中的顶点数记为c(u,v),称为u与v在G中的顶连通度,记为**uv-连通度**。
定义 3.2. 给定连通简单图G=(V(G),E(G)),以及S⊂V(G),若G−S中不连通,则称S是G的顶割集,简称割集。若一个割集中有k个元素,则称之为k-顶割集。含顶点数最少的割集称为最小割集,其中的顶点数记为κ(G),称为G的顶连通度。
- 完全图与非连通图都没有割集,不能应用上面的定义。
- 完全图的连通度为κ(Kn)=n−1;
- 非连通图的连通度为κ(非连通图)=0.
- 若κ(G)≥k,则称G是k-连通的。
如果除了u,v之外。P(u,v)与Q(u,v)没有其他的公共顶点,我们称这样的两条轨道为无公共内顶的uv-轨道。记两两无公共内顶的uv-轨道的最大数量为p(u,v)。
定理 3.1. (Menger定理顶点版本)给定简单图G中两个不相邻的顶点u,v,G中两两无公共内顶的uv-轨道的最大数量等于最小uv-割集中的顶点数,即p(u,v)=c(u,v)
- 收缩图G⋅S的概念:首先在简单图G中删掉两个端点都在S中的边;再将S中所有的顶点收缩为一个顶点s;若v∈V(G)−S与S中某个顶点相邻,则在G⋅S中将v与s连边。
推论 3.1. 给定简单图G,有:min{p(u,v)∣u,v∈V(G),u=v,uv∈/E(G)}=min{c(u,v)∣u,v∈V(G),u=v,uv∈/E(G)}
- 对于Kn来说,κ(Kn)=min{p(u,v)∣u,v∈V(Kn),u=v}
定理 3.2. (Whitney)任给简单图G,都有:κ(G)=min{p(u,v)∣u,v∈V(Kn),u=v}
- 给出一种求κ(G)的方法。
- p(u,v)是两两无公共内顶的uv-轨道的最大数量。
**两个定理(Menger&Whitney)的意义:**将指数级别的运算转化为多项式级。将求κ(G)转化为求G中任意两个不同顶点之间无公共内顶轨道的最大数量。借助辅助的有向图,通过有向图的最大流算法来求出这种轨道的最大数量。
3.2 扇形引理
引理 3.1. 假设简单图G是k-连通图,在G中增加一个新的顶点y,并且在G中任意选取至少k顶点,让y与这些选取的顶点各连一条边,得到的图记为H,则H也是k-连通图。
推论 3.2. 假设简单图G是k-连通图,X,Y是图G中两个顶点子集,∣X∣≥k,∣Y∣≥k且X∩Y=∅,则G中存在k条无公共顶点的(X,Y)-轨道。其中,(X,Y)-轨道指的是轨道的两个端点分属X与Y,而中间顶点不属于X∪Y。
- 加入虚拟顶点x与X相连,y与Y相连,得到图H。
- 根据定理 3.2.(Whitney),可以构造k个xy-轨道。
给定简单图G,x∈V(G),Y⊆V(G)−{x}且∣Y∣≥k,一组k条起点为x、终点为Y中k个不同的顶点、且除了x之外无公共顶点的轨道称为从x到Y的k-扇形。
推论 3.3. 假设简单图G是k-连通图,x∈V(G),Y⊆V(G)−{x}且∣Y∣≥k,则G中存在从x到Y的k-扇形。
定理3.3. (Dirac)设S是k-连通图G中的k元顶点子集,k≥2,则G中存在一个圈C,使得S中所有的顶点都在C上。
3.3 边联通度
定义 3.3. 给定简单图G=(V(G),E(G))的一对顶点u,v,u=v。若边子集E′⊆E(G)使得u和v在G−E′中不连通,即分属两个不同的连通片,则称E′是一个uv-边割集。含边数最少的uv-边割集称为最小uv-边割集,其中的边数记为c′(u,v),称为u与v在G中的边联通度,简称为uv-边联通度。
- c′(u,v)是u与v在G中的边联通度
定义 3.4. 给定连通简单图G=(V(G),E(G)),以及E′⊆E(G)。若G−E′不连通,则称E′是G的边割集。若一个边割集中有k条边,则称之为k-边割集。含边数最少的边割集称为最小边割集,其中的边数记为κ′(G),称为G的边联通度。若图G不是连通图,就定义κ′(G)=0。
定理 3.4. (Menger定理边版本)给定图G中两个顶点u,v,G中两两无公共边的uv-轨道的最大数量等于最小uv-边割集中的边数,即p′(u,v)=c′(u,v)。
定理 3.5. 假定G是简单图,则有:κ(G)≤κ′(G)≤δ(G)。
3.4 割顶、桥与块
定义 3.5. 给定连通简单图G=(V(G),E(G)),若存在顶点v,使得G−v不连通,即{v}是割集,则称v是G的割顶。
定理 3.6. 设G是连通图,v∈V(G)−{v},则下述命题等价:
- v是G的割顶;
- 存在与v不同的两个顶点u,w∈V(G)−{v},使得v在每一条从u到w的轨道上;
- 存在V(G)−{v}的一个划分V(G)−{v}=U∪W,U∩W=∅,U=∅,W=∅,使得任给u∈U,w∈W,v在每一条从u到w的轨道上。
定义 3.6. 给定连通简单图G=(V(G),E(G)),若存在边e,使得G−e不连通,也就是{e}是边割集,则称e是G的桥(或割边)。
定理 3.7. 设G是连通图,v∈V(G)−{v},则下述命题等价:
- e是G的桥;
- e不在G的任一圈上;
- 存在u,w∈V(G),使得e在每一条从u到w的轨道上;
- 存在V(G)的一个划分使V(G)=U∪W,U∩W=∅,U=∅,W=∅,使得任给u∈U,w∈W,e在每一条从u到w的轨道上。
定义 3.7. 没有割顶的简单图G称为块。若G不是块,则G的成块的极大子图称为G的块。
作业
3.1 G是k-边连通图,E’是G的k条边的集合,则ω(G−E′)≤2