最后更新: 2025-01-22 09:18 查看: 115 次纠错评论(0) 课件开VIP

连通

连通
由路（有向路）的概念可以引进图（有向图）的连通概念。
定义 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 章中叙述了用关系图和关系矩阵表示关系，关系图相当于有向图，而关系矩阵就是我们将要介绍的邻接矩阵，对于图也可以用邻接矩阵来表示。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：顶点的度数与握手定理

下一篇：邻接矩阵

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