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

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

bridges

of

K?nigsbergproblem):River

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

EulerLeonhard

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

trail):

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

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

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

v?

V(G),

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

v,w外的頂點都有偶數(shù)度;若v=w,則所有頂點都有偶數(shù)度.輸出:從v到w的歐拉通路/歐拉回路.算法:(下一頁)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-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中滿足如下2條件的邊:ei+1與vi關(guān)聯(lián)除非別無選擇,否則ei+1不是Gi中的橋若Gi?Ni,則回到(2);否則算法停止Fleury算法(舉例)2021/7/12《集合論與圖論》第17講17Fleury算法(正確性證明)定理5:設(shè)G是無向歐拉圖,則Fleury算法終止時得到的簡單通路是歐拉回路證明:

(1)

Pm是回路:

顯然.(2)

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

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

v0時走了橋;這都是矛盾!#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)用(輪盤設(shè)計)10110110000,001,010,011,100,101,110,1112021/7/12《集合論與圖論》第17講21abcca2021/7/12《集合論與圖論》第17講22應(yīng)用(輪盤設(shè)計)01D=<V,E>,

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

abc=<ab,bc>

|a,b,c?

{0,1}

}0000010001010111011100101101110101101

110

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

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

Mei-gu),1962,中國運籌學(xué)(Operation

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

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

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

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

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

CD59E38

14

10456ABFEDC510938