CSGNAK的博客

图论3——图的连通性

Word count: 2.2kReading time: 10 min
2021/10/14 Share

3.1顶联通度

定义 3.1. 给定简单图G=(V(G),E(G))G=(V(G),E(G))的一对不相邻的顶点u,v∈V(G)，u≠vu,v\in V(G)，u\neq v。

若S⊆V(G)−u,vS\subseteq V(G)-{u,v}使得uu与vv在G−SG-S中不连通，即分属于两个不同的连通片，则称SS是一个**uvuv-顶割集**，简称uvuv-割集。也称SS隔离了uu与vv。

含顶点最小的uvuv-割集被称为最小uvuv-割集，其中的顶点数记为c(u,v)c(u,v)，称为uu与vv在GG中的顶连通度，记为**uvuv-连通度**。

  • 割集是一个子图。连通度是最小uv-割集的顶点数。
截屏2021-10-12 下午2.18.15

定义 3.2. 给定连通简单图G=(V(G),E(G))G=(V(G),E(G))，以及S⊂V(G)S\subset V(G)，若G−SG-S中不连通，则称S是G的顶割集，简称割集。若一个割集中有kk个元素，则称之为kk-顶割集。含顶点数最少的割集称为最小割集，其中的顶点数记为κ(G)\kappa(G)，称为GG的顶连通度。

  • 完全图与非连通图都没有割集，不能应用上面的定义。
  • 完全图的连通度为κ(Kn)=n−1\kappa (K_n)=n-1；
  • 非连通图的连通度为κ(非连通图)=0\kappa(非连通图)=0.
  • 若κ(G)≥k\kappa(G)\geq k，则称GG是kk-连通的。

如果除了u,vu,v之外。P(u,v)P(u,v)与Q(u,v)Q(u,v)没有其他的公共顶点，我们称这样的两条轨道为无公共内顶的uvuv-轨道。记两两无公共内顶的uvuv-轨道的最大数量为p(u,v)p(u,v)。

定理 3.1. (Menger定理顶点版本)给定简单图GG中两个不相邻的顶点u,vu,v，GG中两两无公共内顶的uvuv-轨道的最大数量等于最小uvuv-割集中的顶点数，即p(u,v)=c(u,v)p(u,v)=c(u,v)

  • 收缩图G⋅SG·S的概念：首先在简单图GG中删掉两个端点都在SS中的边；再将SS中所有的顶点收缩为一个顶点ss；若v∈V(G)−Sv\in V(G)-S与SS中某个顶点相邻，则在G⋅SG·S中将vv与ss连边。
截屏2021-10-12 下午2.57.49

推论 3.1. 给定简单图GG，有：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)}min\{ p(u,v)|u,v\in V(G),u\neq v,uv\notin E(G)\}\\=min\{ c(u,v)|u,v\in V(G),u\neq v,uv\notin E(G)\}

  • 对于KnK_n来说，κ(Kn)=min{p(u,v)∣u,v∈V(Kn),u≠v}\kappa(K_n)=min\{ p(u,v)|u,v\in V(K_n),u\neq v\}

定理 3.2. (Whitney)任给简单图GG，都有：κ(G)=min{p(u,v)∣u,v∈V(Kn),u≠v}\kappa(G)=min\{ p(u,v)|u,v\in V(K_n),u\neq v\}

  • 给出一种求κ(G)\kappa(G)的方法。
  • p(u,v)p(u,v)是两两无公共内顶的uvuv-轨道的最大数量。

**两个定理(Menger&Whitney)的意义：**将指数级别的运算转化为多项式级。将求κ(G)\kappa(G)转化为求GG中任意两个不同顶点之间无公共内顶轨道的最大数量。借助辅助的有向图，通过有向图的最大流算法来求出这种轨道的最大数量。

3.2 扇形引理

引理 3.1. 假设简单图GG是kk-连通图，在GG中增加一个新的顶点yy，并且在GG中任意选取至少kk顶点，让yy与这些选取的顶点各连一条边，得到的图记为HH，则HH也是kk-连通图。

推论 3.2. 假设简单图GG是kk-连通图，XX,YY是图GG中两个顶点子集，∣X∣≥k|X|\geq k，∣Y∣≥k|Y|\geq k且X∩Y=∅X\cap Y=\empty，则GG中存在kk条无公共顶点的(X,YX,Y)-轨道。其中，(X,YX,Y)-轨道指的是轨道的两个端点分属XX与YY，而中间顶点不属于X∪YX\cup Y。

  • 加入虚拟顶点xx与XX相连，yy与YY相连，得到图HH。
  • 根据定理 3.2.(Whitney)，可以构造kk个xyxy-轨道。

给定简单图GG，x∈V(G)x\in V(G)，Y⊆V(G)−{x}Y\subseteq V(G)-\{x\}且∣Y∣≥k|Y|\geq k，一组kk条起点为xx、终点为YY中kk个不同的顶点、且除了xx之外无公共顶点的轨道称为从xx到YY的kk-扇形。

推论 3.3. 假设简单图GG是kk-连通图，x∈V(G)x\in V(G)，Y⊆V(G)−{x}Y\subseteq V(G)-\{x\}且∣Y∣≥k|Y|\geq k，则GG中存在从xx到YY的kk-扇形。

定理3.3. (Dirac)(Dirac)设SS是kk-连通图GG中的kk元顶点子集，k≥2k\geq2，则GG中存在一个圈CC，使得SS中所有的顶点都在CC上。

3.3 边联通度

定义 3.3. 给定简单图G=(V(G),E(G))G=(V(G),E(G))的一对顶点u,vu,v，u≠vu\neq v。若边子集E′⊆E(G)E'\subseteq E(G)使得uu和vv在G−E′G-E'中不连通，即分属两个不同的连通片，则称E′E'是一个uvuv-边割集。含边数最少的uvuv-边割集称为最小uvuv-边割集，其中的边数记为c′(u,v)c'(u,v)，称为uu与vv在GG中的边联通度，简称为uvuv-边联通度。

  • c′(u,v)c'(u,v)是uu与vv在GG中的边联通度

定义 3.4. 给定连通简单图G=(V(G),E(G))G=(V(G),E(G))，以及E′⊆E(G)E'\subseteq E(G)。若G−E′G-E'不连通，则称E′E'是GG的边割集。若一个边割集中有kk条边，则称之为kk-边割集。含边数最少的边割集称为最小边割集，其中的边数记为κ′(G)\kappa'(G)，称为GG的边联通度。若图GG不是连通图，就定义κ′(G)=0\kappa'(G)=0。

定理 3.4. (MengerMenger定理边版本)给定图GG中两个顶点u,vu,v，GG中两两无公共边的uvuv-轨道的最大数量等于最小uvuv-边割集中的边数，即p′(u,v)=c′(u,v)p'(u,v)=c'(u,v)。

定理 3.5. 假定GG是简单图，则有：κ(G)≤κ′(G)≤δ(G)\kappa(G)\leq\kappa'(G)\leq\delta(G)。

3.4 割顶、桥与块

定义 3.5. 给定连通简单图G=(V(G),E(G))G=(V(G),E(G))，若存在顶点vv，使得G−vG-v不连通，即{v}\{v\}是割集，则称vv是GG的割顶。

定理 3.6. 设GG是连通图，v∈V(G)−{v}v\in V(G)-\{v\}，则下述命题等价：

  • vv是GG的割顶；
  • 存在与vv不同的两个顶点u,w∈V(G)−{v}u,w\in V(G)-\{v\}，使得vv在每一条从uu到ww的轨道上；
  • 存在V(G)−{v}V(G)-\{v\}的一个划分V(G)−{v}=U∪WV(G)-\{v\}=U\cup W，U∩W=∅U\cap W=\empty，U≠∅U\neq\empty，W≠∅W\neq\empty，使得任给u∈Uu\in U，w∈Ww\in W，vv在每一条从uu到ww的轨道上。

定义 3.6. 给定连通简单图G=(V(G),E(G))G=(V(G),E(G))，若存在边ee，使得G−eG-e不连通，也就是{e}\{e\}是边割集，则称ee是GG的桥（或割边）。

定理 3.7. 设GG是连通图，v∈V(G)−{v}v\in V(G)-\{v\}，则下述命题等价：

  • ee是GG的桥；
  • ee不在GG的任一圈上；
  • 存在u,w∈V(G)u,w\in V(G)，使得ee在每一条从uu到ww的轨道上；
  • 存在V(G)V(G)的一个划分使V(G)=U∪WV(G)=U\cup W，U∩W=∅U\cap W=\empty，U≠∅U\neq\empty，W≠∅W\neq\empty，使得任给u∈Uu\in U，w∈Ww\in W，ee在每一条从uu到ww的轨道上。

定义 3.7. 没有割顶的简单图GG称为块。若GG不是块，则GG的成块的极大子图称为GG的块。

作业

3.1 GG是kk-边连通图，E’E’是GG的kk条边的集合，则ω(G−E′)≤2\omega(G-E')\leq2

CATALOG
  1. 1. 3.1顶联通度
  2. 2. 3.2 扇形引理
  3. 3. 3.3 边联通度
  4. 4. 3.4 割顶、桥与块
  5. 5. 作业
Total : 9
2021
数据结构 心得 计算系统概论 大二上
数据结构