最后更新: 2025-01-21 17:11 查看: 58 次反馈刷题

欧拉图

## 欧拉图
定义7-4.1 给定无孤立点的图G，若存在一条路，经过所有边一次且仅一次，称为欧拉路；若存在经过图中所有边一次并且仅一次的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图
具有欧拉路而无欧拉回路的图称为半欧拉图
定义7-4.2 给定有向图G，通过图中每边一次且仅一次的一条单向路(回路)，称作单向欧拉路(欧拉回路)。

定理7－4．1 无孤立点的无向图G具有一条欧拉路，当且仅当 $G$ 是连通的，且有零个或两个奇数度结点。

证明 若 $G$ 是平凡图，结论显然成立。
若 G 为非平凡图，设 $G$ 是 $m$ 条边的 n 阶无向图，结点集 $V$ $=\left\{v_1, v_2, \ldots, v_n\right\}$ 。
必要性。 $G$ 中有欧拉路 L 时，由于图中无孤立点，当路L经过所有边时也经过了所有的点，故G连通。

对任意一个不是端点的结点 $v_i$ ，在欧拉路中每当 $v_i$ 出现一次，必关联两条边，贡献2度，故deg $\left(v_i\right)$ 必是偶数。若起点和终点重合，则G中没有奇数度点；若起点不同于终点，则两个端点是奇数度的点，其它都是偶数度的结点。

证明 充分性。若G中每个结点都是偶数度结点，因 $G$ 连通，所以 $G$ 中至少含有一个基本回路 $C_1$ ，从 $G$ 中删除 $C_1$ 上的各边得到子图 $G_1$ ，若 $G_1$ 中仍然有边，由 $G_1$ 每个结点仍为偶数度结点，则可得基本回路 $C_2$ ，且使得 $C_1$ 与 $C_2$ 有一个公共结点。
按照此法，直到删去G中的所有边。于是得到一系列基本回路 $C 1, C 2, \ldots, Cm$ ，且 $U _{ c } c _{ i }$ 与 Cj 有一个公共结点，则由 $C 1, C 2, \ldots, Cm$ 构成 ${ }^{-1}$ 一个欧拉回路。
由于本定理是一个充要条件，所以不仅给出了欧拉图的判定方法，而且也给出了构造欧拉回路的方法。

## 推论
－连通无向图 $G=<V, E>, u, ~ v \in V$ 且 $u \neq v, u$ 与 $v$ 之间存在欧拉路当且仅当 $G$ 中仅有两个奇数度结点。
－证明 对 $G$ 加上一条边 $[u, v]$ 得到新图 $G_1, G$ 中 $u$ 和 $v$之间存在欧拉路 $\Leftrightarrow G_1$ 中有欧拉回路 $\Leftrightarrow G_1$ 中每个结点为偶数度结点 $\Leftrightarrow G$ 除 $u, ~ v$ 外其余结点均为偶数度结点 $\Leftrightarrow G$ 仅有 $u$ 和 $v$ 为奇数度结点。

例7-4.1 判断图是否是(半)欧拉图？
 ![图片](/uploads/2025-01/6ecbf2.jpg)
 
 例7-4.2 判断下图能否一笔画出。
  ![图片](/uploads/2025-01/d46166.jpg)
  
  例7-4.3 寻找欧拉回路
   ![图片](/uploads/2025-01/c9d425.jpg)
   
   
   定理7-4.2 有向图G具有一条单向欧拉回路，当且仅当它是连通的，且每个结点入度等于出度。有向图G具有一条单向欧拉路，当且仅当它是连通的，且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个节点的入度比出度大1，另一个结点的入度比出度小1。

例7-4.4 判断以下有向图是否有欧拉回路、欧拉路。
 ![图片](/uploads/2025-01/62c71f.jpg)
 解：(1)无欧拉通路，(2)有欧拉通路，无欧拉回路，(3)有欧拉回路。

刷题

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

上一篇：邻接矩阵

下一篇：汉密尔顿图

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