【图论】欧拉图、汉密尔顿图

2021年10月23日

Author: Guofei

文章归类: 8-数据结构与算法，文章编号: 507

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2021/10/23/graph2.html

欧拉回路

【定义】欧拉回路 一个连通图，如果存在一条路，它经过每条边且仅一次，这个路叫做 欧拉路；如果它是个回路，称为 欧拉回路

【定理】 一个无向图 G 有一条欧拉路，当且仅当 G 是连通的，并且有0个或2个奇数度节点。

必要性。如果有一条欧拉路，G 显然就是连通的。假设欧拉路是 v0v1…vnv0v1…vn，那么对于每个中间的点，它每次出现都对应左右两个边，所以它们“带来”偶数个度。两个端点则带来2个奇数度（如果两个端点相同，带来 0 个奇数度）
充分性。
- 如果有 2 个奇数度节点，找这两个节点之间的路径 L1；如果没有奇数度节点，找任意闭合路径 L1。
- G-L1 也构成一个图，其每个节点度必然为偶数，可以找出任意闭合路径L2。
- 如此重复找到 Ln，直到边全部用完。
- 由于是连通图，它们之间有共享节点。
- （得到结论）

对于有向图，有类似结论：有单向欧拉回路当且仅当：

（感觉上面的定理应该从“回路”出发，否则证明和表述会出现）

【定义】汉密尔顿图 一个图，存在一个路径，它经过图上每个节点恰好一次，这个路径叫做 汉密尔顿路径，如果它是回路，叫做 汉密尔顿回路。含有汉密尔顿回路的图叫做 汉密尔顿图

一个图，如果能画在一个平面上，使边不交叉，叫做 平面图

您的支持将鼓励我继续创作！