最后更新: 2025-01-22 09:23 ● 参与者查看: 16 次纠错分享参与项目词条搜索

欧拉图和半欧拉图

图论起源于哥尼斯堡七桥问题。哥尼斯堡七桥问题的论述是＂从任意一地点出发，通过每座桥一次且仅仅一次，最后回到原地，这是否可能？＂此前我们已经用图表示哥尼斯堡：顶点表示岛屿和河的两岸，边表示桥，如此前给出的图8．1 所示。

这样，哥尼斯堡七桥问题的论述就改为＂从图8．1中任意一顶点出发，通过每条边一次且仅仅一次，最后回到原出发顶点，这是否可能？＂这也就是如何一笔画的问题。由此，我们引出欧拉图的定义。

定义8．24（欧拉图）若图 $G$ 中具有一条包含 $G$ 中所有边的闭链，则称它为欧拉闭链，

简称为欧拉链，称 $G$ 为欧拉图。若图 $G$ 中具有一条包含 $G$ 中所有边的开链，则称它为欧拉开链，称 $G$ 为半欧拉图。

显然，欧拉图除孤立点以外是连通的，而孤立点的有无并不影响对欧拉图的讨论，因此以后不妨设欧拉图是连通的。

定理8．14 $G$ 是连通图，则 $G$ 是欧拉图当且仅当 $G$ 的所有顶点都是偶顶点。
证明：$\Rightarrow$ 因为 $G$ 是欧拉图，所以 $G$ 有欧拉链（ $v_0, e_1, v_1, e_2, \cdots, e_i, v_i, e_{i+1}, \cdots, e_k, v_k$ ），$v_0=v_k$ ，其中顶点可以重复出现，而边不重复出现。所以对于任意 $v_i$ ，每当出现 $v_i$ ，它关联两条边，而 $v_i$ 可以重复出现，所以 $d \left(v_i\right)$ 是偶数。
$\Leftarrow: ~$ 若图 $G$ 是连通的，则可以构造一条欧拉链。
（1）从任意一顶点 $v_0$ 开始，取关联于 $v_0$ 的边 $e_1$ 到 $v_1$ ，每边仅取一次。因为所有顶点为偶数度，并且 $G$ 是连通的，所以可以继续取关联与 $v_1$ 的边 $e_2$ 到 $v_2, \cdots$ ，直到回到顶点 $v_0$ ，得到一条闭链 $h:\left(v_0, e_1, v_1, \cdots, v_0\right)$ 。
（2）若 $h=G$ ，则 $G$ 即为欧拉图；否则 $G-h=h^{\prime}$ 不是空集，$h^{\prime}$ 中顶点度数均为偶数，又 $G$ 是连通的，$h^{\prime}$ 与 $h$ 必有一个顶点 $v_i$ 重合。在 $h^{\prime}$ 中从 $v_i$ 出发重复（1），得到一条闭链 $h 2:\left(v_i, e_1{ }^{\prime}, v_1{ }^{\prime}, \cdots\right.$ ， $v_i$ ）。
（3）若 $h \cup h^{\prime}=G$ ，则 $G$ 即为欧拉图：$\left(v_0, e_1, v_1, \cdots, v_i, e_1{ }^{\prime}, v_1{ }^{\prime}, \cdots, v_i, \cdots, v_0\right)$ ；否则，重复（2）直至构成一条包含 $G$ 中所有边的闭链。

定理8．15 $G$ 是连通图，则 $G$ 是半欧拉图当且仅当 $G$ 中有且仅有两个奇顶点。
证明：证法类似定理 8.14 的证明，仅步骤（1）从一个奇顶点 $v_0$ 开始，取关联于 $v_0$ 的边 $e_1$到 $v_1, \cdots$ ，直到另一个奇顶点 $v_i$ 为止，得到一条开链 $h_1$ 。其他步骤类同定理 8.14 的证明。最后构造一条包含 $G$ 中所有边的开链为止，此开链即为欧拉开链，$G$ 就是半欧拉图。

对于哥尼斯堡七桥问题，由于 4 个顶点的度数都是奇数的，不可能有欧拉链。
定理 8.14 和定理 8.15 不但可以用来判别一个图能否一笔画，并且给出一笔画的方法。
定理8．16 $G$ 是连通图，则 $G$ 是欧拉图当且仅当 $G$ 是若干条边不相重的回路之并。
证明留作习题。
欧拉有向图
在讨论有向图时，我们也给出类似于欧拉图和半欧拉图的充要条件。
定义8．25（欧拉有向图）若连通有向图 $G$ 中具有一条包含 $G$ 中所有弧的有向闭链，则称该闭链为欧拉有向链，称 $G$ 为欧拉有向图。若图 $G$ 中具有一条包含 $G$ 中所有弧的有向开链，则称该开链为欧拉有向开链，称 $G$ 为半欧拉有向图。

类似定理 8.14 和定理 8.15 的证明，可以证明下面的定理。
定理8．17 $G$ 是连通有向图，则 $G$ 是欧拉有向图当且仅当 $G$ 的每个顶点 $v$ ，有 $d^{+}(v)=d^{\prime}(v)$ 。
定理8．18 $G$ 是连通有向图，则 $G$ 是半欧拉有向图当且仅当 $G$ 中恰有两个奇顶点，其中一个奇顶点的入度比出度大 1 ，另一个奇顶点的出度比入度大 1 ，而其他顶点的出度等于入度。

由上述讨论可知，欧拉图等价于一笔画的问题：从一点出发，在一笔内画尽所有的边，且每条边只画一次，最后回到出发点。我们可以推出，如果在一个图中奇顶点个数为 $2 K$ 个，则该图是 $K$ 笔画的。证明留作习题。

上一篇：二分图

下一篇：哈密顿图

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