科数网
学习首页
高中数学
高中物理
微积分
线性代数
概率论
赞助
在线教程
图论
欧拉图与哈密尔顿图
欧拉图
最后更新:
2023-10-27 09:50
查看:
216
次
下载
编辑本文
科数网
欧拉图
**引言** 柯尼斯堡七桥问题是《图论》中的著名问题。这个问题是基于一个现实生活中的事例:当时东普鲁士柯尼斯堡市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍? ![图片](/uploads/2023-10/d1cba6.jpg) 欧拉在1735年提出,并没有方法能圆满解决这个问题,他更在第二年发表在论文《柯尼斯堡的七桥》中,证明符合条件的走法并不存在,也顺带提出和解决了一笔画问题。 ![图片](/uploads/2023-10/6cc1c0.jpg) ## 定义 欧拉路径:图 $G$ 上有一条经过所有顶点、所有边的简单路径 (边不重复,点可以重复) 欧拉回路:图 $G$ 上有一条经过所有顶点、所有边的简单回路(边不重复,点可以重复) 欧拉图: 有欧拉回路的连通无向图 欧拉有向图: 有欧拉回路的连通有向图 ## 定理 定理1:设 $G$ 是连通无向图。 $G$ 是欧拉图,当且仅当 $G$ 的结点都为偶结点。 定理2: 设 $G=\langle V, E, \varphi\rangle$ 为连通无向图,且 $v_1, v_2 \in V$ ,则 $G$ 有一条从 $v_1$ 至 $v_2$ 的欧拉路径当且仅当 $G$ 恰有两个奇结点 $v_1$ 和 $v_2$ 。 例1:下图中,(a)是欧拉图,也是欧拉回路,(c)是欧拉路径,(b)两者都不是 ![图片](/uploads/2023-10/eafb6e.jpg) 定理3: 设 $G$ 为弱连通有向图。 $G$ 是欧拉有向图,当且仅当 $G$ 所有结点的出度等于入度。 定理4: 设 $G=\langle V, E, \varphi\rangle$ 为弱连通有向图,且 $v_1, v_2 \in V$ 。 $G$ 有一条从 $v_1$ 至 $v_2$ 的欧拉路径,当且仅当 $d_G^{+}\left(v_1\right)=d_G^{-}\left(v_1\right)+1 , d_G^{-}\left(v_2\right)=d_G^{+}\left(v_2\right)+1$ ,且对 $G$ 的其他结点 $v_i$ 有 $d_G^{+}\left(v_i\right)=d_G^{-}\left(v_i\right)$ 。 例2:下图中,(b)是欧拉有向图,也是欧拉回路,(c)是欧拉路径,(a)两者都不是 ![图片](/uploads/2023-10/58f0ce.jpg) PS:现在返回来看哥尼斯堡七桥问题,由于哥尼斯堡七桥问题不是欧拉图,不存在欧拉回路,所以哥尼斯堡七桥问题无解。 定理5: 如果 $G_1=\left\langle V_1, E_1\right\rangle$ 和 $G_2=\left\langle V_2, E_2\right\rangle$ 是可运算的欧拉图,则 $G_1 \oplus G_2$ 是欧拉图。 证明:设 $v$ 是 $G_1 \oplus G_2$ 的任意结点,于是可能出现 2 种情况: (1) 若 $v \in V_1 \wedge v \notin V_2$ 或 $v \in V_2 \wedge v \notin V_1$ ,则 $v$ 是 $G_1 \oplus G_2$ 的偶结点。 (2) 若 $v \in V_1 \wedge v \in V_2 , G_1$ 和 $G_2$ 有 $k$ 条公共边和 $l$ 个公共自圈与 $v$ 关联,则 $$ d_{G_1 \oplus G_2}(v)=d_{G_1}(v)+d_{G_2}(v)-2(k+l) $$ 显然 $v$ 是 $G_1 \oplus G_2$ 的偶结点。 因此, $G_1 \oplus G_2$ 是欧拉图。 ![图片](/uploads/2023-10/db31d5.jpg)
上一篇:
没有了
下一篇:
哈密顿图
本文对您是否有用?
有用
(
0
)
无用
(
0
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,也欢迎
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记