图的连通性

$G=<V,E>$ 为无向图, 若 $v_i$ 与 $v_j$ 之间有通路, 则 $v_i\sim v_j$, $\sim$ 是 $V$ 上的等价关系 $R=\{<u,v>|u,v\in V\wedge u\sim v\}$.

若 $\forall u,v\in V,u\sim v$, 则称 $G$ 连通.

连通分支

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

指向原始笔记的链接

短程线与距离

$u\sim v$, $u$ 与 $v$ 之间长度最短的通路称为短程线.

短程线的长度称为 $u$ 与 $v$ 的距离, 记为 $d(u,v)$.

• $d(u,v)\ge 0$.
• $u\nsim v$ 时, $d(u,v)=\infty$.
• $d(u,v)=d(v,u)$.
• $d(u,v)+d(v,w)\ge d(u,w)$.

指向原始笔记的链接

删除顶点和边

• 从 $G$ 中将 $v$ 及其关联的边去掉, $G-v$.
• 从 $G$ 中删除 $V^{\prime }$ 中所有的顶点, $G-V^{\prime }$.
• 将 $e$ 从 $G$ 中去掉, $G-e$.
• 删除 $E^{\prime }$ 中所有边, $G-E^{\prime }$.

指向原始笔记的链接

点割集与边割集

连通分支

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

指向原始笔记的链接

指向原始笔记的链接

有向图的连通性

$D=<V,E>$ 为有向图, $v_i$ 到 $v_j$ 有通路, $v_i\to v_j$, $v_i$ 与 $v_j$ 相互可达, $v_i\leftrightarrow v_j$.

• $\to$ 具有自反性, 传递性.
• $\leftrightarrow$ 具有自反性, 对称性, 传递性.

基图为无向连通图, $D$ 弱连通. $\forall v_i,v_j\in V,v_i\to v_j\vee v_j\to v_i$, $D$ 单向连通. $forall{v}_i,v_j\in V,v_i\leftrightarrow v_j$, $D$ 强连通.

定理 $D$ 强连通当且仅当 $D$ 中存在经过每个顶点至少一次的回路.

定理 $D$ 单向连通当且仅当 $D$ 中存在经过每个顶点至少一次的通路.

指向原始笔记的链接

扩大路径法

设 $G=<V,E>$ 为 $n$ 阶无向图, $E\ne \varnothing$, 设 ${\Gamma }_l$ 为 $G$ 中的一条 路径, 若路径的起点或终点与路径外的顶点相邻, 将顶点扩大到路径中. 设最后得到的路径为 ${\Gamma }_{l+k}$, 称为极大路径.

极大路径不一定是图中最长的路径.

指向原始笔记的链接

二部图

设 $G=<V,E>$ 为一个无向图, 若能将 $V$ 分为 $V_1$ 和 $V_2$, $V=V_1\cup V_2$, $\varnothing =V_1\cap V_2$, 使得 $G$ 中的每条边的两个顶点都是一个属于 $V_1$, 一个属于 $V_2$, 则称 $G$ 为二部图, $V_1,V_2$ 为互补顶点子集, $G$ 记作 $<V_1,V_2,E>$.

完全二部图

若 $G$ 是简单二部图, $V_1$ 中每个顶点均与 $V_2$ 中的所有顶点相邻, 则称 $G$ 为完全二部图, 记为 $K_{r,s}$, $r=|V_1|,s=|V_2|$.

指向原始笔记的链接

$n$ 阶零图为二部图.

定理 无向图 $G=<V,E>$ 是二部图当且仅当 $G$ 中无奇圈.

指向原始笔记的链接