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

欧拉图和半欧拉图

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

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

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：二分图

下一篇：哈密顿图

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