歐拉圖在生活中的應(yīng)用本科畢業(yè)論文-文庫(kù)吧資料
2025-07-04 15:17本頁(yè)面
【正文】 化了多奇點(diǎn)對(duì)之間增加重復(fù)邊的繁瑣性，試圖尋求一種新的適合我國(guó)牛奶配送系統(tǒng)的路徑優(yōu)化方法，并力求有所突破。而國(guó)外的一些路徑優(yōu)化軟件由于交通規(guī)則、道路規(guī)劃等各方面不符合我國(guó)國(guó)情，很難符合改革中的中國(guó)牛奶的管理流程，因此牛奶配送路徑優(yōu)化問(wèn)題已成為制約我國(guó)牛奶物流發(fā)展的主要因素之一。圖38解：圖中只有兩個(gè)奇度頂點(diǎn)和，因此存在起點(diǎn)，終點(diǎn)為的歐拉跡。圖36解： 圖37例9 某博物館的一層布置如圖210，其中邊代表走廊，結(jié)點(diǎn)是入口，結(jié)點(diǎn)是禮品店，通過(guò)我們可以離開(kāi)博物館。不滿足定理，修改得圖35 55433332221圖35易知，圖35滿足定理7，故圖35是歐拉回路。得圖33，考察33中的回路 55433332221圖33，，顯然不滿足定理的要求，作。圖32中不存在重復(fù)邊數(shù)超過(guò)1的邊。解：圖31到圖35給了中國(guó)郵路問(wèn)題的求解過(guò)程。圖32輸出，便是最優(yōu)集。圖中重復(fù)邊的集合記為。第二步：檢查圖的每條邊。設(shè)已知圖中頂點(diǎn)的度數(shù)為奇數(shù)的點(diǎn)為。充分得證。同理。令，則圖沒(méi)有度數(shù)為奇數(shù)的頂點(diǎn)，可分解成若干簡(jiǎn)單回路，或記以，則有。充分性證明。必要性得到了證明。顯然，可使圖的所有頂點(diǎn)保持其度數(shù)為偶數(shù)，由于假定，故。也可作為重復(fù)邊使圖成為歐拉圖。證明：必要性。設(shè)是所求的重復(fù)邊的集合，使達(dá)到最小，對(duì)于任一簡(jiǎn)單回路，可分解為與相交的部分，及其余。為使總數(shù)達(dá)到最小，我們不妨假定每條邊重復(fù)數(shù)目不超過(guò)1。不失一般性，假定圖存在度數(shù)為奇數(shù)的頂點(diǎn)，如若不然，存在一條歐拉回路，它就是所求的郵路。如若不然，即存在度數(shù)為奇數(shù)的頂點(diǎn)，必然有些街道需要多走至少1遍，這時(shí)用中國(guó)郵路問(wèn)題算法可求出最短路徑。設(shè)郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到目的地后返回郵局，要求所走的路徑最短。即它是歐拉圖。由于，都是歐拉圖，所以都連通。所以，是歐拉圖，那么頂點(diǎn)度數(shù)為偶數(shù)。同理，對(duì)于的任意一個(gè)鄰點(diǎn)，一定有的一個(gè)鄰點(diǎn)，反之亦然。例7 證明：若和是歐拉圖，則是歐拉圖。如果它們速度相同，問(wèn)誰(shuí)最先到達(dá)目的地？解：圖中，有兩個(gè)奇度頂點(diǎn)，因此存在從到的歐拉通路，螞蟻乙走到只要走一條歐拉通路，邊數(shù)為9，螞蟻甲要想走完圖中所有邊到達(dá)，至少要先走一條邊到達(dá)，再走一條歐拉通路，故它至少要走10條邊到達(dá)，所以乙必勝。兩只螞蟻甲、乙分別處在圖中的頂點(diǎn)處，并設(shè)圖中各邊長(zhǎng)度相等。所以一個(gè)連通的線的網(wǎng)絡(luò)，能夠無(wú)折回地走通時(shí)，網(wǎng)絡(luò)中的奇度頂點(diǎn)個(gè)數(shù)要么為0，要么為2，具有可信性和可執(zhí)行性。網(wǎng)絡(luò)是在物理上或和邏輯上，按一定拓?fù)浣Y(jié)構(gòu)連接在一起的多個(gè)結(jié)點(diǎn)和鏈路的集合。例2 驗(yàn)證一個(gè)連通的線的網(wǎng)絡(luò)，能夠無(wú)折回地走通時(shí)，則網(wǎng)絡(luò)中的奇度頂點(diǎn)要么為0，要么為2。于是，可以想象，個(gè)圈可以假設(shè)成個(gè)點(diǎn)，要使個(gè)獨(dú)立點(diǎn)成為圖，即在這2個(gè)圈之間加2條方向相反的邊，因?yàn)槿χ忻總€(gè)點(diǎn)的度數(shù)是2（1入1出），已經(jīng)符合歐拉圖的條件，必須在一個(gè)頂點(diǎn)上再加兩條方向相反的邊與其相鄰的頂點(diǎn)連接，這樣才能使之符合歐拉圖的每個(gè)頂點(diǎn)的度均為偶數(shù)且出度等于入度的條件。2﹒2歐拉圖實(shí)例例1 設(shè)是給定正整數(shù)，由個(gè)圈組成一個(gè)（有向或無(wú)向）圖，最少要添加的幾條邊使之成為歐拉圖？圖21解答：在無(wú)向圖中，假設(shè)如果有2個(gè)圈，不重合，加上最少的邊成為歐拉圖，即在這2個(gè)圈之間加2條平行邊（如圖2所示）。定理5 有向圖是半歐拉圖當(dāng)且僅當(dāng)是單向連通的，且中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)的出度比入度大1，而其余頂點(diǎn)的入度都等于出度。定理3 設(shè)是一個(gè)連通一般圖，并設(shè)中奇度頂點(diǎn)的個(gè)數(shù)，則的邊可以被劃分為個(gè)開(kāi)跡，但不能被劃分為少于個(gè)開(kāi)跡。我們可以把看作起始與頂點(diǎn)，其第一條邊是連接和的新邊的閉歐拉跡，從中去掉這條邊，我們就得到了一條中連接和的，且起始與頂點(diǎn)的開(kāi)歐拉跡。如果中存在一條開(kāi)歐拉跡，則它必連接中的兩個(gè)奇度頂點(diǎn)和，而中的其他頂點(diǎn)必是偶度次的（因?yàn)闅W拉跡每次進(jìn)入并離開(kāi)一個(gè)不同于和的頂點(diǎn)時(shí)，使得與鄰接的邊必成對(duì)出現(xiàn)）。證明：首先，回憶定理（設(shè)是一個(gè)一般圖，則其所有頂點(diǎn)的度數(shù)之和是一個(gè)偶數(shù)，從而，其奇度頂點(diǎn)的個(gè)數(shù)也必為偶數(shù)。定理2 設(shè)是一個(gè)連通的一般圖，則中存在一條開(kāi)歐拉跡，當(dāng)且僅當(dāng)中恰好有兩個(gè)奇度頂點(diǎn)和。重復(fù)上述過(guò)程，直到所有的邊都包含在一條閉跡 中為止?，F(xiàn)在我們把和在頂點(diǎn)處拼接在一起，得到一條包含和的所有邊的閉跡。令是去掉中屬于閉跡的邊后得到的一般圖，則的所有頂點(diǎn)都具有偶度次。證明：我們已經(jīng)觀察到了：如果中有一條閉歐拉跡，則的每個(gè)頂點(diǎn)都具有偶度次。由于一條閉跡中的邊可以被劃分為圈，所以我們完成了引理的證明。既然在一般圖中具有偶度次，則必存在一個(gè)還不屬于的邊與鄰接。容易看到：算法中每步iv)的d)結(jié)束時(shí)，一般圖的每個(gè)頂點(diǎn)都具有偶度次，只有頂點(diǎn)（它起始于奇度1）和最新加入的頂點(diǎn)（它的度數(shù)剛剛增加1）可能除外。因此，我們只需證明：如果，那么就有一個(gè)不在中的邊與鄰接。 假設(shè)只要時(shí)，滿足iv)a)的一條邊總存在。d) 令。b) 將放人中（也許已在中）。在該算法中，我們要構(gòu)造一個(gè)頂點(diǎn)集和一個(gè)邊集。2歐拉圖的判定定理和實(shí)例2﹒1歐拉圖的判定定理下面介紹歐拉圖的一些判定定理：引理：設(shè)一般圖，如果它的每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)，則的每條邊都屬于一條閉跡，因而也屬于一個(gè)圈。定義10 歐拉閉跡：經(jīng)過(guò)圖的每條邊恰好一次的閉跡
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1