点割集与边割集

连通分支

$V/R=\{V_1,V_2,...,V_k\}$, 称 $G[V_1],G[V_2],...,G[V_k]$ 为连通分支, 其个数 $p(G)=k(k\ge 1)$.

指向原始笔记的链接

$G=<V,E>,V^{\prime }\subset V$, $V^{\prime }$ 为点割集, 当且仅当 $p(G-V^{\prime })>p(G)$ 且有极小性, $v$ 为割点, $\{v\}$ 为点割集.

$G=<V,E>,E^{\prime }\subseteq E$, $E^{\prime }$ 是边割集, 当且仅当 $p(G-E^{\prime })>p(G)$ 且有极小性, $e$ 是割边 (桥), $\{e\}$ 是边割集.

• $K_n$ 中无点割集, $N_n$ 中既无点割集, 也无边割集. $N_n$ 为 $n$ 阶零图.
• 若 $G$ 连通, $E^{\prime }$ 为边割集, 则 $p(G-E^{\prime })=2$, $V^{\prime }$ 为点割集, 则 $p(G-V^{\prime })\ge 2$.

点连通度与边连通度

点连通度

$\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)$.

指向原始笔记的链接