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

有向图无向图

图是由一些顶点和连接这些顶点的边所组成的集合。我们可以用图表示哥尼斯堡：顶点表示岛屿和河的两岸，边表示桥，
 
 ![图片](/uploads/2025-01/beeb2b.jpg)
 
本章首先讨论图的基本概念和术语，然后讨论欧拉图、哈密顿图和最短路，最后对如何利用图论来解决实际问题作了简单介绍

有向图
在第 2 章中，集合论中离散对象之间的关系可以用关系图来描述，这就是图论中的有向图，定义如下。

定义8．1（有向图）设 $V$ 是一个非空集，$E$ 是 $V$ 上的二元关系，称有序对 $(V, E)$ 为有向图，记为 $G=(V, E)$ 或 $G(V, E) 。 V$ 中元素称为顶点（或点），$V$ 称顶点集。 $E$ 是 $V \times V$ 的子集， $E$ 中的元素是有序对，称为弧，$E$ 称为弧集。

为了描述有向图的顶点与弧的连接关系，我们定义如下术语。
定义8．2 顶点 $a$ 和 $b$ 称为弧 $(a, b)$ 的端点，$a$ 为起点，$b$ 为终点。称 $a$ 和 $b$ 与弧 $(a, b)$关联。若顶点 $a$ 和 $b$ 相同，则对应的弧 $(a, b)$ 称为自环。若 $V$ 中某顶点与 $E$ 中任何弧都不关联，则该顶点称为孤立点。与一条弧相关联的两个顶点称为邻接的或相邻的。一个顶点关联于几条弧，称这些弧是弧邻接或弧相邻。

例如图 8.2 中的有向图 $G(V, E) 。 V=\{a, b, c, d\}, E=\{(a, b),(b, a),(b, d),(d, a),(c, c),(d, d)\}$ ，其中 $(c, c),(d, d)$ 均为自环。 $a$ 与 $b$ 相邻；$b$ 与 $d$ 相邻；$(a, b)$ 与 $(b, d)$ 相邻。

在研究有向图时，只考察它的顶点与弧的连接关系以及整个图所具有的性质。至于各个顶点之间的相对位置及弧的长短曲直都是无关紧要的。

无向图
定义8．3（无向图）设 $V$ 是一个非空集，$E$ 是 $V$ 中两个元素组成的多重集为元素的集合，称有序对 $(V, E)$ 为无向图，记为 $G=(V, E)$ 或 $G(V, E)$ 。 $V$ 中元素称为顶点（或点），$V$ 称顶点集。 $E$ 中的元素称为边，$E$ 称为边集。

例如图 8.3 中的无向图 $G(V, E){ }_{\circ} V=\{a, b, c, d, e\}, E=\{\{a, b\},\{b, e\},\{d, a\},\{a, c\},\{c, d\},\{d$ ， $e\},\{c, e\}\}$ 。
 
 ![图片](/uploads/2025-01/bc7aa4.jpg)
 
为了叙述方便，简称无向图为图，如果在有向图中顶点标以名称，如图 8.2 中顶点标 $a$ ， $b, c, d$ ，这样的有向图称为标定图（有向标定图），否则称为非标定图（有向非标定图）。

如果一个图的顶点集和边集是有限的，则称该图为有限图。类似地定义有限有向图。本书中的图和有向图是指有限图和有限有向图。

定义 8.4 若在图 $G=(V, E)$ 中，连接两个顶点之间的边不止一条（这些边称为多重边），则图 $G$ 称为多重图。无自环的非多重图称为简单图。边集为空集的图称为零图。只有一个顶点的图称为平凡图。若图 $G$ 中每两个顶点之间恰有一条边，则图 $G$ 称为完全图。 $n$ 个顶点的完全图记为 $K_n$ 。

定理8．1 $n$ 个顶点的完全图 $K_n$ 的边数为 $n(n-1) / 2$ 。
证明：在 $K_n$ 中，任意两个顶点都有边相连，$n$ 个顶点中任意两个点的组合数为 $n(n-1) / 2$ ，故 $K_n$ 的边数为 $n(n-1) / 2$ 。

从实际问题中抽象出来的图往往在顶点上和边上带有信息，用带权图定义。
定义8．5（带权图）设 $V$ 是顶点集，$E$ 是边集，$f$ 是 $V$ 到实数集的函数，$g$ 是 $E$ 到实数集的函数。称有序三元组 $G=(V, E, f)$ 或 $G=(V, E, g)$ 以及有序四元组 $G=(V, E, f, g)$ 为带权图。

在有向图中类似地可以定义带权有向图。
顶点度数
从以上叙述可知图（有向图）的最本质的内容就是顶点与边（弧）的关系。为了描述这一关系，我们介绍顶点度数这样一个重要的概念。

定义8．6 设 $G=(V, E)$ 是一个图，顶点 $v$ 所关联的边数（自环计算两次）称为顶点 $v$ 的度数，记为 $d(v)$ 。度数为 1 的顶点称为悬挂点。度数为奇（偶）数的顶点称为奇（偶）顶点。图 $G$中顶点的最小度数记为 $\delta(G)$ ，即 $\delta(G)=\min _{v \in V}\{d(v)\}$ ，简记为 $\delta$ 。

设图 $G$ 有 $n$ 个顶点 $v_1, v_2, \cdots, v_n, e$ 条边。有如下定理。

定理 8.2 （握手定理）图 $G$ 的所有顶点度数之和为边数的两倍，即 $\sum_{i=1}^n d\left(v_i\right)=2 e$ 。
证明：因为每条边必定关联两个顶点，而一条边给予其关联的每个顶点的度数为 1 。因此在一个图中，顶点度数的总和等于边数的两倍。

定理 8.3 在图 $G$ 中奇顶点有偶数个。
证明：因为 $\sum_{\text {奇顶占 } v_j} d\left(v_j\right)+\sum_{\text {偶顶点 } v_k} d\left(v_k\right)=\sum_{i=1}^n d\left(v_i\right)$ 为偶数，又因 $\sum_{\text {侧顶点 } v_k} d\left(v_k\right)$ 为偶数，所以 $\sum_{\text {奇顶点 }} d\left(v_j\right)$ 为偶数。由于 $d\left(v_j\right)$ 是奇数，因此奇顶点 $v_j$ 偶数个。

定义 8.7 （可图化与可简单图化）设图 $G=(V, E), V=\left\{v_1, v_2, \cdots, v_n\right\}$ ，称 $\left(d\left(v_1\right), d\left(v_2\right), \cdots\right.$ ， $\left.d\left(v_n\right)\right)$ 为 $G$ 的度数列。给出非负整数列 $d=\left(d\left(v_1\right), d\left(v_2\right), \cdots, d\left(v_n\right)\right)$ ，若存在以 $V=\left\{v_1, v_2, \cdots, v_n\right\}$ 为顶点集的图，以 $d$ 为度数列，则称 $d$ 是可图化的。若存在以 $V=\left\{v_1, v_2, \cdots, v_n\right\}$ 为顶点集的简单图，以 $d=\left(d\left(v_1\right), d\left(v_2\right), \cdots, d\left(v_n\right)\right)$ 为度数列，则称 $d$ 是可简单图化的。

定理 $8.4 d=\left(d_1, d_2, \cdots, d_n\right) \quad\left(d_i \geqslant 0, i=1,2, \cdots, n\right)$ 是可图化的当且仅当 $\sum_{i=1}^n d_i$ 为偶数。
证明：由定理 8.2 可知，必要性是显然的。采用构造性方法进行充分性证明。 $d=\left(d_1, d_2, \cdots\right.$ ， $\left.d_n\right)$ 中有偶数个奇数，设奇数个数为 $2 k(0 \leqslant k \leqslant[n / 2])$ ，奇数分别为 $d_{i_1}, d_{i_2}, \ldots, d_{i_k}, d_{i_{k+1}}, \ldots, d_{i_{2 k}}$ ，用如下方法构造图 $G(V, E)$ ：顶点集 $V=\left\{v_1, v_2, \cdots, v_n\right\}$ ；首先在顶点 $v_{i_r}$ 和 $v_{i_{r+k}}$ 之间连边 $\left\{v_{i_r}, v_{i_{r+k}}\right\}$ ， $r=1,2, \cdots, k_{\circ}$ 若 $d_i$ 为偶数，令 $d_i{ }^{\prime}=d_i$ ；若 $d_i$ 为奇数，令 $d_i{ }^{\prime}=d_i-1$ ；得 $d^{\prime}=\left(d_1{ }^{\prime}, d_2{ }^{\prime}, \cdots, d_n{ }^{\prime}\right)$ 。则 $d_i{ }^{\prime} \geqslant$ 0 且为偶数，$i=1,2, \cdots, n$ ；再在 $v_i$ 处作 $d_i^{\prime} / 2$ 条自环，所得边构成图 $G$ 的边集 $E$ ，则 $G(V, E)$ 的度数列为 $d$ 。所以 $d=\left(d_1, d_2, \cdots, d_n\right)$ 是可图化的。

定理 8.5 设非负整数列 $d=\left(d_1, d_2, \cdots, d_n\right),(n-1) \geqslant d_1 \geqslant d_2 \geqslant \cdots \geqslant d_n \geqslant 0$ ，则 $d$ 可简单图化当且仅当对于每个整数 $r, 1 \leqslant r \leqslant(n-1), \sum_{i=1}^r d_i \leqslant r(r-1)+\sum_{i=r+1}^n \min \left\{r, d_i\right\}$ 并且 $\sum_{i=1}^n d_i$ 为偶数。证明留作习题。

定理 8.6 设非负整数列 $d=\left(d_1, d_2, \cdots, d_n\right), \sum_{i=1}^n d_i$ 为偶数且 $(n-1) \geqslant d_1 \geqslant d_2 \geqslant \cdots \geqslant d_n \geqslant 0$ ，则 $d$ 可简单图化当且仅当 $d^{\prime}=\left(d_2-1, d_3-1, \cdots, d_{d_1+1}-1, d_{d_1+2}, \cdots, d_n\right)$ 是可简单图化的。

证明留作习题。
定义8．8（出度／入度）设 $G$ 是一个有向图，以顶点 $v$ 为起点的弧数称为 $v$ 的出度，记为 $d^{+}(v)$ ；以顶点 $v$ 为终点的弧数称为 $v$ 的入度，记为 $d(v)$ 。

定理 8.7 在有向图中，所有顶点的入度之和等于所有顶点的出度之和。
证明留作习题。
同构概念
一个图的边的长度，边以及边关联的顶点位置变动后，同一个图可以画出不同形状。如图8．4中（a）和（b）就是同一个图。
 ![图片](/uploads/2025-01/0af336.jpg)
 
 定义8．9（图的同构）图 $G=(V, E)$ 和 $G^{\prime \prime}=\left(V^{\prime}, E^{\prime}\right)$ 是同构的，如果存在一个从顶点集 $V$ 到顶点集 $V^{\prime}$ 的双射函数 $f$ ，和一个从边集 $E$ 到边集 $E^{\prime}$ 的双射函数 $g$ ，使得 $G$ 中的边 $e$ 与顶点 $v$和 $w$ 相关联当且仅当 $G^{\prime}$ 中的边 $g(e)$ 与顶点 $f(v)$ 和 $f(w)$ 相关联，则称 $G$ 和 $G^{\prime}$ 是同构的，记为 $G \cong G^{\prime}$ 。函数 $f$ 和 $g$ 称为 $G$ 到 $G^{\prime}$ 的同构函数。

定理8．8 图 $G$ 和 $G^{\prime}$ 同构当且仅当对某一顶点的顺序，它们的邻接矩阵是一样的。
证明：$\Rightarrow$ 假设图 $G$ 和 $G^{\prime}$ 同构，则存在一个从 $G$ 的顶点集到 $G^{\prime \prime}$ 的顶点集的双射函数 $f$ ，和一个从 $G$ 的边集到 $G^{\prime}$ 的边集的双射函数 $g$ ，使得 $G$ 中的边 $e$ 与顶点 $v$ 和 $w$ 相关联当且仅当 $G^{\prime}$ 中的边 $g(e)$与顶点 $f(v)$ 和 $f(w)$ 相关联。令 $v_1, \cdots, v_n$ 是 $G$ 中顶点的排序，令 $A_1$ 是 $G$ 依这个顺序建立起来的邻接矩阵，并且 $A_2$ 是依 $f\left(v_1\right), \cdots, f\left(v_n\right)$ 这个顺序建立起来的 $G^{\prime}$ 的邻接矩阵。则 $A_1=A_2$ 。
$\Leftarrow$ ：证明类似。
推论 8.1 令 $G$ 和 $G^{\prime}$ 是简单图，下列命题是等价的。
（1）$G$ 和 $G^{\prime}$ 是同构的。
（2）存在一个从 $G$ 的顶点集到 $G^{\prime}$ 的顶点集上的双射函数 $f, G$ 的顶点 $v$ 和 $w$ 相邻接当且仅当 $G^{\prime}$ 中的顶点 $f(v)$ 和 $f(w)$ 相邻接。

证明：（1）$\Rightarrow(2)$ ，同构定义。
$(2) \Rightarrow(1)$ 假设存在一个从 $G$ 的顶点集到 $G^{\prime}$ 的顶点集上的双射函数 $f, G$ 的顶点 $v$ 和 $w$ 相邻接当且仅当 $G^{\prime}$ 中的顶点 $f(v)$ 和 $f(w)$ 相邻接。令 $v_1, \cdots, v_n$ 是 $G$ 中顶点的排序，令 $A_1$ 是 $G$ 依 $v_1, \cdots, v_n$ 这个顺序建立起来的邻接矩阵，$A_2$ 是 $G^{\prime}$ 依 $f\left(v_1\right), \cdots, f\left(v_n\right)$ 这个顺序建立起来的邻接矩阵。则 $A_1=A_2$ 。由定理 8．8，命题成立。

有关图的同构，还有一个在 1929 年提出，但还没有解决的Ulam猜想：设 $G_1$ 和 $G_2$ 是两个图，$\left|V\left(G_1\right)\right|=\left|V\left(G_2\right)\right|=n, V\left(G_1\right)=\left\{v_{11}, v_{12}, \cdots, v_{1 n}\right\}, V\left(G_2\right)=\left\{v_{21}, v_{22}, \cdots, v_{2 n}\right\}$ ，且 $G_1-v_{1 i} \cong G_2-v_{2 j}, i, j=1$ ， $2, \cdots, n$ ，则 $G_1 \cong G_2$ 。

有向图同构的定义类似。

定义 $8 . 1 0$（有向图的同构）设 $G=(V, E)$ 和 $G^{\prime}=\left(V^{\prime}, E^{\prime \prime}\right)$ 是两个有向图，若存在双射 $\varnothing: V \rightarrow V^{\prime}$以及双射 $\psi: E \rightarrow E^{\prime}$ ，使得对任何 $u, v \in V,(u, v) \in E$ ，有 $\psi((u, v))=(\varnothing(u), \varnothing(v))$ ，称 $G$ 和 $G^{\prime}$ 是同构的，记为 $G \cong G^{\prime \prime}$ 。

正则图
一般，若图中的每个顶点度数均为 $r$ ，则称为 $r$－正则图。如图 8.5 给出 3 －正则图。
定理 8.9 对于每一个大于 2 的偶数 $n$ ，存在 $n$ 个顶点的 3－正则图。
证明：设 $n$ 是大于 2 的偶数，构造图 $G=(V, E), G$ 的顶点集 $V=\left\{v_1, \cdots, v_n\right\}$ ，边集 $E=\left\{\left\{v_i, v_{i+1}\right\} \mid 1 \leqslant i \leqslant n-1\right\} \cup\left\{\left\{v_n, v_1\right\}\right\} \cup\left\{\left\{v_i, v_{i+n / 2}\right\} \mid 1 \leqslant i \leqslant n / 2\right\}$ ，则 $G$的每一个顶点的度数为 3 。

子图
在进一步讨论图的性质时，研究图的局部结构是相当重要的，现在

图 8.5介绍子图的概念。
 ![图片](/uploads/2025-01/1529cc.jpg)
 
定义 8.11 （子图）设图 $G=(V, E)$ ，若在图 $G^{\prime \prime}=\left(V^{\prime}, E^{\prime}\right)$ 中，$V^{\prime} \subseteq V, E^{\prime} \subseteq E$ 且 $E^{\prime}$ 中边所关联的顶点在 $V^{\prime}$ 中，则称 $G^{\prime}$ 为 $G$ 的子图。若 $V^{\prime}=V, E^{\prime} \subseteq E$ ，则子图 $G^{\prime \prime}=\left(V^{\prime}, E^{\prime}\right)$ 称为图 $G$ 的一个生成子图。

定义 8.12 （导出子图）设图 $G=(V, E), E^{\prime} \subseteq E$ ，以 $E^{\prime}$ 为边集，$E^{\prime}$ 中边的端点全体为顶点集，构成的子图称为由 $E^{\prime}$ 导出的 $G$ 的子图，记为 $G\left(E^{\prime}\right)$ ，又称为 $G$ 的边导出子图。设 $V^{\prime} \subseteq V$ ，以 $V$ 为顶点集，端点均在 $V$ 中的所有边的全体为边集，构成的子图称为由 $V$ 导出的 $G$ 的子图，记为 $G\left(V^{\prime}\right)$ ，又称为 $G$ 的导出子图。

如对于图 8.6 中的（a），（b）是（a）的子图，图 8.6 中的（c）是（a）的导出子图。

![图片](/uploads/2025-01/5668d6.jpg)
 
 
 定义 8.13 （补图）设图 $G=(V, E)$ 是 $n$ 个顶点的任意简单图，从完全图 $K_n$ 中删去 $G$ 的所有边，但保留顶点集 $V$ 所得到的图称为 $G$ 的补图，记为 $\bar{G}$ ，简称为 $G$ 的补。

如图 8.7 中的（a）和（b）互为补图。
一般来说，简单图 $G=(V, E)$ 的补图 $\bar{G}$ 是一个以 $V$ 为顶点集的简单图， $\bar{G}$ 中两个顶点相邻当且仅当这两个顶点在 $G$ 中
（a）
（b）

图 8.7不相邻。从图 $G$ 中删去一个顶点 $v$ 及其关联的边得到的子图，记为 $G-v$ ，或 $G-\{v\}$ 。从图 $G$ 中删去一条边 $e$ 得到的子图记为 $G-e$ 。
 ![图片](/uploads/2025-01/9f4721.jpg)

刷题

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

上一篇：哥尼斯堡（Könisberg）七桥问题

下一篇：路与回路

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