欧拉图与哈密顿图
01 欧拉图
(1)问题提出：
哥尼斯堡是18世纪东普鲁士的一个城市，普雷格尔河流经过该市，将哥尼斯堡分为四个部分：两岸和两个河心岛，河上共有7座桥将这些陆地相连。
问：游人从任一地点出发，怎样才能做到穿过每座桥一次且仅一次后又返回到原出发地？
1736年欧拉（Euler）用图论方法解决了“哥尼斯堡七桥问题”。
(2)转化为图论问题：
用节点表示陆地，用边表示桥。在图中寻找一条穿程于每条边一次的回路。
(3)定义：
-
欧拉道路
设G是一个无向图，包含G的每条边的简单道路称为欧拉道路；（即：穿程于图G的每条边一次且仅一次的道路） -
欧拉回路
包含G的每条边的简单回路称欧拉回路；（即：穿程于图G的每条边一次且仅一次的回路） -
欧拉图
具有欧拉回路的图称为欧拉图。
(4)欧拉道路和欧拉回路的判定：
- 定理：连通图G是欧拉图，当且仅当G不含奇数度节点。
note：节点度是指和该节点相关联的边的条数，又称关联度。
- 证明
(4.1)必要性
因为：设G是欧拉图，则存在一条包含每条边的简单回路C，当沿回路一个方向前进时，必定沿一条边进入一个节点，再沿另一条边从这个节点出去，即每个节点都和偶数条边关联。
所以：G中不含奇数度节点。
(4.2)充分性
设G的节点都是偶数度，则G含有回路。
假设C是其中一条包含G中边数最多的简单回路。
(1)若C包含了G中所有的边，则C为欧拉回路，G是欧拉图。结论成立。
(2)若C没有包含G中所有的边，则G-E(C)是删边子图，仍然都是偶数度节点。在G-E(C)中必还有简单回路，设为C_hat。
因为：G是连通的，C_hat和C至少会在某一点u连接，则由C和C_hat构造出G的一条包含边数比C多的回路，与假设矛盾。
所以：G中包含边数最多的回路必定是欧拉回路。
即不含奇数度节点的连通图是欧拉图。
note：——————充分必要条件——————
假设A是条件，B是结论，设C、D分别为A、B所描述对象的集合，则有下列定义和推论：
- 由A可以推出B，由B可以推出A，则A是B的充分必要条件（此时C=D）；
- 由A可以推出B，由B不可以推出A，则A是B的充分不必要条件（此时C⊂D）；
- 由A不可以推出B，由B可以推出A，则A是B的必要不充分条件（此时D⊂C）；
- 由A不可以推出B，由B不可以推出A，则A是B的既不充分也不必要条件（此时C∉D, D∉C）；
(5)有向图的欧拉回路和欧拉道路判定：
- 定理：
(1)连通有向图G含有有向欧拉回路，当且仅当G中每个节点的入度等于出度。
(2)连通有向图G含有有向欧拉道路，当且仅当G中最多有两个节点入度不等于出度，这两个节点中，一个节点的入度数比出度数大1，另一个节点的出度数比入度数大1。
(6)案例：
(6.1)判断图：
一个图能一笔画完回到起点 ↔ 该图为欧拉图
- 一个图能从一点出发一笔画完到另一个节点 ↔ 图中存在一条欧拉道路
(6.2)应用举例：
一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又回到邮局，问怎样走使全程的路径最短？
分析：
(1)如果所作图是欧拉图，任何一条欧拉回路满足条件；
(2)如果所作图不是欧拉图，寻找的闭圈道道路中必定会重复通过某些边。
02 哈密顿图
(1)问题提出：
Hamilton发明一种游戏，周游世界。用12面体的20个顶点代表世界上的20个城市，每条棱表示城市间的一条路线。
问：能否从任何一座城市出发，沿棱行走，通过每座城市一次且仅一次，最后又回到出发点？
(2)转换为图论问题：
判断连通图中是否存在一个包含全部节点的圈。
(3)定义：
-
哈密顿道路
设G是一个连通图，若G中存在一条包含全部节点的基本道路，则称这条道路为G的哈密顿道路。（即：穿程于G的每个节点一次且仅一次的道路） -
哈密顿回路
若G中存在一条包含全部节点的圈（基本回路），则称这个圈为G的哈密顿回路（或哈密顿圈）。（即：穿程于G的每个节点一次且仅一次的回路） -
哈密顿图
含有哈密顿圈的图称为哈密顿图。
(4)判断条件：
- 定理：
(4.1)必要条件：若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分枝的个数。
(4.2)充分条件：设G=(V,E)是一个无向简单图，|V|=n. n≥3. 若对于任意的两个顶点u，v∊V，d(u)+d(v) ≥n，那么, G是哈密尔顿图。此条件由美国图论数学家奥勒在1960年给出。
寻找哈密顿路径是一个典型的NPC问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的。
寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为\(O(n×n!)\)暴力搜索。利用状态压缩动态规划，可以将时间复杂度降低到\(O(2^n×n^3)\)。