科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
数学分析
复变函数
离散数学
实变函数
数论
群论
高中物理
词条搜索
科数
试题
高中数学
高数
线代
more
你好
游客,
登录
注册
在线学习
拓扑学
欧拉图与哈密尔顿图
欧拉图
最后
更新:
2023-10-27 09:50
查看:
266
次
高考专区
考研专区
公式专区
刷题专区
词条搜索
欧拉图
**引言** 柯尼斯堡七桥问题是《图论》中的著名问题。这个问题是基于一个现实生活中的事例:当时东普鲁士柯尼斯堡市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?  欧拉在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$ 是欧拉图。 
上一篇:
没有了
下一篇:
哈密顿图
本文对您是否有用?
有用
(
0
)
无用
(
0
)
制作不易,如果您喜欢本站,也欢迎
赞助本站
。
初中数学
高中数学
高中物理
高等数学
线性代数
概率论与数理统计
复变函数
离散数学
实变函数
数学分析
数论
群论
纠错
高考
考研
关于
赞助本站
下载
科数网是专业专业的数学网站。