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