離散數(shù)學(xué)集合論圖論chapter

第17講歐拉圖2021/7/12《集合論與圖論》第17講11.七橋問(wèn)題,一筆畫(huà),歐拉通(回)路,歐拉圖2.判定歐拉圖的充分必要條件3.求歐拉回路的算法4.中國(guó)郵遞員問(wèn)題七橋問(wèn)題七橋問(wèn)題(Seven

bridges

of

K?nigsbergproblem):River

Pregel,Kaliningrad,Russia2021/7/12《集合論與圖論》第17講22021/7/123Leonhard

EulerLeonhard

Euler(1707~1783):人類(lèi)有史以來(lái)最多產(chǎn)的數(shù)學(xué)家.1736年,“七橋問(wèn)題”,圖論和拓?fù)鋵W(xué)誕生DcAdabfCg《集合論與圖論》第17講Be一筆畫(huà)2021/7/12《集合論與圖論》第17講4歐拉圖(Eulerian)2021/7/12《集合論與圖論》第17講5歐拉通路(Euler

trail):

經(jīng)過(guò)圖中所有邊的簡(jiǎn)單通路歐拉回路(Euler

tour/circuit):經(jīng)過(guò)圖中所有邊的簡(jiǎn)單回路歐拉圖(Eulerian):有歐拉回路的圖半歐拉圖(semi-Eulerian):有歐拉通路的圖無(wú)向歐拉圖的充分必要條件定理1:設(shè)G是無(wú)向連通圖,則G是歐拉圖G中所有頂點(diǎn)都是偶數(shù)度G是若干個(gè)邊不交的圈的并證明:(1)(2)(3)(1).(1)(2):若歐拉回路總共k次經(jīng)過(guò)頂點(diǎn)v,則d(v)=2k.2021/7/12《集合論與圖論》第17講6定理1((2)(3))G中所有頂點(diǎn)都是偶數(shù)度G是若干個(gè)邊不交的圈的并證明:(2)(3):若刪除任意1個(gè)圈上的邊,則所有頂點(diǎn)的度還是偶數(shù),但是不一定連通了.對(duì)每個(gè)連通分支重復(fù)進(jìn)行.2021/7/12《集合論與圖論》第17講7定理1((3)(1))(1)G是歐拉圖(3)

G是若干個(gè)邊不交的圈的并證明:(3)(1):有公共點(diǎn)但邊不交的簡(jiǎn)單回路,總可以拼接成歐拉回路:在交點(diǎn)處,走完第1個(gè)回路后再走第2個(gè)回路.#用歸納法嚴(yán)格證明2021/7/12《集合論與圖論》第17講8無(wú)向半歐拉圖的充分必要條件定理2:設(shè)G是無(wú)向連通圖,則G是半歐拉圖G中恰有2個(gè)奇度頂點(diǎn)證明:(1)(2):歐拉通路的起點(diǎn)和終點(diǎn)是奇數(shù)度,其余頂點(diǎn)都是偶數(shù)度.(2)(1):在兩個(gè)奇數(shù)度頂點(diǎn)之間加1條新邊,所有頂點(diǎn)都是偶數(shù)度,得到歐拉回路.從歐拉回路上刪除所加邊后,得到歐拉通路.#2021/7/12《集合論與圖論》第17講9有向歐拉圖的充分必要條件定理3:設(shè)G是有向連通圖,則G是歐拉圖"

v?

V(G),

d+(v)=d-(v)G是若干個(gè)邊不交的有向圈的并證明:(1)(2)(3)(1).(1)(2):若歐拉回路總共k次經(jīng)過(guò)頂點(diǎn)v,則d+(v)=d-(v)=k.其余與定理1類(lèi)似.#2021/7/12《集合論與圖論》第17講10有向半歐拉圖的充分必要條件定理4:設(shè)G是無(wú)向連通圖,則G是半歐拉圖G中恰有2個(gè)奇度頂點(diǎn),其中1個(gè)入度比出度大1,另1個(gè)出度比入度大1,其余頂點(diǎn)入度等于出度.#2021/7/12《集合論與圖論》第17講11例2021/7/12《集合論與圖論》第17講12算法(algorithm)一組有限條指令,具有以下特征:輸入:算法工作對(duì)象輸出:算法工作結(jié)果確定性:算法根據(jù)輸入和當(dāng)前工作狀態(tài),決定下一步采用的指令可行性:算法的指令都是可以實(shí)現(xiàn)的終止性:算法工作有窮步后停止輸入2021/7/12《集合論與圖論》第17講13輸出指令組工作區(qū)Fleury算法2021/7/12《集合論與圖論》第17講14輸入:連通圖G,起點(diǎn)v,終點(diǎn)w.若v?w,則除

v,w外的頂點(diǎn)都有偶數(shù)度;若v=w,則所有頂點(diǎn)都有偶數(shù)度.輸出:從v到w的歐拉通路/歐拉回路.算法:(下一頁(yè))Fleury算法(遞歸形式)2021/7/12《集合論與圖論》第17講15算法:if

d(v)>1

then

e:=v關(guān)聯(lián)的任意非割邊else

e:=v關(guān)聯(lián)的唯一邊u:=e的另一個(gè)端點(diǎn).遞歸地求G-e的從u到w的歐拉通路把e接續(xù)在遞歸地求出的通路上Fleury算法(迭代形式)2021/7/12《集合論與圖論》第17講16算法:P0:=v;設(shè)Pi=v0e1v1e2…eivi已經(jīng)行遍,設(shè)Gi=G-{e1,e2

,…,ei},ei+1:=Gi中滿(mǎn)足如下2條件的邊:ei+1與vi關(guān)聯(lián)除非別無(wú)選擇,否則ei+1不是Gi中的橋若Gi?Ni,則回到(2);否則算法停止Fleury算法(舉例)2021/7/12《集合論與圖論》第17講17Fleury算法(正確性證明)定理5:設(shè)G是無(wú)向歐拉圖,則Fleury算法終止時(shí)得到的簡(jiǎn)單通路是歐拉回路證明:

(1)

Pm是回路:

顯然.(2)

Pm經(jīng)過(guò)G中所有邊:(反證)否則,G-Pm的連通分支還是歐拉回路,并且與

Pm相交.若v0是交點(diǎn),則算法不應(yīng)結(jié)束;若v0不是交點(diǎn),則算法在最后離開(kāi)交點(diǎn)回到

v0時(shí)走了橋;這都是矛盾!#2021/7/12《集合論與圖論》第17講18逐步插入回路算法2021/7/12《集合論與圖論》第17講19(0)

i:=0,

v*:=v,v:=v1,P0=v1,G0=G.

e:=在Gi中與v關(guān)聯(lián)的任意邊(v,v’),Pi+1:=“Pi”ev’.if

v’?v*

then

i:=i+1,

v=v’,

goto

(1).if

E(Pi+1)=E(G)then

結(jié)束else

Gi+1:=G-E(Pi+1),e:=Gi+1中與Pi+1上vk關(guān)聯(lián)的任意邊,Pi+1:=vk…vk.v*:=vk,v:=vk,

i:=i+1,

goto

(1).逐步插入回路算法(舉例)2021/7/12《集合論與圖論》第17講20應(yīng)用(輪盤(pán)設(shè)計(jì))10110110000,001,010,011,100,101,110,1112021/7/12《集合論與圖論》第17講21abcca2021/7/12《集合論與圖論》第17講22應(yīng)用(輪盤(pán)設(shè)計(jì))01D=<V,E>,

V={00,01,10,11},E={

abc=<ab,bc>

|a,b,c?

{0,1}

}0000010001010111011100101101110101101

110

0中國(guó)郵遞員問(wèn)題2021/7/12《集合論與圖論》第17講23中國(guó)郵遞員問(wèn)題(Chinese

postmanproblem):求郵遞員走遍管區(qū)所有街道的最短回路管梅谷(Guan

Mei-gu),1962,中國(guó)運(yùn)籌學(xué)(Operation

Research)組合優(yōu)化(Combinatorial

Optimization)帶權(quán)圖(weighted

graph)帶權(quán)圖(weighted

graph):G=<V,E,W>,W:Efi

R,W(e)稱(chēng)為e的權(quán)AFB

CD59E38

14

10456ABFEDC510938