圖論 - 歐拉圖

首先,說明一下一些前置概念:

跡:邊不重復(頂點可以重復)的通道;如果通道首尾相接,這是閉跡。

定義一:

歐拉跡、歐拉圖:設 G=(V,E)為無向圖,包含瞭G的所有頂點、所有邊的(閉)跡稱為歐拉(閉)跡,歐拉閉跡形成的圖稱為歐拉圖。

歐拉定理:

定理1:G是歐拉圖 ⇔ G連通 且 每個頂點的度為偶數。

證明 定理1:

(1)先證明必要性 ⇒,即 要證明:

如果G是歐拉圖 ⇒ G連通 且 每個頂點的度為偶數

證明:因為 G是歐拉圖,則 G包含瞭所有點 所有邊,且還形成瞭閉跡,因閉跡是連通的,故G是連通的,顯然,每個點的度數都是偶數。

(2)再證明充分性 ⇐,即 要證明:

如果G連通 且 每個頂點的度為偶數 ⇒ G是歐拉圖

證明:如果 G連通,且每個頂點的度數為偶數,則 G中必有一個圈 C1,如果C1包含瞭所有的點與邊,則證明完畢。

假設G中不止有圈C1,還有其他的點邊,

則 假設把 C1從圖中拿掉,則因 全圖的頂點度數是偶數,圈C1的頂點度數也都是偶數,故剩餘的圖G2中的頂點度數也都是偶數,所以G2中必定存在圈C2,

以此類推 得出 C3、C4,、……..Ck

以下有歸納法證明由C1~Ck組成的圖是歐拉圖:

因G是連通的,故C1和C2肯定存在公共點,

當G隻能分給成 C1和C2時,則C1和C2組成的圖G是歐拉圖(如下圖所示):a>b>c>d>a>e>c>f>a

C1和C2組成的圖G是歐拉圖

begin{aligned} &那 如果C1 … C_{K-1} 組成的圖G_{K-1}是歐拉圖時,那麼由C1 … C_K 組成的圖G是歐拉圖嗎?\&因圖G是連通的,故 G_{k-1} 和 C_K肯定存在公共點,\​&因圖中每個點的度數都是偶數,故公共點的度數必定是偶數,G_{K-1}和 C_K 能形成一個圈,\&故 由C1…Ck組成的圖是歐拉圖。\end{aligned}

赞(0)