Question

Hamilton Circuit（Hamilton Cycle）

每一点刚好经过一次的路线，起点和终点相同。可能有许多种，也可能不存在。

Hamilton Path

每一点刚好经过一次的路线，起点和终点不相同。可能有许多种，也可能不存在。

Travelling Salesman Problem

一个周游各国的商人，他想去所有不同的城市买卖东西。商人打算从其中一个城市出发，各个地方刚好经过一次、只能经过一次，回到原城市。请规划出距离最短的路线，以及算出距离。

有时候走回头路会比较快，然而商人就是不想这麽做。

这个问题其实就是找到权重最小的 Hamilton Circuit。

找到一个 Hamilton Circuit

判断是否存在 Hamilton Circuit、找到一个 Hamilton Circuit 是 NP-complete 问题，找到一个权重最小的 Hamilton Circuit 是 NP-hard 问题，目前尚未出现有效率的演算法。

以 Backtracking 穷举所有地点排列方式，一一判断是否可行，时间複杂度为 O(V!)。运用“ Dynamic Programming ”可降低为 O(2^V * V^2)。

Vehicle Routing Problem

车辆路径问题

给定起点，除了起点以外，每一点刚好经过一次的路线。

一个仓库（物流中心）、数台货车（有承载限制）。另外有几位客户，分散各处，各自需要某些商品，该如何规划配送路线、配送车次，使得油耗最少？

Euler Circuit

Seven Bridges of Königsberg

“七桥问题”。有一说是当地居民的休閒活动就是游览那七座桥，大家都在尝试找一条可以经过七座桥各一次，然后回到原处的路线。这活动蔚为风潮，许多数学家听到这个消息后，也致力于解决这个问题，却都无疾而终。这个问题也传到了数学家 Euler 的耳中，最后他想出了一个漂亮的证法。

另外还有一个童话版本：有天国王想召王宫贵族一起出去散散心，游览他的庭园。国王他打算从他的城堡出发，看一看他的庭园花草，以及在他庭园裡的七座桥上散散步。然后回到城堡裡去。由于天气一定很好、阳光一定很强，届时出发后绝不要在同一座桥上反反覆覆的走来走去，一直晒太阳，看同样的风景，那多烦闷。

国王于是下令叫他的臣子们好好的规划一下出游路线，每一座桥都要参观到，而且绝不能让大家走同样的桥两次。臣子们想了很久，却连一条路线都规划不出来，国王只好召来聪明的数学大臣 Euler 来解决这个问题。Euler 奉旨后，自行在家没日没夜的闭关了三天，终于解决了这个问题：他证明出路线不存在！

Euler 当然要能向国王解释路线为何不存在，要不然国王肯定气得叫人把他吊起来。Euler 想到，无论陆地和桥的形状、距离、位置是如何，要找出合适的游览路径，只跟桥与陆地如何连接有关係。Euler 首先把庭园的地图，简化成我们在图论中所看到的“图”，圆形（点）就是陆地，线（边）就是桥。Euler 发明的这张“图”包含了充分的连接资讯，他也是第一个使用“图”来解决问题的数学家。

接著 Euler 想到，如果每一座桥只能穿过一次，那麽一座桥就成了去而不回的单行道。然后，对图上的某一个点来看，一旦从某座桥进入了一次，就要从另一座桥走出去一次，而不会一直停留在某个点上——这跟从哪裡走来、怎麽走来、哪裡出去、怎麽出去无关。所以，只要看到有个点有奇数个边，也就是有块陆地有奇数座桥，就表示有这块陆地有一条桥会让国王走得过去、却走不出来，此时就得重複走一座桥、或不走这座桥——这就代表著国王的游历路线不存在。

不知道国王后来还有没有出游？不过 Euler 的这个证明过程倒是出名了。数学家们为了纪念 Euler 的这项贡献，把一笔划走完所有边一次后恰好回到起点的路线，称作 Euler Tour，Tour 即是游览的意思；至于 Euler Circuit 则是另一个比较精准的用词。

一笔划问题

给定一个图案，要如何一笔划完成？留给读者解决！

Euler Circuit

每条边刚好经过一次的路线，起点和终点相同。可能有许多种，也可能不存在。

一张图存在 Euler Circuit 的条件是：

无向图：每个点都是偶数条边。相互连通。
有向图：每个点的出边与入边一样多。相互连通。

Euler Trail

每条边刚好经过一次的路线。可能有许多种，也可能不存在。Euler Circuit 也算是 Euler Trail。

Euler Circuit 随意删除一条边，形成 Euler Trail。Euler Trail 的起点与终点补上一条边，形成 Euler Circuit。

一张图存在 Euler Trail 的条件是：

无向图：恰有零个点或两个点是奇数条边。相互连通。
有向图：恰有一点出边比入边多一条（作为起点），
　　　　恰有一点入边比出边多一条（作为终点），
　　　　其他的点出边与入边一样多。相互连通。
　或者，每个点的出边与入边一样多（任选两点作为起点与终点）。相互连通。

无向图找出一个 Euler Circuit（Hierholzer's Algorithm）

一个 Euler Circuit，在某点相交，可拆成两个 Euler Circuit。

两个 Euler Circuit，可在某点相接，合成一个 Euler Circuit。

大的 Euler Circuit 可拆成小的，小的可接成大的——自然想到 Divide and Conquer。

在图上随意走一圈。未及之处，一定是一个（或数个）Euler Circuit。

Divide ：在图上随意走一圈。
Conquer：其馀部份递迴下去。
Combine：其馀部分的 Euler Circuit 们，衔接到随意走的那一圈。

图的资料结构为 adjacency matrix，时间複杂度是 O(V^2 + E)。图的资料结构为 adjacency list，时间複杂度是 O(V+E)。

有向图找出一个 Euler Circuit

有向图的情况下，就将每个点的入边与出边分开来看，如果入边与出边的数量相等，表示有路可走。

除此之外，都与无向图相同。

找出所有 Euler Circuit

可以採用 backtracking。无法在多项式时间内完成。

UVa 117 291 302 10054 10129 10441 10506 10596 10735

Chinese Postman Problem

中国邮差问题

邮差叔叔走访每条大街小巷，让家家户户都收到信。

给定一张图，找出一条环状路线，图上每条边至少经过一次，并且距离最短。

无向图演算法

http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.4.html

1. 先判断整张图是否为一个强连通分量，否则无解。
2. 找出图上所有奇点，一定是偶数个。
3. 找出所有奇点点对之间的最短路径长度。
4. 把这些奇点做最小权匹配，权重採用刚才算的最短路径长度。
5. 把匹配边加在原图上，再找欧拉环，即得中国邮差路径之权重。
6. 将匹配边改成其代表的最短路径，即得中国邮差路径。

时间複杂度为六项步骤总和。各条匹配边所代表的最短路径，绝对不会重叠。

ICPC 4039

有向图演算法

1. 先判断整张图是否为一个强连通分量，否则无解。
2. 找出图上所有出边数不等于入边数的点。
3. 于上述找到的点，找出所有点对之间的最短路径长度。
4. 令 d(x) 为 x 点出边与入边的数量差。
   出边多于入边的点 x，建立 d(x) 份，放在 X 侧。
   出边少于入边的点 y，建立 d(y) 份，放在 Y 侧。
   最后建立 X 侧到 Y 侧的边，权重採用刚才算的最短路径长度。
   算最小权二分匹配。
4. 合理的做法是建立最小权最大流模型：
   把出边多于入边的点 x，放在 X 侧。拉一条源点到 x 点的边，权重为零，容量为 d(x)。
   把出边少于入边的点 y，放在 Y 侧。拉一条 y 点到汇点的边，权重为零，容量为 d(y)。
   最后建立 X 侧到 Y 侧的边，权重採用刚才算的最短路径长度，容量为无限大。
   算最小权最大流。
5. 把匹配边加在原图上，再找欧拉环，即得中国邮差路径之权重。
6. 将匹配边改成其代表的最短路径，即得中国邮差路径。

时间複杂度为六项步骤总和。

简单来说：Minimum Cost Flow，每条边容量下限皆为一。