【離散數學】

• path VS trail
  
  
  在一個 graph 中，我們將相鄰的頂點一個個連接起來，形成一個頂點序列，若其中每個頂點只出現一次，這就是一個 path 。
  
  trail 是 path 的推廣， 我們將相鄰頂點一個個連接起來，形成一個頂點序列，若此序列沒有重複使用任一條 edge，則這個序列就是一個 trail。
  
  
  由定義可知，一個 path 必定也是一個 trail ，因為頂點不重複的 path ，其連線必定也不會重複；然而 trail 不一定是個 path ，因為 trail 可能使用了同一個頂點的兩條以上連線，如此一來就會造成該頂點重複。
  
  然而我們可以經由修剪 trail 序列而造出 path 序列，只要將 trail 中重複的頂點之間的所有頂點去掉，例如：a-b-c-d-e-b-f   ->   a-b-f，直到序列中沒有重複的頂點即可，我們可以發現這個過程並沒有改變序列中任何頂點的鄰居，因此序列中相鄰的頂點仍然會是 graph 中相連的頂點。
  
  簡單的說： path 不允許頂點重複； trail 不允許連線重複。
  
  我們還可以發現一些性質：
  
  1. 若一個 graph 可以由一個 path 表示，則 path 頭尾的頂點 degree 為一，而其餘頂點的 degree 皆為二。
  
  2. 而若一個 graph 可表示為 trail ，則 trail 頭尾的頂點 degree 為奇數，而其餘頂點的 degree 為偶數。
  
  這是因為，若頂點不重複出現，那此 trail 就是一個 path，而若 trail 中有重複的頂點，當該點不是頭尾，則每走到這個頂點後，必定會由另一條 edge 走出去，因此該點有偶數 degree；而若該點是頭尾，則 degree 是偶數加上一，因此是奇數。

• circuit and cycle
  
  
  若是 path 最前面的頂點與最後的頂點相鄰，就稱為 circuit。
  若是 trail 最前面的頂點與最後的頂點相鄰，就稱為 cycle 。
  
  
  同上，一個 circuit 必定是一個 cycle，反之則不然。
  
  我們也可以將 cycle 裁剪成一個 circuit。
  
  且我們有以下性質：
  
  1. circuit graph 每一個點皆有 degree 2。
  
  2. cycle graph 每一個點必有偶數 degree。

• graph VS multigraph
  
  
  multigraph 是 graph 的推廣，multigraph 放寬了頂點間連線的限制，允許兩相異頂點間有數條不同的連線，並且允許 (a,a) 這樣的迴圈作為 edge。
  
  
  graph 是一種 multigraph ，反之則否。
  
  我們可以發現，multigraph 與 graph 的差別在於連線變多了，然而在 graph 中定義的許多名詞仍能在 multigraph 中使用，其中 path 用法仍然相同，頂點不能重複，而 trail 則是多了一些連線可以使用，但同一條連線仍然只能用於 trail 中一次( 例如 : 若 (a,b) 有三條，則(a,b)最多能在 trail 中出現三次 。)
  
  若G 是 planar graph ，我們發現，不論是重複增加 G 中已有的連線，或是在增加迴圈，使得 G 變成 multigraph，但只要不加入原本沒有的兩點連線，就不會改變 planar 的性質。

• Euler cycle
  
  
  若是一個 graph 可以畫出一個包含所有連線且經過每一個頂點的 cycle，則我們稱這個 cycle 為 Euler cycle。
  
  
  事實上， Euler cycle 就是一個可以完全表示為 cycle 的 graph。因此若一個 graph 有 Euler graph 則此圖必 connected 。
  
  我們可以將 Euler cycle 視為無論從何處出發，皆能不重複路線走完全程，並回到原點的 graph。

• Euler cycle thm
  
  
  一個 multigraph G 擁有 Euler cycle 若且惟若 G connected 且 G 的每一個頂點皆有偶數的 degree。
  
  
  由以上討論可知，一個 Euler cycle 的任意頂點必有偶數 degree。
  
  而若 graph G 上每個頂點皆有偶數 degree，我們可以由任意頂點出發，構造一個 trail ，並且我們可以持續延長這個 trail ，因為每個頂點皆有偶數的連線，因此若我們走到一個頂點，則必有另一條線走到另一頂點，只有當走回一開始的頂點才有可能阻止這個 trail 繼續延長 (此時事實上已變為 cycle)。
  
  當我們構造出這樣的 cycle C，我們將剩下的 edges 所成的 graph 稱為 G'，則我們可以發現，因為被扣掉的 cycle graph 的每個頂點皆有偶數連線，因此剩餘的 G' 其頂點必也擁有偶數連線，又因為 G 是相連的，C 與 G' 必定有共同點，而我們可以用這共同點再造一個 cycle ，並將這個 cycle 加入 C 中，而 G' 留下的 graph 仍具有 G' 的性質，因為 G 中的連線數量有限，因此我們可以一直重複找出 cycle 並加入 C 中，直到沒有任何連線不在 C 裏頭，如此一來我們就證明了 G 可以找到 C 這個 Euler cycle。
  
  由我們的證明過程，我們可以看到 Euler cycle 一些有趣的細節，例如我們可以將 Euler cycle 視為一個 cycle 上面掛著許多小 cycle，而小 cycle 受又掛著其他小 cycle ...。
  
  
  cor：Euler trail thm
  
  
  一個 multigraph G 擁有 Euler trail 若且惟若 G connected 且 G 只有兩個奇數 degree 的頂點。
  
  
  可將 Euler trail 視為可以由某一點出發，不重複路線走完全程的 graph。而起點與終點正是那兩個擁有奇數連線的頂點。

• Def：Hamilton circuit (path)
  
  
  Hamilton circuit (path) 是包含了 graph 中的每一個頂點的 circuit (path)。Hamilton circuit 是一個 circuit ，因此其中頂點必不重複，且任意頂點皆有兩條連線。而這些性質提供了我們在尋找 Hamilton circuit 時的準則：
  
  
  1. 若一個頂點只有兩條連線，則此兩條連線必在 Hamilton circuit 之中。
  
  2. 若能找到 Hamilton circuit ，則在構造過程中不可能出現未包含所有點的 circuit。
  
  3. 若一個頂點的其中兩條連線已經被加入 circuit 中，則此頂點的其餘連線就可以排除考慮。
  
  每當我們確定某些連線，就可以檢查是否有哪些連線不必考慮或是應該加入。
  
  若在尋找 Hamilton circuit 的過程中違反任一準則，就可斷定此種造法行不通；而若是所有的造法皆會違法準則，即代表我們找不到 Hamilton circuit。