最后更新: 2024-04-06 18:29 查看: 148 次反馈刷题

连通性

## 连通性
定义 7 在无向图中, 若存在从 $u$ 到 $v$ 的通路, 则称 $u$ 和 $v$ 是连通的。规定任一结点到自身总是连通的; 在有向图中, 若存在从 $u$ 到 $v$ 的通路, 则称 $u$ 可达 $v$ 。规定任一结点 $u$ 到自身总是可达的。

定义 8 若无向图 $G$ 是平凡图, 或 $G$ 中任意两个结点都是连通的, 则称 $G$ 是连通图;否则称 $G$ 是非连通图或分离图。

易知无向图结点之间的连通关系为等价关系，按等价关系可将结束集 $V$ 划分成互不相交的等价类 $V_1, V_2, \cdots, V_K$, 则导出子图 $G\left(V_1\right), G\left(V_2\right), \cdots, G\left(V_k\right)$ 都是 $G$ 的连通子图,称为 $G$ 的连通分支或分支。 $G$ 的分支数记作 $p(G)$ 。

对图的连通性需要作定量的描述。首先要确定衡量图的连通程度的标准。对无向连通图 $G$, 若至少要删除若干个结点或若干条边才能使 $G$ 成为不连通的, 则显然需要删除的结点数和边数愈多, 说明 $G$ 的连通程度愈 “好”。下面给出一些确切的定义。

定义 9 设 $G=<V, E>$ 为连通无向图, $T \subset V$, 若 $G-T$ 不连通或是平凡图, 则称 $T$为 $G$ 的点断集或点割集。若 $\{v\}$ 为 $G$ 的点断集, 则称 $v$ 为 $G$ 的断点或割点, $\kappa(G)=\min \{|T| \mid T$ 为 $G$ 的点断集 $\}$ 称为 $G$ 的点连通度或连通度。规定非连通图和平凡图

的连通度为 0 。若 $\kappa(G) \geq k$, 则称 $G$ 是 $k$-连通的。 $\kappa\left(K_n\right)=n-1$ 。
定义 10 设 $G=<V, E>$ 为连通无向图, $S \subset E$, 若 $G-S$ 不连通或是平凡图, 则称 $S$为 $G$ 的边断集或边割集或割集。若 $\{e\}$ 为 $G$ 的边断集, 则称 $e$ 为 $G$ 的断边或割边或桥。 $\lambda(G)=\min \{|S| \mid S$ 为 $G$ 的边断集 $\}$ 称为 $G$ 的边连通度。若 $\lambda(G) \geq k$, 则称 $G$ 是 $k-$ 边连通的。规定非连通图和平凡图的边连通度为 0 。 $\lambda\left(K_n\right)=n-1$ 。
定理 5 对任一无向图 $G$, 有 $\kappa(G) \leq \lambda(G) \leq \delta(G)$ 。
定理 6 对任一无向图 $G=(n, m)$, 有 $\kappa(G) \leq\left\lfloor\frac{2 m}{n}\right\rfloor, \lambda(G) \leq\left\lfloor\frac{2 m}{n}\right\rfloor$ 。
定义 11 设 $D$ 为有向图, 若略去 $D$ 中有向边的方向所得的无向图是连通图, 则称 $D$为连通的或弱连通的; 若 $D$ 中任意两结点间至少有一个结点可达另一个结点, 则称 $D$ 为单向连通的; 若 $D$ 中的任意一对结点都相互可达, 则称 $D$ 为强连通的。
若 $D$ 强连通, 则 $D$ 是单向连通的; 若 $D$ 单向连通, 则 $D$ 是弱连通的。反之, 则不然。
定理 7 有向图 $D$ 是强连通的, 当且仅当 $D$ 中存在一条经过每个结点至少一次的有向回路。

定理 8 设有向图 $D$ 是弱连通的, 若 $D$ 的每个结点的出度 (或入度) 均为 1 , 则 $D$ 恰有一条有向回路。

在有向图中, 具有强连通性质的极大子图称为强分图; 具有单向连通性质的极大子图称为单向分图; 具有弱连通性质的极大子图称为弱分图 (此处 “极大” 的含义是子图具有某种性质, 但若再加上任意一个其他结点, 就不再具有该性质)。
定理 9 有向图的每个结点恰好位于一个强分图中。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：通路与回路

下一篇：图的矩阵表示

本文对您是否有用？有用 (0) 无用 (0)