注意
當強調不重複邊時，常用circuit。
不重複點時，用cycle來敘述。
Path
滿足條件, 原點不是終點
Circuit(Cycle)
滿足條件, 原點等於終點
Euler
cycle(circuit): 每條路都走過一遍, 原點等於終點。
path: 每條路都走過一遍，原點不等於終點。
如何判斷是不是Euler 迴路/路徑
\( V \)為所有點的集合，\( E \)為所有邊的集合。
假設為無向簡單/多重圖。
每個點都有他的degree(分支度)，
每個點需要是偶數的分支度，且為連通圖，才能夠形成euler 迴路(circuit)。
點degree含0個或2個奇數其他點的degree為偶數，且為連通圖，euler路徑(path/trail)。
假設為有向簡單/多重圖。
每個點inner degree = outer degree，這裡用\( id(v) = od(v),\; v\in V \)代表，且為強連通圖，才能夠形成euler 迴路(circuit)。
故事
Konigsberg的七橋問題
一筆劃問題(all of degree of vertex are even.(circuit))(otherwise, path)
Hamilton
cycle(circuit): 每個點只走過一遍(除了原點和終點),
因為原點就是終點。
path: 每個點只走過一遍，且不重複。
wiki
故事
五邊形構成的十二面體, 每個點當作一個城市,
是否能找到一個迴路, 每個城市都走過一遍, 然後回到原來的城市。(也就是原來起點的城市會走兩次)
旅行銷售員問題(travelling salesman problem)(此問題邊上是有權重的)
TSP art
問題
Hamilton cycle 目前沒有很好的演算法去判斷 (為NP-complete問題)(time complexity 為指數)。