1.3節(jié) Hamilton Cycles and Euler Circuits 哈密頓圈和歐拉回路

本篇簡要的介紹了概念和相關(guān)定理。首先明確一下，下面討論有三種圖：無向圖(simple graph)，有向圖(directed graph)以及（有向）混合圖(directed multigraph)，混合圖允許自己指向自己的邊(loop)?；旌蠄D的基圖(underlying graph)就是刪去了這些邊的有向圖。

1. 定義：

如果圖G中的一個(gè)路徑包括每個(gè)邊恰好一次，則該路徑稱為歐拉路徑(Euler path)。如果一個(gè)回路是歐拉路徑，則稱為歐拉回路(Euler circuit)；

如果G中的圈C恰好經(jīng)過每一個(gè)頂點(diǎn)一次，則稱圈C是一個(gè)哈密頓圈(Hamilton Cycles)。

2. 定理：

????1. 眾所周知，歐拉回路的研究始自Konigsberg七橋問題。Euler指出，(TH12) 連通圖G有歐拉跡iff x\y為唯二奇度頂點(diǎn)，以及G為歐拉圖iff頂點(diǎn)全為偶數(shù)。對有向圖（混合圖），則需要入度等于出度。這一定理可用割圈的方式證明。事實(shí)上，每一個(gè)歐拉回路都是一些不相交之圈的并。

????2. 關(guān)于Hamilton圈的TH11指出，Kn能被分割成不相交的Hamilton圈 iff n 是奇數(shù)，能被分割成不相交的Hamilton路 iff n是偶數(shù)。這一定理可以歸納的證明。

????3. 下面介紹TH13。這一定理對入度等于出度的混合歐拉圖適用。對圖G有如下等式成立： s(G)? = ti(G)Π(d+(vj)-1)!

????其中，s(G)是G歐拉回路的個(gè)數(shù)，ti(G)是朝向(oriented towards)i的生成樹（OST）的個(gè)數(shù)(明顯，t1 = t2 = ... = tn)。朝向i的生成樹定義為：For every j!=i, the unique path from vi to vj is oriented towards vi.也就是以下三點(diǎn)：每個(gè)j出度1，i出度0，沒有有向圈。

????證明這一定理，構(gòu)造T，邊為e2,...,en,其中ei是一條歐拉跡S中最后一次離開vi的那條邊。不難證明T是OST。映射Π(S)=T，即求|Π-1(T)|。用簡單的組合知識即得。

????4. TH14：G是無限多邊的連通混合圖，則G有一條雙向歐拉跡 iff 滿足：1.E可數(shù) 2. 邊的度是偶數(shù)或無限大 3. 每個(gè)無限邊的子圖G'(V,E'),?G -?E'有至多兩個(gè)無限連通分量。（進(jìn)一步地，若G‘各點(diǎn)均為偶數(shù)度，G?- E'有一個(gè)連通分量）。