【文章內容簡介】 2條方向相反的邊，因為圈中每個點的度數是2（1入1出），已經符合歐拉圖的條件，必須在一個頂點上再加兩條方向相反的邊與其相鄰的頂點連接，這樣才能使之符合歐拉圖的每個頂點的度均為偶數且出度等于入度的條件。于是，可以想象，個圈可以假設成個點，要使個獨立點成為圖，那么最少必須加上條邊且方向相同才能使之成為歐拉圖。例2 驗證一個連通的線的網絡，能夠無折回地走通時，則網絡中的奇度頂點要么為0，要么為2。解答：在計算機領域中，網絡就是用物理鏈路將各個孤立的工作站或主機連在一起，組成數據鏈路，從而達到資源共享和通信的目的。網絡是在物理上或和邏輯上，按一定拓撲結構連接在一起的多個結點和鏈路的集合。這里如果我們把工作站和主機都看做是結點，鏈路看做是邊的話，那么連通的網絡就是判斷有沒有歐拉通路的網絡，結合歐拉圖的判定定理，每個結點的度都是偶數或只有奇度頂點（其它點的度都為偶數），才能構成歐拉通路。所以一個連通的線的網絡，能夠無折回地走通時，網絡中的奇度頂點個數要么為0，要么為2，具有可信性和可執(zhí)行性。例3 設是歐拉圖，但不是平凡圖，也不是一個環(huán)則證明：只需證明中不肯能有橋（如何證明？） 圖22 圖23上圖中，圖22，圖23兩圖都是歐拉圖，均從點出發(fā)，如何一次成功地走出一條歐拉回路來？例4 多米諾骨牌 28塊，能否排成一圈使兩兩相鄰的半邊的點數相同，問是否可能？解答：種例5 “兩只螞蟻比賽問題”。兩只螞蟻甲、乙分別處在圖中的頂點處，并設圖中各邊長度相等。甲提出同乙比賽：從它們所在頂點出發(fā)，走過圖中所有邊最后到達頂點處。如果它們速度相同，問誰最先到達目的地？解：圖中，有兩個奇度頂點，因此存在從到的歐拉通路，螞蟻乙走到只要走一條歐拉通路，邊數為9，螞蟻甲要想走完圖中所有邊到達，至少要先走一條邊到達，再走一條歐拉通路，故它至少要走10條邊到達，所以乙必勝。圖24例6下面圖中誰是歐拉圖？誰是非歐拉圖但存在歐拉跡？誰是非歐拉圖且不存在歐拉跡？圖25 圖26 圖27解：圖25是歐拉圖；圖26是非歐拉圖，但存在歐拉跡；圖27中不存在歐拉跡。例7 證明：若和是歐拉圖，則是歐拉圖。證明：首先證明：對任意，有：事實上，設是的任意一個鄰點，一定有的一個鄰點，反之亦然。同理，對于的任意一個鄰點，一定有的一個鄰點，反之亦然。即：在乘積圖中鄰點個數等于在中鄰點個數與在中鄰點個數之和。所以，是歐拉圖，那么頂點度數為偶數。其次證明：是連通的。由于，都是歐拉圖，所以都連通。設最短的路最短的路分別為： 那么，由乘積圖的定義：在乘積圖中有路：這樣，我們證明了是連通的且每個頂點度數為偶數。即它是歐拉圖。3歐拉圖的應用3﹒1中國郵遞員問題及算法中國郵遞員問題中國郵遞員問題，是我國梅谷教授于1960年首先提出而得名。設郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到目的地后返回郵局，要求所走的路徑最短。當然如若他所管轄的街道構成一歐拉回路，則這歐拉回路便是所求路徑。如若不然，即存在度數為奇數的頂點，必然有些街道需要多走至少1遍，這時用中國郵路問題算法可求出最短路徑。現將中國郵路問題用圖論的語言描述如下：設是連通圖，而且對于所有的，都賦以權，求從點出發(fā)，通過所有至少一次最后返回點的回路，使得達到最小。不失一般性，假定圖存在度數為奇數的頂點，如若不然，存在一條歐拉回路，它就是所求的郵路。我們可以設想，有些邊添加若干次使得到的圖的所有頂點的度數均為偶數，即為歐拉圖，問題導致求圖的歐拉回路，但圖不再是簡單圖，它具有平行邊，設邊重復了次，去掉偶數條后，仍保持各頂點的度數為偶數，即所得到的圖仍是歐拉圖。為使總數達到最小，我們不妨假定每條邊重復數目不超過1。仍使郵路達到最短，也就是要求重復邊的長度達到最短。設是所求的重復邊的集合，使達到最小，對于任一簡單回路，可分解為與相交的部分，及其余。定理7 設是使達到最小的重復邊集合，當且僅當對于圖的任一回路，恒有。證明：必要性。如若不然，假定存在使，這意味部分的權超過其余部分的權，令即。也可作為重復邊使圖成為歐拉圖。這里是對稱差。顯然，可使圖的所有頂點保持其度數為偶數，由于假定，故。跟的假設相矛盾。必要性得到了證明。注意：這里分解為與共同部分，還有其余部分，后者出現在中。充分性證明。假定存在由的邊作為重復的邊，滿足定理的條件：對于任一回路有，可以證明等式。令，則圖沒有度數為奇數的頂點，可分解成若干簡單回路，或記以，則有。但，故。同理。即，所以。充分得證。從上定理的證明過程提供了構造中國郵路問題的算法。設已知圖中頂點的度數為奇數的點為。算法第一步：從1到，引從到得鏈的每條邊附加一條使成為重復邊。第二步：檢查圖的每條邊。若添加的重復邊數超過1，則出去其中偶數條，使得每條邊之多有一條添加的邊，且每一個頂點的度為偶數，從而得圖。圖中重復邊的集合記為。第三步：，圖31若對于回路有，則作【，轉圖31】否則轉圖32。圖32輸出，便是最優(yōu)集。例題：給出中國郵路問題求解的過程。解：圖31到圖35給了中國郵路問題的求解過程。圖31便是圖，其中點是度數為奇數的點，引重復邊便得圖32。圖32中不存在重復邊數超過1的邊。55433332