点连通度与边连通度

点连通度

$\kappa (G)=min\{|V^{\prime }||V^{\prime }\text{为点割集}\}$, 称为点连通度.

规定 $\kappa (K_n)=n-1$, 若 $G$ 非连通, $\kappa (G)=0$.

指向原始笔记的链接

k-连通图

若 $\kappa (G)\ge k$, 则称 $G$ 为 k- 连通图.

指向原始笔记的链接

边连通度

$\lambda (G)=min\{|E^{\prime }||E^{\prime }\text{为边割集}\}$, 称为 $G$ 的边连通度.

若 $G$ 非连通, 则 $\lambda (G)=0$.

指向原始笔记的链接

r 边-连通图

若 $\lambda (G)\ge r$, 则称 $G$ 是 $r$ 边 - 连通图.

指向原始笔记的链接

• $\kappa (K_n)=\lambda (K_n)=n-1$.
• $G$ 非连通, 则 $\kappa =\lambda =0$.
• 若 $G$ 中有割点, $\kappa =1$.
• 若 $G$ 中有桥, $\lambda =1$.
• 若 $\kappa (G)=k$, 则 $G$ 是 1- 连通图, 2- 连通图, …, $k$- 连通图, 但不是 $(k+s)$- 连通图.
• 若 $\lambda (G)=r$, 则 $G$ 是 1- 边连通图, 2- 边连通图, …, $r$- 边连通图, 但不是 $(r+s)$- 边连通图.

定理 $\kappa (G)\le \lambda (G)\le \delta (G)$.