图的连通度

割点、割边和块
定义：设v是G的结点，如果\(G-v\)的连通分支比G多，则称v是G的一个割点。类似定义割边。
如果G有割边，则G一定有割点。

定义：图G的极大的无割点连通子图称为G的块。
如果G没有割点，则G本身是一个块。

定理1. 设v是G的结点。则以下论断等价：
1. v是G的割点；
2. 存在两个不同于v的结点u，w使得任意一条u到w的道路P都经过v；
3. \(V-v\)可以划分为两个结点子集\(U,W\)，使得任意\(u\in U, w\in W\)，v都在u到w的任意一条道路上。

定理2. 设e是G的一边。则以下论断等价：
1. e是G的割边；
2. e不属于G的任何回路；
3. 存在两结点u，v，使得e属于任何u到v的道路；
4. \(G-e\)的结点集可以划分为两个结点子集\(U,W\)，使得任意\(u\in U, w\in W\)，e都在u到w的任意一条道路上。

定理3. 设G是n阶无向连通图，则G是块当且仅当G的任意两结点在同一回路上。
证明：充分性显然。必要性对\(d(u,v)\)归纳。注意利用块的性质：删去任一结点后仍连通。

定理4. 设G是阶不小于3的连通图，则以下论断等价：
1. G是块；
2. G的任何两结点同属于某回路；
3. G的任一结点和任一边同属于某回路；
4. G的任意两边同属于某回路；
5. 给定任意两结点u，v和一边e，存在一条从u到v的道路包含e；
6. 对任意三个结点u，v，w，存在从u到w的道路经过v；
7. 对任意三个结点u，v，w，存在从u到w的道路不经过v。
证明：既得1，2，3，4等价，\(3\Rightarrow5\Rightarrow6\Rightarrow7\Rightarrow1\)显然。

可以在G的边集上定义一个等价关系：\(e_1\sim e_2\)当且仅当\(e_1,e_2\)在同一回路上或\(e_1=e_2\)。\(\sim\)的等价类即G的块。

连通度
定义：若连通图G删去结点子集\(A\subseteq V\)后不连通，称A为G的一个点断集。
称\(\mu(G)=\min |A|\)为G的连通度。
定义：对于连通图G的断集B，称\(\lambda(G)=\min |B|\)为G的边连通度。

定理5. 连通图G中有\[\mu(G)\le\lambda(G)\le\delta(G)\]
定义. 设G是连通图，若\(\mu(G)\ge k,\)则称G是k连通图；若\(\lambda(G)\ge k\)，则称G是k边连通图。

定理6. 简单连通图G中，有\(\mu(G)\le [\frac{2m}{n}]\)。
证明：由握手定理显然。
用\(f(k,n)\)表示n阶k连通图的最少边数，则定理6说明\(f(k,n)\ge \lceil \frac {kn}{2}\rceil\)。

定理7. 设G是n阶简单图，k是正整数，结点度满足：\(d(v_1)\le d(v_2)\le \cdots\le d(v_n)\),且当\(1\le r\le n-1-d(v_{n-k+1})\)时有\(d(v_r)\ge r+k-1\)，则G是k连通图。

定理8. 设G是n阶简单图，若\(\delta(G)\ge \lfloor \frac n 2\rfloor\)，则\(\lambda(G)=\delta(G)\)。
证明：先证G是连通图。再取\(\lambda(G)\)边的断集，分别估计两个连通分支的边数。

定理9. 设G是n阶连通图，\(k\le n-1\)。则以下结论成立：
1. G是k连通的，当且仅当G中任意两点之间至少有k条内部不交的道路。
2. G是k边连通的，当且仅当G中任意两结点之间至少存在k条边不重复的道路。

    所属分类：离散数学     发表于2022-08-25