科数网知识库
首页
目录
知识库
离散数学 Discrete mathematics
图论
欧拉图
欧拉图
日期:
2023-10-27 09:50
查看:
41
次
更新
导出Word
**引言** 柯尼斯堡七桥问题是《图论》中的著名问题。这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？  欧拉在1735年提出，并没有方法能圆满解决这个问题，他更在第二年发表在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题。  ## 定义 欧拉路径：图 $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)两者都不是  定理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)两者都不是  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$ 是欧拉图。 
上一篇：
没有了
下一篇：
哈密顿图
知识库是科数网倾心打造的大型数学知识网站，欢迎各位老师、数学爱好者加入,联系微信 18155261033， 制作不易，也欢迎
赞助
本站。