欧拉图与哈密顿图
欧拉图
def： G = (V,E) 是连通无向图：
- 通过G中所有边一次且仅一次的通路称为欧拉通路
- 通过G中所有边一次且仅一次的回路称为欧拉回路
- 具有欧拉回路的图称为欧拉图
- 具有欧拉通路而无欧拉回路的图称为半欧拉图
判定定理
Th1： 无向连通图G是欧拉图 ⟺ G中所有结点度数均为偶数。
Th2： 无向连通图G为半欧拉图 ⟺ G中只有两个奇度结点。
Th3： 有向连通图G是欧拉图 ⟺ G中每个结点的入度 = 出度。
Th4： 有向连通图G是半欧拉图 ⟺ G中只有两个奇度结点，其中一个结点入度比出度大1，另一个结点入度比出度小1，其余结点入度和出度相等。
例1：下图中，哪个图是欧拉图？哪个是半欧拉图？
| 图 | 结论 | 原因 |
|---|---|---|
| ① 无向图（带中心结点的菱形） | 不是欧拉图，不是半欧拉图 | 有4个以上奇度结点 |
| ② 无向图（正方形） | 是欧拉图 | 所有结点度数均为偶数（每个结点度数为2） |
| ③ 无向图（菱形加横边） | 是半欧拉图 | 恰好只有两个奇度结点 |
| ④ 有向图（正方形，边方向一致） | 是欧拉图 | 每个结点入度 = 出度 |
| ⑤ 有向图（正方形，边方向不一致） | 不是欧拉图，不是半欧拉图 | 奇度结点超过两个，不满足半欧拉图条件 |
哈密顿图
def： G = (V,E) 无向图或有向图。
- 若G中有一条包含所有结点一次且仅一次的回路，称该回路为哈密顿回路，称图G为哈密顿图。
- 若G中有一条包含G的所有结点的通路，则称该通路为哈密顿通路，具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。
例：圆桌会议安排
题目： 有7人，A会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲德语和意大利语，F会讲法语、日语和俄语，G会讲法语和德语。问能否将他们沿圆桌安排坐成一圈，使每个人都能与两旁的人交谈。
解： 以每个人为结点，若两人有共同语言则连边：
A
/ \
B C
/| |\
D | | E
\| |/
F---G哈密顿回路：A → B → D → F → G → E → C → A
∴ 可以按该回路安排座位，每人都能与两旁的人交谈。
例：求下图中结点u到v的最短路径（Dijkstra算法）
图的结构：
a ---3--- b
/ \ \
2 \ 2
/ 1 \
u \ v
\ \ /
1 d---2-/
\ /
c--3-边的权重：
- u-a = 2，u-c = 1
- a-b = 3，a-d = 1
- b-v = 2
- c-d = 3
- d-v = 2
Dijkstra算法步骤：
初始化：dist(u)=0，其余结点=∞，已确定集合 S={}
第1步： 取dist最小的未确定结点 u（dist=0），加入S
更新邻居：
- dist(a) = 0+2 = 2
- dist(c) = 0+1 = 1
S = {u}，当前dist：a=2, b=∞, c=1, d=∞, v=∞
第2步： 取dist最小的未确定结点 c（dist=1），加入S
更新邻居：
- dist(d) = 1+3 = 4
S = {u, c}，当前dist：a=2, b=∞, c=1, d=4, v=∞
第3步： 取dist最小的未确定结点 a（dist=2），加入S
更新邻居：
- dist(b) = 2+3 = 5
- dist(d) = min(4, 2+1) = 3 ✓ 更新
S = {u, c, a}，当前dist：a=2, b=5, c=1, d=3, v=∞
第4步： 取dist最小的未确定结点 d（dist=3），加入S
更新邻居：
- dist(v) = 3+2 = 5
- dist(b) = min(5, 3+?) —— d与b无直接边，不更新
S = {u, c, a, d}，当前dist：a=2, b=5, c=1, d=3, v=5
第5步： 取dist最小的未确定结点 b 或 v（dist均=5），取 b，加入S
更新邻居：
- dist(v) = min(5, 5+2) = 5 不更新
S = {u, c, a, d, b}，当前dist：b=5, v=5
第6步： 取 v（dist=5），加入S，算法结束。
结论： u到v的最短路径长度为 5，路径为：
u → a → d → v（2+1+2=5）
或 u → c → d → v（1+3+2=6）❌
∴ 最短路径为 u → a → d → v，长度为 5。