最后更新: 2025-01-22 09:18 查看: 38 次反馈刷题

连通

连通
由路（有向路）的概念可以引进图（有向图）的连通概念。
定义 8.16 （连通图）设 $u$ 和 $v$ 是图 $G$ 的两个不同的顶点，若 $u$ 和 $v$ 之间存在一条路，则称顶点 $u$ 和 $v$ 是连通的。若图 $G$ 中任何两个不同顶点之间存在一条路，则称 $G$ 为连通图，否则称 $G$ 为不连通图。

在顶点集 $V$ 上定义一个二元关系 $R$ ：对于 $u, v \in V, u R v$ 当且仅当 $u$ 和 $v$ 是连通的，$R$ 称为连通关系。容易验证连通关系是 $V$ 上的一个等价关系。这一等价关系便确定了 $V$ 的一个划分：把 $V$划分为非空子集 $V_1, V_2, \cdots, V_\omega$ ，使得 $u$ 和 $v$ 属于同一子集 $V_i$ 当且仅当 $u$ 和 $v$ 是连通的。

每个顶点子集 $V_i$ 的导出子图 $G_i$ 称为 $G$ 的一个连通分支，简称分支。根据连通关系 $V$ 可以划分为 $V_1, V_2, \cdots, V_\omega$ ，则 $G$ 有 $\omega$ 个连通分支：$G_1, G_2, \cdots, G_\omega$ 。当 $\omega=1$ 时，$G$ 是连通图。

下面给出有关连通的两个例子。
例 8.1 若图 $G$ 中恰有两个顶点的度数为奇数，则这两个顶点之间必有一条路。
证明：如果 $G$ 是连通图，结论显然成立。如果 $G$ 不连通，有连通分支：$G_1, G_2, \cdots, G_\omega$ ，则可分两种情况：度数为奇数的两个顶点 $v_1$ 和 $v_2$ 同属于一个分支 $G_i$ ，结论成立；当 $v_1$ 和 $v_2$ 不属于同一个分支，设 $v_1 \in G_1, v_2 \in G_2$ ，因为 $G_1$ 和 $G_2$ 是图，在 $G_1$ 和 $G_2$ 中奇顶点都是偶数个，所以这是不可能的。因此 $v_1$ 和 $v_2$ 必属于同一分支，结论成立。

例8．2 设 $G$ 是 $n$ 个顶点的简单图，若 $G$ 有 $e$ 条边，$\omega$ 个分支，则 $n-\omega \leqslant e \leqslant(n-\omega)(n-\omega+1) / 2$ 。
证明：首先证明 $e \geqslant n-\omega$ ，即 $G$ 的边数最少有 $n-\omega$ 条边。以 $G$ 的边数为归纳变量，用归纳法进行证明。设 $e=0$ ，即 $G$ 是零图，$n=\omega$ ，结论成立。假设对 $e=e_0-1$ 的简单图，结论成立；对于 $e=e_0$ 的简单图 $G$ ，从 $G$ 中删去任一边，得到图 $G^{\prime}$ ，有两种情况。
（1）$G^{\prime}$ 有 $n$ 个顶点，$\omega$ 个分支，$e_0-1$ 条边，由归纳假设可知 $n-\omega \leqslant e_0-1$ ，显然 $n-\omega \leqslant e_0$ ；
（2）$G^{\prime}$ 有 $n$ 个顶点，$\omega+1$ 个分支，$e_0-1$ 条边，由归纳假设可知 $n-(\omega+1) \leqslant e_0-1$ ，即 $n-\omega \leqslant e_0$ 。因此在 $G$ 中 $n-\omega \leqslant e_0$ 。

然后证明 $e \leqslant(n-\omega)(n-\omega+1) / 2$ ，即 $G$ 的边数最多有 $(n-\omega)(n-\omega+1) / 2$ 条。要求 $G$ 的边数最多，则首先要求 $G$ 的每个分支是一个完全图。现在假设其中两个完全图的分支为 $G_i$ 和 $G_j$ ，其顶点数分别为 $n_i$ 和 $n_j$ ，则边数分别为 $n_i\left(n_i-1\right) / 2$ 和 $n_j\left(n_j-1\right) / 2$ ，并设 $n_i \geqslant n_j>1$ ，若在 $G_i$ 中增加一个顶点， $G_j$ 中减少一个顶点，则图 $G$ 的顶点总数不变，分支数不变，而边数增加为： $n_i\left(n_i+1\right) / 2-n_i\left(n_i-1\right) / 2-n_j\left(n_j-1\right) / 2+\left(n_j-1\right)\left(n_j-2\right) / 2=n_i-n_j+1>0$ 。

所以，要使 $n$ 个顶点，$\omega$ 个分支的图 $G$ 的边数最多，$G$ 必须是由一个 $n-\omega+1$ 个顶点的完全图和 $\omega-1$ 个孤立点组成，$n-\omega+1$ 个顶点的完全图的边数为 $(n-\omega)(n-\omega+1) / 2$ 。因此 $e \leqslant$ $(n-\omega)(n-\omega+1) / 2$ 。

由例 8.2 可推导出：当 $\omega=1$ 时，$e \geqslant n-1$ ；即 $n$ 个顶点的连通图至少有 $n-1$ 条边。 $n$ 个顶点且边数为 $n-1$ 的连通图称为最小连通图，又称为树，第 10 章将系统地论述树及其性质。

对于有向图，有三种不同的连通概念。现给出有关的定义。
定义 8.17 （可达的）设 $u$ 和 $v$ 是有向图 $G$ 的两个顶点，若从 $u$ 到 $v$ 存在一条有向路，则称顶点 $v$ 是从 $u$ 可达的，或称从 $u$ 可达 $v$ 。

定义8．18（强连通图／单向连通图／弱连通图）设有向图 $G$ ，若 $G$ 中任何两个顶点是互相可达的，则称 $G$ 为强连通图。若 $G$ 中任何两个顶点至少有一个顶点从另一个顶点可达，则称 $G$ 为单向连通图。若 $G$ 中弧的方向不考虑时，任何两个顶点之间存在一条路，则称 $G$ 为弱连通图。

显然，每一个强连通图是单向连通的，而每个单向连通图是弱连通的，但不一定是强连通的。

每个顶点子集 $V_i$ 导出的子图 $G\left(V_i\right)$ 是强连通的，称为 $G$ 的一个强连通分支。
邻接矩阵和路径矩阵
在第 2 章中叙述了用关系图和关系矩阵表示关系，关系图相当于有向图，而关系矩阵就是我们将要介绍的邻接矩阵，对于图也可以用邻接矩阵来表示。

刷题

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

上一篇：路与回路

下一篇：邻接矩阵

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