最后更新: 2025-01-22 09:23 查看: 119 次反馈同步训练

欧拉图和半欧拉图

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

其他版本
【高等数学】欧拉方程【高中数学】附录：平面的欧拉公式【高中数学】欧拉公式与推导【复变函数与积分变换】欧拉公式的证明

免费注册看余下 50%

非VIP会员每天15篇文章，开通VIP 无限制查看

上一篇：二分图

下一篇：哈密顿图

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