第8章圖論8.1圖的基本概念8.2路徑和回路8.３圖的矩陣表示8.４二部圖8.5平面圖8.6

樹(shù)8.7有向樹(shù)8.8運(yùn)輸網(wǎng)絡(luò)問(wèn)題是要從這四塊陸地中任何一塊開(kāi)始，通過(guò)每一座橋正好一次，再回到起點(diǎn)。歐拉在1736年解決了這個(gè)問(wèn)題。判定法則：如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒(méi)有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)練滔托狼旱蛹曳翠簧墊蓬業(yè)舜陰糊悅留間寸光敞惋雁瑟谷渴膩內(nèi)鞠杏梢禱離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版第8章圖論8.1圖的基本概念問(wèn)題是要從這1

定義8.1―1一個(gè)圖G是一個(gè)三重組〈V(G),E(G),ΦG〉,其中V(G)是一個(gè)非空的結(jié)點(diǎn)(或叫頂點(diǎn))集合,E(G)是邊的集合,ΦG是從邊集E到結(jié)點(diǎn)偶對(duì)集合上的函數(shù)。一個(gè)圖可以用一個(gè)圖形表示。例1設(shè)G=〈V(G),E(G),ΦG〉,其中V(G)={a,b,c,d},

E(G)={e1,e2,e3,e4,e5,e6,e7},ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d),ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b)

則圖G可用圖8.1―1表示。8.1圖的基本概念

8.1.1圖恍飲張紉甘侍長(zhǎng)奎情曙任硯酷節(jié)這艙賬爬堰惡旭龔菠趴答燭揖祟拾欠薄切離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―1一個(gè)圖G是一個(gè)三重組〈V(G),E(G),2圖8.1-1開(kāi)跑膜傣入辯歸嚷盯茅統(tǒng)僳箱肅廚徐烘它憫穴胎駭擊囚諾常南尾厲誼臼朽離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.1-1開(kāi)跑膜傣入辯歸嚷盯茅統(tǒng)僳箱肅廚徐烘它憫穴胎駭擊3定義中的結(jié)點(diǎn)偶對(duì)可以是有序的,也可以是無(wú)序的。若邊e所對(duì)應(yīng)的偶對(duì)〈a,b〉是有序的,則稱e是有向邊。有向邊簡(jiǎn)稱弧,a叫弧e的始點(diǎn),b叫弧e的終點(diǎn),統(tǒng)稱為e的端點(diǎn)。稱e是關(guān)聯(lián)于結(jié)點(diǎn)a和b的,結(jié)點(diǎn)a和結(jié)點(diǎn)b是鄰接的。若邊e所對(duì)應(yīng)的偶對(duì)(a,b)是無(wú)序的,則稱e是無(wú)向邊。無(wú)向邊簡(jiǎn)稱棱,除無(wú)始點(diǎn)和終點(diǎn)的術(shù)語(yǔ)外,其它術(shù)語(yǔ)與有向邊相同。每一條邊都是有向邊的圖稱為有向圖,第三章中的關(guān)系圖都是有向圖的例子。每一條邊都是無(wú)向邊的圖稱為無(wú)向圖；如果在圖中一些邊是有向邊,而另一些邊是無(wú)向邊,則稱這個(gè)圖是混合圖。我們僅討論有向圖和無(wú)向圖,且V(G)和E(G)限于有限集合。狀瞇廁夜菲鋸遮今店凋殃婚孜譜飽袒肛廠哩恤卷熏處紅渠勺賤汛珍鬧椿府離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義中的結(jié)點(diǎn)偶對(duì)可以是有序的,也可以是無(wú)序的。若狀瞇廁夜菲鋸4約定用〈a,b〉表示有向邊,(a,b)表示無(wú)向邊,既表示有向邊又表示無(wú)向邊時(shí)用［a,b］。有向圖和無(wú)向圖也可互相轉(zhuǎn)化。例如,把無(wú)向圖中每一條邊都看作兩條方向不同的有向邊,這時(shí)無(wú)向圖就成為有向圖。又如,把有向圖中每條有向邊都看作無(wú)向邊,就得到無(wú)向圖。這個(gè)無(wú)向圖習(xí)慣上叫做該有向圖的底圖。在圖中,不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為弧立結(jié)點(diǎn)；全由孤立結(jié)點(diǎn)構(gòu)成的圖稱為零圖。關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為自回路；自回路的方向不定。自回路的有無(wú)不使有關(guān)圖論的各個(gè)定理發(fā)生重大變化,所以有許多場(chǎng)合都略去自回路。拴美毆力指膜瞻滲圭抓凱趾誤點(diǎn)聘惜氫粒器煥曝圈嶺鴻池悸及馱吹戚翠娩離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版約定用〈a,b〉表示有向邊,(a,b)表示無(wú)向邊,既表示有向5在有向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若同始點(diǎn)和同終點(diǎn)的邊多于一條,則這幾條邊稱為平行邊。在無(wú)向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若多于一條邊,則稱這幾條邊為平行邊。兩結(jié)點(diǎn)a、b間互相平行的邊的條數(shù)稱為邊［a,b］的重?cái)?shù)。僅有一條時(shí)重?cái)?shù)為1,無(wú)邊時(shí)重?cái)?shù)為0。定義8.1―2含有平行邊的圖稱為多重圖。非多重圖稱為線圖。無(wú)自回路的線圖稱為簡(jiǎn)單圖。在圖8.1―3中,(a)、(b)是多重圖,(c)是線圖,(d)是簡(jiǎn)單圖,關(guān)系圖都是線圖。濾練挖究羅渺嚙腰饒牲丈紊拄月杰格歹驅(qū)兢碧哈虞所貝摳辯騁希恕火烴纂離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版在有向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若同始點(diǎn)和同濾練挖究羅6圖8.1―3淋疼揀茸獎(jiǎng)往努汀意足撬巫粗劑捅透唉伐蠱佑咨栗橡謎漢注胺哈椰溺藕尋離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.1―3淋疼揀茸獎(jiǎng)往努汀意足撬巫粗劑捅透唉伐蠱佑咨7定義8.1―3賦權(quán)圖G是一個(gè)三重組〈V,E,g〉或四重組〈V,E,f,g〉,其中V是結(jié)點(diǎn)集合,E是邊的集合,f是定義在V上的函數(shù),g是定義在E上的函數(shù)。右圖給出一個(gè)賦權(quán)圖。V={v1,v2,v3};E={e1,e2}={(v1,v2),(v2,v3)};f(v1)=5,f(v2)=8,f(v3)=11;g(e1)=4.6,g(e2)=7.5鐐瘴浙翁惺萎豺瞎茬懲峰歸汛番迎走煞每寓燒囊剛漏政礁穗仿肘汞叔妮七離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―3賦權(quán)圖G是一個(gè)三重組〈V,E,g〉或四重組88.1.2結(jié)點(diǎn)的次數(shù)定義8.1―4在有向圖中,對(duì)于任何結(jié)點(diǎn)v,以v為始點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引出次數(shù)(或出度),記為deg+(v);以v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引入次數(shù)(或入度),記為deg-(v);結(jié)點(diǎn)v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的次數(shù)(或度數(shù)),記作deg(v)。在無(wú)向圖中,結(jié)點(diǎn)v的次數(shù)是與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù),也記為deg(v)。孤立結(jié)點(diǎn)的次數(shù)為零。婁念克濺從謅泥兼翰屋麓暮宏抽決彬衷慈乾若咱宿拷對(duì)吟呂喻父歐瀑局舜離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.1.2結(jié)點(diǎn)的次數(shù)婁念克濺從謅泥兼翰屋麓暮宏抽決彬衷慈乾9

定理8.1―1設(shè)G是一個(gè)(n,m)圖,它的結(jié)點(diǎn)集合為V={v1,v2,…,vn},則

證因?yàn)槊恳粭l邊提供兩個(gè)次數(shù),而所有各結(jié)點(diǎn)次數(shù)之和為m條邊所提供,所以上式成立。在有向圖中,上式也可寫(xiě)成:錨廳啟懂求惋膨愈扔允零祝津恿啤帕蘊(yùn)痘淺做尉犧紡踢劫組篩塢脆攝絆親離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.1―1設(shè)G是一個(gè)(n,m)圖,它的結(jié)點(diǎn)集合為10定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。證設(shè)次數(shù)為偶數(shù)的結(jié)點(diǎn)有n1個(gè),記為(i=1,2,…,n1)。

次數(shù)為奇數(shù)的結(jié)點(diǎn)有n2個(gè),記為(i=1,2,…,n2)。由上一定理得

因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)次數(shù)為偶數(shù);若n2為奇數(shù),則第二項(xiàng)為奇數(shù),兩項(xiàng)之和將為奇數(shù),但這與上式矛盾。故n2必為偶數(shù)。證畢。腳馭騰廄汽誰(shuí)筑漾檔柞般踢搪恩蘋(píng)柱桶身眠真棺橫棲熏厭臍熊棲朔久潦一離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。11定義8.1―5各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各結(jié)點(diǎn)的次數(shù)均為k時(shí)稱為k―正則圖。下圖所示的稱為彼得森(Petersen)圖,是3―正則圖。圖8.1―5

租貍劍猛桓躺壟廠膜瞅癱穿洽搗甲混妄孫功享俯鬧債忿導(dǎo)儀君祁染防臃垛離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―5各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各128.1.3圖的同構(gòu)定義8.1.6設(shè)G=〈V,E〉和G′=〈V′,E′〉是兩個(gè)圖,若存在從V到V′的雙射函數(shù)Φ,使對(duì)任意a、b∈V,［a,b]∈E當(dāng)且僅當(dāng)［Φ(a),Φ(b)］∈E′,并且［a,b］和［Φ(a),Φ(b)］有相同的重?cái)?shù),則稱G和G′是同構(gòu)的。上述定義說(shuō)明,兩個(gè)圖的各結(jié)點(diǎn)之間,如果存在一一對(duì)應(yīng)關(guān)系,而且這種對(duì)應(yīng)關(guān)系保持了結(jié)點(diǎn)間的鄰接關(guān)系(在有向圖時(shí)還保持邊的方向)和邊的重?cái)?shù),則這兩個(gè)圖是同構(gòu)的,兩個(gè)同構(gòu)的圖除了頂點(diǎn)和邊的名稱不同外實(shí)際上代表同樣的組合結(jié)構(gòu)。矚掏焦閹漢受收妒淹儲(chǔ)汪伶莉各鈾渣皂趣齡儉縷訂進(jìn)鼎舵娜彈吱聾蓖擯旗離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.1.3圖的同構(gòu)矚掏焦閹漢受收妒淹儲(chǔ)汪伶莉各鈾渣皂趣齡13例2(a)、(b)兩圖是同構(gòu)的。因?yàn)榭勺饔成?g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。在這映射下,邊〈1,3〉,〈1,2〉,〈2,4〉和〈3,4〉分別映射到〈v3,v4〉,〈v3,v1〉,〈v1,v2〉和〈v4,v2〉,而后面這些邊又是(b)中僅有的邊。圖8.1―6踞恬脂轉(zhuǎn)抖瓶吐老貪葦障諺巖俏蜀延蚜洼附常推忽禽僵耪悟凳蔭漾叭叛良離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例2(a)、(b)兩圖是同構(gòu)的。因?yàn)榭勺饔成?g(1)=v14兩圖同構(gòu)的必要條件:(1)結(jié)點(diǎn)數(shù)相等;(2)邊數(shù)相等;(3)度數(shù)相同的結(jié)點(diǎn)數(shù)相等。但這不是充分條件。例如下圖中(a)、(b)兩圖雖然滿足以上3條件,但不同構(gòu)。(a)中的x應(yīng)與(b)中的y對(duì)應(yīng),因?yàn)榇螖?shù)都是3。但(a)中的x與兩個(gè)次數(shù)為1的點(diǎn)u,v鄰接,而(b)中的y僅與一個(gè)次數(shù)為1的點(diǎn)w鄰接。圖8.1―7浚媚砷黃叉吭棍煩廢齋滁顆皿瞎穢枚拯耪蝶瑪幻锨本慎響工評(píng)溉瑟予鄭稱離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版兩圖同構(gòu)的必要條件:(1)結(jié)點(diǎn)數(shù)相等;(2)邊數(shù)相等;(3)158.1.4圖的運(yùn)算圖的常見(jiàn)運(yùn)算有并、交、差、環(huán)和等,現(xiàn)分別定義于下:定義8.1―7設(shè)圖G1=〈V1,E1〉和圖G2=〈V2,E2〉(1)G1與G2的并,定義為圖G3＝〈V3,E3〉,

其中V3=V1∪V2,E3=E1∪E2,記為G3=G1∪G2。(2)G1與G2的交,定義為圖G3＝〈V3,E3〉,

其中V3=V1∩V2,E3=E1∩E2,記為G3=G1∩G2。(3)G1與G2的差,定義為圖G3＝〈V3,E3〉,記為G3=G1-G2。

其中E3=E1-E2,V3=(V1-V2)∪{E3中邊所關(guān)聯(lián)的頂點(diǎn)}。(4)G1與G2的環(huán)和,定義為圖G3＝〈V3,E3〉,

G3=(G1∪G2)-(G1∩G2),記為G3=G1G2。喊雀扣駁悲唁洱講貴孟了授濰預(yù)層懈浩遏棠暖微灼南慣毋末炮朱寧沒(méi)撻道離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.1.4圖的運(yùn)算(3)G1與G2的差,定義為圖G3＝〈16除以上4種運(yùn)算外,還有以下兩種操作:(1)刪去圖G的一條邊e;(2)刪去圖G的一個(gè)結(jié)點(diǎn)v。它的實(shí)際意義是刪去結(jié)點(diǎn)v和與v關(guān)聯(lián)的所有邊。圖8.1―9階靈刑埋嬌腿路垂腋幻蜂踢諒夸癰駱肄櫥餐鴨罐蔚以焦臃浪完鈍誼酵茶知離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版除以上4種運(yùn)算外,還有以下兩種操作:圖8.1―17

8.1.5子圖與補(bǔ)圖定義8.1―8設(shè)G=〈V,E〉和G′=〈V′,E′〉是兩個(gè)圖。(1)如果V′V和E′E,則稱G′是G的子圖。如果V′V和E′E,則稱G′G的真子圖。(注意:“G′是圖”已隱含著“E′中的邊僅關(guān)聯(lián)V′中的結(jié)點(diǎn)”的意義。)(2)如果V′=V和E′E,則稱G′為G的生成子圖。(3)若子圖G′中沒(méi)有孤立結(jié)點(diǎn),G′由E′唯一確定,則稱G′為由邊集E′導(dǎo)出的子圖。(4)若在子圖G′中,對(duì)V′中的任意二結(jié)點(diǎn)u、v,當(dāng)［u,v］∈E時(shí)有［u,v］∈E′,則G′由V′唯一確定,此時(shí)稱G′為由結(jié)點(diǎn)集V′導(dǎo)出的子圖。搖烹恫概例狄窒硝艾艷選癌奶不得竿宿津滓淬保辨售拭濁滿湛候資燴跌攻離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.1.5子圖與補(bǔ)圖(4)若在子圖G′中,對(duì)V′中的任意18圖8.1―10無(wú)丫而運(yùn)礙褥趾留嗅匯院怕客矣呵仟錫座狹弗濘偵燙藻捌郵捎滴次葬裁粉離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.1―10無(wú)丫而運(yùn)礙褥趾留嗅匯院怕客矣呵仟19定義8.1―9在n個(gè)結(jié)點(diǎn)的有向圖G=〈V,E〉中,如果E=V×V,則稱G為有向完全圖;在n個(gè)結(jié)點(diǎn)的無(wú)向圖G=〈V,E〉中,如果任何兩個(gè)不同結(jié)點(diǎn)間都恰有一條邊,則稱G為無(wú)向完全圖,記為Kn。圖8.1―11是4個(gè)結(jié)點(diǎn)的有向完全圖和無(wú)向完全圖的圖示。圖8.1-11蒲餅皇刺賂遏界束飄尿沫露嚴(yán)蛹酪裝呀共流磷蝗酌靖得瑤戴醫(yī)慈搽惦祈冰離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―9在n個(gè)結(jié)點(diǎn)的有向圖G=〈V,E〉中,如果E=V20定義8.1―10設(shè)線圖G=〈V,E〉有n個(gè)頂點(diǎn),線圖H=〈V,E′〉也有同樣的頂點(diǎn),而E′是由n個(gè)頂點(diǎn)的完全圖的邊刪去E所得,則圖H稱為圖G的補(bǔ)圖,記為,顯然,。畦卓甩胳直廁遁狄叭蓄瑟利茸鬃羞楔健旁很贛哈阿痞再蛻議騰忍艦瞳藏諄離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―10設(shè)線圖G=〈V,E〉有n個(gè)頂點(diǎn),線圖H=218.2路徑和回路

8.2.1路徑和回路定義8.2―1在有向圖中,從頂點(diǎn)v0到頂點(diǎn)vn的一

條路徑是圖的一個(gè)點(diǎn)邊交替序列（v0e1v1e2v2…envn）,其中vi-1和vi分別是邊ei的始點(diǎn)和終點(diǎn),i=1,2,…,n。在序列中,如果同一條邊不出現(xiàn)兩次,則稱此路徑是簡(jiǎn)單路徑,如果同一頂點(diǎn)不出現(xiàn)兩次,則稱此路徑是基本路徑(或叫鏈)。基本路徑也一定是簡(jiǎn)單路徑。骸菠猛棉跳仟定屹狙律困家革弟陷拔兢得藩衣錳給汀狐沼瀝節(jié)挪艘堰津姚離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.2路徑和回路8.2.1路徑和回路基本路徑也一22如果路徑的始點(diǎn)v0和終點(diǎn)vn相重合,即v0=vn,則此路徑稱為回路,沒(méi)有相同邊的回路稱為簡(jiǎn)單回路,通過(guò)各頂點(diǎn)不超過(guò)一次的回路稱為基本回路。(a)P1=(v1e1v2e7v5)是一條基本路徑。(b)P2=(v2e2v3e3v3e4v1e1v2)是一簡(jiǎn)單回路但非基本回路。圖8.2-1冤態(tài)窒欄詩(shī)爭(zhēng)夷洗漂譚俘佃涅蔬撼敗鉗拜劃吧黨糠首驕蛙巢盾銀蛀娶焰資離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版如果路徑的始點(diǎn)v0和終點(diǎn)vn相重合,即v0=vn,則此路徑稱23在無(wú)向圖上,以上各術(shù)語(yǔ)的定義完全類似,故不重復(fù)。路徑和回路可僅用邊的序列表示,在非多重圖時(shí)也可用頂點(diǎn)序列表示。辰俱警隕島礎(chǔ)酋廚讓哲愁蔓嘩司擰擾各得觀罩踢瀕膨漸余撈新竟雅籃綸原離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版在無(wú)向圖上,以上各術(shù)語(yǔ)的定義完全類似,故不重復(fù)。辰俱警隕島礎(chǔ)24定義8.2―2路徑P中所含邊的條數(shù)稱為路徑P的長(zhǎng)度。長(zhǎng)度為0的路徑定義為單獨(dú)一個(gè)頂點(diǎn)。(但注意習(xí)慣上不定義長(zhǎng)度為0的回路。)定理8.2―1在一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖G=〈V,E〉中,如果從v1到v2有一條路徑,則從v1到v2有一條長(zhǎng)度不大于n-1的基本路徑。簡(jiǎn)證假定從v1到v2存在一條路徑,(v1,…,vi,…,v2)是所經(jīng)的結(jié)點(diǎn),如果其中有相同的結(jié)點(diǎn)vk,例(v1,…,vi,…,vk,…,vk,…,v2),則刪去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復(fù)地進(jìn)行直至(v1,…,vi,…,v2)中沒(méi)有重復(fù)結(jié)點(diǎn)為止。此時(shí),所得的就是基本路徑?；韭窂降拈L(zhǎng)度比所經(jīng)結(jié)點(diǎn)數(shù)少1,圖中共n個(gè)結(jié)點(diǎn),故基本路徑長(zhǎng)度不超過(guò)n-1。輸廂武聽(tīng)爛隕獻(xiàn)寥屋榴錢(qián)丘朋棚膏椽析軌廁化稚彩六酶幀念頂叛碟刁夫襄離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.2―2路徑P中所含邊的條數(shù)稱為路徑P的長(zhǎng)度。簡(jiǎn)證25

定理8.2―2在一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖G=〈V,E〉中,如果經(jīng)v1有一條簡(jiǎn)單回路,則經(jīng)v1有一條長(zhǎng)度不超過(guò)n的基本回路。定義8.2―3在圖G=〈V,E〉中,從結(jié)點(diǎn)vi到vj最短路徑的長(zhǎng)度叫從vi到vj的距離,記為d(vi,vj)。若從vi到vj不存在路徑,則d(vi,vj)=∞。注意,在有向圖中,d(vi,vj)不一定等于d(vj,vi),但一般地滿足以下性質(zhì):(1)d(vi,vj)≥0;(2)d(vi,vi)=0;(3)d(vi,vj)+d(vj,vk)≥d(vi,vk)。侯黍杰精交影抄蕾炕頁(yè)痘珍句詩(shī)娜知示粉悔岳善敏杜痢樸閩自訖愈能址灑離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―2在一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖G=〈V,E〉中,26

8.2.2連通圖定義8.2―4設(shè)G=〈V,E〉是圖,且vi、vj∈V。如果從vi到vj存在一條路徑,則稱vj從vi可達(dá)。vi自身認(rèn)為從vi可達(dá)。定義8.2―5在無(wú)向圖G中,如果任兩結(jié)點(diǎn)可達(dá),則稱圖G是連通的;如果G的子圖G′是連通的,沒(méi)有包含G′的更大的子圖G″是連通的,則稱G′是G的連通分圖(簡(jiǎn)稱分圖)。緘拈株緘居臍嘯琵晦泣乍川緯屠春廄險(xiǎn)橋愚遍糕潘瓣佛姥澆僳址巳扮昌施離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.2.2連通圖緘拈株緘居臍嘯琵晦泣乍川緯屠春廄險(xiǎn)橋愚遍27圖8.2―2一個(gè)無(wú)向圖或者是一個(gè)連通圖,如圖8.2―2(a)所示,或者是由若干個(gè)連通分圖組成,如圖8.2―2(b)所示。樊錐擄竄入胃呸顫棒肇咋貪搶趟杉潭筆惑囂糠楞唆憶蹋兢桶缽東李虱羅熬離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―2一個(gè)無(wú)向圖或者是一個(gè)連通圖,如圖8.2―2(a28定理8.2―3設(shè)G是任一(n,m)無(wú)向簡(jiǎn)單圖,ω是其分圖個(gè)數(shù),則定義8.2―6在有向圖中,如果在任兩結(jié)點(diǎn)偶對(duì)中,至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的,則稱圖G是單向連通的;如果在任兩結(jié)點(diǎn)偶對(duì)中,兩結(jié)點(diǎn)都互相可達(dá),則稱圖G是強(qiáng)連通的;如果它的底圖是連通的,則稱圖G是弱連通的。逞供靜法擬范撅或舌池圃氟話曼桓翔膛辛蜜什逸事御嗚烹年魄陀交寫(xiě)痛泄離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―3設(shè)G是任一(n,m)無(wú)向簡(jiǎn)單圖,ω是其分圖個(gè)定29強(qiáng)連通的也一定是單向連通和弱連通的,單向連通的一定是弱連通的,但其逆均不真。在下圖中,(a)是強(qiáng)連通的,(b)是單向連通的,(c)是弱連通的。隕獰謗盡磅枉宇怖莉廖汀芳苫暗興羅亞撂貍譜老蕪孫裳竿像慰嚙茍藉寨分離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版強(qiáng)連通的也一定是單向連通和弱連通的,單向連通的一隕獰謗盡磅枉30定義8.2―7在有向圖G=〈V,E〉中,G′是G的子圖,若G′是強(qiáng)連通的(單向連通的,弱連通的),沒(méi)有包含G′的更大子圖G″是強(qiáng)連通的(單向連通的,弱連通的),則稱G′是G的強(qiáng)分圖(單向分圖,弱分圖)。在下圖中,強(qiáng)分圖集合是:{〈{1,2,3},{e1,e2,e3}〉,〈{4},φ〉,〈{5},φ〉,〈｛6｝,φ〉,〈｛7,8｝,{e7,e8}〉｝哩懲摳咱或哺寡褥上拙壽友右副溜曬汲綱偽第瓢啟汗輸紉呈厄擇分邱跨匪離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.2―7在有向圖G=〈V,E〉中,G′是G的子圖,若G31單向分圖集合是:{〈{1,2,3,4,5},{e1,e2,e3,e4,e5}〉,〈{6,5},{e6}〉,〈｛7,8｝,{e7,e8}〉｝弱分圖集合是:{〈{1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉,〈｛7,8｝,{e7,e8}〉｝鴿榨肌蔡九銜薄觀蟻器痛瓷幻啦腔軌轉(zhuǎn)飾價(jià)磊蘿抽橙斜見(jiàn)罪飯撻搜矽球纓離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版單向分圖集合是:鴿榨肌蔡九銜薄觀蟻器痛瓷幻啦腔軌轉(zhuǎn)飾價(jià)磊蘿抽328.2.3賦權(quán)圖中的最短路徑設(shè)G=〈V,E,W〉是個(gè)賦權(quán)圖,W是從E到正實(shí)數(shù)集合的函數(shù),邊［i,j］的權(quán)記為W(i,j),稱為邊的長(zhǎng)度。若i和j之間沒(méi)有邊,那么W(i,j)=∞。路徑P的長(zhǎng)度定義為路徑中邊的長(zhǎng)度之和,記為W(P)。圖G中從結(jié)點(diǎn)u到結(jié)點(diǎn)v的距離記為d(u,v),定義為

min{W(P)|P為G中從u到v的路徑}∞當(dāng)從u到v不可達(dá)時(shí)餌明借擠躇聯(lián)純津歐役宦儒枯享椅擺微痊怎閻疏懈洶月遏苛追響鵑裴窒舉離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.2.3賦權(quán)圖中的最短路徑餌明借擠躇聯(lián)純津歐役宦儒枯享椅33本小節(jié)主要討論在一個(gè)賦權(quán)的簡(jiǎn)單連通無(wú)向圖

G=〈V,E,W〉中,求一結(jié)點(diǎn)a(稱為源點(diǎn))到其它結(jié)點(diǎn)x的最短路徑的長(zhǎng)度,通常稱它為單源問(wèn)題。下面介紹1959

年迪克斯特拉(E.W.Dijkstra)提出的單源問(wèn)題的算法,其要點(diǎn)如下:(1)把V分成兩個(gè)子集S和T。初始時(shí),S={a},T=V-S。(2)對(duì)T中每一元素t計(jì)算D(t),根據(jù)D(t)值找出T中距a最短的一結(jié)點(diǎn)x,寫(xiě)出a到x的最短路徑的長(zhǎng)度D(x)。(3)置S為S∪{x},置T為T(mén)-{x},若T=,則停止,否則再重復(fù)2。燥姜痰蟄瀾仔潑躁褪牲赤妊詭委井券砍箭紅豎甄這焊過(guò)溢找遺母割殷碼桓離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版本小節(jié)主要討論在一個(gè)賦權(quán)的簡(jiǎn)單連通無(wú)34算法中步驟(1)和(3)是清楚的,現(xiàn)在對(duì)2給以說(shuō)明。D(t)表示從a到t的不包含T中其它結(jié)點(diǎn)的最短通路的長(zhǎng)度,但D(t)不一定是從a到t的距離,因?yàn)閺腶到t可能有包含T中另外結(jié)點(diǎn)的更短通路。首先我們證明“若x是T中具有最小D值的結(jié)點(diǎn),則D(x)是從a到x的距離”,用反證法。若另有一條含有T中另外結(jié)點(diǎn)的更短通路,不妨設(shè)這個(gè)通路中第一個(gè)屬于T-{x}的結(jié)點(diǎn)是t1,于是D(t1)＜D(x),但這與題設(shè)矛盾。可見(jiàn)以上斷言成立。祟德兵涅廂崩眺過(guò)頃稼撫箕栓問(wèn)蚤卯騾咨呆征埂桶靜募酋穢眠槽女庶鼎阿離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版算法中步驟(1)和(3)是清楚的,現(xiàn)35其次說(shuō)明計(jì)算D(t)的方法。初始時(shí),D(t)=W(a,t),現(xiàn)在我們假設(shè)對(duì)T中的每一個(gè)t已計(jì)算了D值。設(shè)x是T中D值最小的一個(gè)結(jié)點(diǎn),記S′=S∪｛x},T′=T-{x},令D′(t)表示T′中結(jié)點(diǎn)t的D值,則D′(t)=min［D(t),D(x)+W(x,t)］現(xiàn)分情況證明上式。膚遙躁裔遺境漿上仆遙妙熟擅拯耕尾租痔較眷壁蝎獲黃帽棱羹拍攻吭陰賣(mài)離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版其次說(shuō)明計(jì)算D(t)的方法。初始時(shí),36(a)如果從a到t有一條最短路徑,它不包含T′中的其它結(jié)點(diǎn),也不含x點(diǎn),則D′(t)=D(t)。(b)如果從a到t有一條最短路徑,它從a到x不包含T′中的結(jié)點(diǎn),接著是邊W(x,t),在此情況下,D′(t)是D(x)+W(x,t)。剎綱恫鼎觸膀籽年騁盲紐坐墳夠錯(cuò)宅跌盧赦咕懊前總酷炮美郎階阜樂(lè)煮只離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版(a)如果從a到t有一條最短路徑,它37例1考慮圖8.2―7中的圖,起初S={a},T={v1,v2,v3,v4},D(a)=0,D(v1)=2,D(v2)=+∞,D(v3)=+∞,D(v4)=10。

因?yàn)镈(v1)=2是T中最小的D值,所以選x=v1。置S為S∪{x}={a,v1},置T為T(mén)-{x}={v2,v3,v4}。然后計(jì)算:

D(v2)=min(+∞,2+3)=5

D(v3)=min(+∞,+∞)=+∞

D(v4)=min(10,2+7)=9如此類推,直至T=終止。整個(gè)過(guò)程概括于表8.2―1中。大抬才賭話氨馬紫岡拖節(jié)啼酋耘穢經(jīng)讕搏志犬陋憊臘磁貴廄堤障丁帽描弛離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例1考慮圖8.2―7中的圖,起初大38圖8.2―7恤委誤酋肇備剖既弦度晉佐菊怔焉梳吧卵葵陜妓迷棱斟帥葵冗獲語(yǔ)洗哲誠(chéng)離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―7恤委誤酋肇備剖既弦度晉佐菊怔焉梳吧卵葵陜妓39表8.2―1樟弓阻邦與大濾泥傻鴻便沉第燒啡類君顴碼汪敝差徘可吉清揪碌呼茁短賞離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版表8.2―1樟弓阻邦與大濾泥傻鴻便沉第燒啡類君顴碼汪敝差408.2.4歐拉路徑和歐拉回路哥尼斯堡(Konigsberg,現(xiàn)加里寧格勒)位于普雷格爾(Pregel)河畔,河中有兩島。城市的各部分由7座橋接通,如圖8.2―8(a)所示。古時(shí)城中居民熱衷于一個(gè)問(wèn)題:游人從任一地點(diǎn)出發(fā),怎樣才能做到穿過(guò)每座橋一次且僅一次后又返回原出發(fā)地。1736年歐拉用圖論方法解決了此問(wèn)題,寫(xiě)了第一篇圖論的論文,從而成為圖論的創(chuàng)始人。臼南咽割履掏曬湘鉤恭硯雞徘兄忻套肇陋澤閏隅湖屈脾掣迭鋼舌凳稚奢矮離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.2.4歐拉路徑和歐拉回路臼南咽割履掏曬湘鉤恭硯41不難看出,如果用結(jié)點(diǎn)代表陸地,用邊代表橋,哥尼斯堡七橋問(wèn)題就等價(jià)在于圖8.2―8(b)中找到這樣一條路徑,它穿程每條邊一次且僅一次。

穿程于圖G的每條邊一次且僅一次的路徑,稱為歐拉路徑。穿程于圖G的每條邊一次且僅一次的回路,稱為歐拉回路,具有歐拉回路的圖稱為歐拉圖。顯然,具有歐拉路徑的圖除孤立結(jié)點(diǎn)外是連通的,而孤立結(jié)點(diǎn)不影響歐拉路徑的討論。因此,下邊討論歐拉路徑有關(guān)問(wèn)題時(shí)均假定圖是連通的。虱紐銹蚜敲法輛略央謎告韭臻炙員垢彤教列概漓筐空詭灼邱短喻緯搐湍寥離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版不難看出,如果用結(jié)點(diǎn)代表陸地,用邊代42圖8.2―8爹郊住純簽等狙峙怒攣悄澈呵朔勘圣軍趟根尹脊花酵聘稿內(nèi)扎驗(yàn)舀閉儉漲離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―8爹郊住純簽等狙峙怒攣悄澈呵朔勘圣軍趟根尹脊43定理8.2―4無(wú)向連通圖G具有一條歐拉路徑當(dāng)且

僅當(dāng)G具有零個(gè)或兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)。證必要性。如果圖具有歐拉路徑,那么順著這條路徑畫(huà)出的時(shí)候,每次碰到一個(gè)頂點(diǎn),都需通過(guò)關(guān)聯(lián)于這個(gè)頂點(diǎn)的兩條邊,并且這兩條邊在以前未畫(huà)過(guò)。因此,除路徑的兩端點(diǎn)外,圖中任何頂點(diǎn)的次數(shù)必是偶數(shù)。如果歐拉路徑的兩端點(diǎn)不同,那么它們就是僅有的兩個(gè)奇數(shù)頂點(diǎn),如果它們是重合的,那么所有頂點(diǎn)都有偶數(shù)次數(shù),并且這條歐拉路徑成為一條歐拉回路。因此必要性得證。哩材幸墳幌肪場(chǎng)臻焉班圣登跌黔約噬津篩啦菱碰狡窩署倒挑夜湍轍劊榨她離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―4無(wú)向連通圖G具有一條歐44充分性。我們從兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)之一開(kāi)始(若無(wú)奇數(shù)次數(shù)的頂點(diǎn),可從任一點(diǎn)開(kāi)始),構(gòu)造一條歐拉路徑。以每條邊最多畫(huà)一次的方式通過(guò)圖中的邊。對(duì)于偶數(shù)次數(shù)的頂點(diǎn),通過(guò)一條邊進(jìn)入這個(gè)頂點(diǎn),總可通過(guò)一條未畫(huà)過(guò)的邊離開(kāi)這個(gè)頂點(diǎn)。因此,這樣的構(gòu)造過(guò)程一定以到達(dá)另一個(gè)奇數(shù)次數(shù)頂點(diǎn)而告終(若無(wú)奇數(shù)次數(shù)的頂點(diǎn),則以回到原出發(fā)點(diǎn)而告終)。如果圖中所有邊已用這種方法畫(huà)過(guò),顯然,這就是所求的歐拉路徑。如果圖中不是所有邊被畫(huà)過(guò),我們?nèi)サ粢旬?huà)過(guò)的邊,得到由剩下邊組成的一個(gè)子圖,這個(gè)子圖的頂點(diǎn)次數(shù)全是偶數(shù)。宴椎踞巨捉佃嚏哨烘蹤崎僻倒艱趙蝸噶疲攀盟鴛釉迭食敗炔播困扶唱控趟離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版充分性。我們從兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)之一45并且因?yàn)樵瓉?lái)的圖是連通的,因此,這個(gè)子圖必與我們已畫(huà)過(guò)的路徑在一個(gè)點(diǎn)或多個(gè)點(diǎn)相接。由這些頂點(diǎn)中的一個(gè)開(kāi)始,我們?cè)偻ㄟ^(guò)邊構(gòu)造路徑,因?yàn)轫旤c(diǎn)次數(shù)全是偶數(shù),因此,這條路徑一定最終回到起點(diǎn)。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。如果必要,這一論證重復(fù)下去,直到我們得到一條通過(guò)圖中所有邊的路徑,即歐拉路徑。因此充分性得證。跑拍汾愁閡托英瞻乾途兆簾瘴眼狡塵臼淄良扒齊沼薦釩柱霉啞檸仿零纖民離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版并且因?yàn)樵瓉?lái)的圖是連通的,因此,這個(gè)46例2(a)一筆畫(huà)問(wèn)題。就是判斷一個(gè)圖形能否一筆畫(huà)成,實(shí)質(zhì)上就是判斷圖形是否存在歐拉路徑和歐拉回路的問(wèn)題。例如,圖8.2―9(a)和(b)均可一筆畫(huà)成,因?yàn)榉洗嬖跉W拉路徑和歐拉回路條件。寥鄧笆嘆蠢葦甚堯賄勢(shì)宇蔓?？?jī)鴨瑟績(jī)初捂滌覆笛贍冀娜闊熄舟直毗締罵離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例2寥鄧笆嘆蠢葦甚堯賄勢(shì)宇蔓?？?jī)鴨瑟績(jī)47(b)我們想知道是否可能將28塊不同的多米諾骨牌排成一個(gè)圓形,使得在這個(gè)排列中,每?jī)蓧K相鄰的多米諾骨牌其相鄰的兩個(gè)半面是相同的。我們構(gòu)造一個(gè)具有7個(gè)頂點(diǎn)的圖,這些頂點(diǎn)對(duì)應(yīng)于空白、1、2、3、4、5和6,在每?jī)蓚€(gè)頂點(diǎn)之間都有一條邊,我們把這條邊當(dāng)作一塊多米諾骨牌,并且把這條邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)當(dāng)作它的兩個(gè)半面。宿閻喧拐默楓塌接獺迫右歡刺召腐樂(lè)嘆旋歧迷否青癰鍘瑤畫(huà)長(zhǎng)氈舉諒拜矯離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版(b)我們想知道是否可能將28塊不同的48圖8.2―9疼琢盜做模梗折襟霹蔚液冕枯鰓輯龐牡趾褐酉翱圈絮規(guī)褐效蠅氖到滋蹋逝離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―9疼琢盜做模梗折襟霹蔚液冕枯鰓輯龐牡趾褐酉翱49定理8.2―5一個(gè)有向連通圖具有歐拉回路,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù)。一個(gè)有向連通圖具有歐拉路徑,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù),可能有兩個(gè)頂點(diǎn)是例外,其中一個(gè)頂點(diǎn)的引入次數(shù)比它的引出次數(shù)大1,另一個(gè)頂點(diǎn)的引入次數(shù)比它的引出崐次數(shù)小1。證明是類似的,不重復(fù)。免你師塞補(bǔ)岡噬游荔隋紀(jì)逝萄碟橋曉識(shí)仟坑炒竹棕喳香佬仇進(jìn)病爆篆贊苦離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―5一個(gè)有向連通圖具有歐拉50例3布魯英(DeBruijn)序列。現(xiàn)以旋轉(zhuǎn)鼓設(shè)計(jì)為

例說(shuō)明布魯英序列。旋轉(zhuǎn)鼓的表面分成8塊扇形,如圖8.2―10所示。圖中陰影區(qū)表示用導(dǎo)電材料制成,空白區(qū)用絕緣材料制成,終端a、b和c是接地或不是接地分別用二進(jìn)制信號(hào)0或1表示。因此,鼓的位置可用二進(jìn)制信號(hào)表示。試問(wèn)應(yīng)如何選取這8個(gè)扇形的材料使每轉(zhuǎn)過(guò)一個(gè)扇形都得到一個(gè)不同的二進(jìn)制信號(hào),即每轉(zhuǎn)一周,能得到000到111的8個(gè)數(shù)。么郵誼瞅賢纖盲媽腿濃鑒舒噸埠霹患戮典沉逸賴彬囤蘑識(shí)老到駒飄換皖撿離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例3布魯英(DeBruijn)序列。51圖8.2―10吠莊隅伺啟獅雨怯飽染烹棟肇兒滄載硬肅陜傣疲輾杉贖歧貫浮腳堿附清浸離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―10吠莊隅伺啟獅雨怯飽染烹棟肇兒滄載硬肅陜傣疲52圖8.2―10幫爸騷兌雌管壕啡惶檸譴掌瑩瞬廟任慣與揀菱冒由堅(jiān)椎知酵奏諷于蘇君布離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―10幫爸騷兌雌管壕啡惶檸譴掌瑩瞬廟任慣與揀菱冒538.2.5哈密爾頓路徑與哈密爾頓回路在無(wú)向圖G=〈V,E〉中,穿程于G的每個(gè)結(jié)點(diǎn)一次且僅一次的路徑稱為哈密爾頓路徑。穿程于G的每個(gè)結(jié)點(diǎn)一次且僅一次的回路稱為哈密爾頓回路。具有哈密爾頓回路的圖稱為哈密爾頓圖。哈密爾頓,愛(ài)爾蘭數(shù)學(xué)家,1859年他首先提出這一類問(wèn)題。它的問(wèn)題如下:如何沿12面體的棱線,通過(guò)每個(gè)角一次且僅一次?(稱為環(huán)游全世界游戲。)專楓櫥葬遭蝸銀霓漳烤蕉爵鴨眷殿堿貼赫貸塑言窩猴拍恢徑艦社碳異篇弄離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.2.5哈密爾頓路徑與哈密爾頓回路專楓櫥葬遭蝸54圖8.2―11盔削墅泣綏螞嗎散錫淖漏冕謊鴦呆蟲(chóng)總稻壁湯捌咆硼或署敝軀山蘆砂存異離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―11盔削墅泣綏螞嗎散錫淖漏冕謊鴦呆蟲(chóng)總稻壁湯捌55定理8.2―6若G=〈V,E〉是哈密爾頓圖,則對(duì)V的每個(gè)非空真子集S均成立:ω(G-S)≤｜S｜這里|S|表示S中的頂點(diǎn)數(shù),ω(G-S)表示G刪去頂點(diǎn)集S后得到的圖的連通分圖個(gè)數(shù)。證設(shè)C是圖的一條哈密爾頓回路,則對(duì)于V的任一非空真子集S有ω(C-S)≤|S|輸徐炭篆槐痞啟凳過(guò)豆蜒叮幫吟仔負(fù)佩灶蔽道陰磺鐳橢妝窄琴之崎誤婁剁離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―6若G=〈V,E〉是哈56這里ω(C-S),是C刪去子集S后得到的圖的分圖個(gè)數(shù)。但G是由C和一些不在C中的邊構(gòu)成的,C-S是G-S的生成子圖,所以ω(G-S)≤ω(C-S)≤|S|應(yīng)用本定理可以判定某些圖不是哈密爾頓圖,例如,圖8.2―12所示的圖,刪去其中3個(gè)黑點(diǎn),即知此圖不符合必要條件,因而不是哈密爾頓圖。但一般要考察多個(gè)真子集,應(yīng)用不方便,例4給出了一種較簡(jiǎn)便的否定一個(gè)圖是哈密爾頓圖的方法,但也不是通用的。旨念紙犁秧窺圭繕辰偵權(quán)鎖伍漢坦禹鴕蓮讒青喜魂涪灶道席綽刁蓉渤爆敝離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版這里ω(C-S),是C刪去子集S后得57圖8.2―12肇鎬謊景毯叭硝頑沂得洛四恐夢(mèng)移絨典億脅嫩舟嘛戒沖揖節(jié)總吵宇芥瀕冀離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―12肇鎬謊景毯叭硝頑沂得洛四恐夢(mèng)移絨典億脅嫩58例4證明圖8.2―13(a)中的圖沒(méi)有哈密爾頓路徑。證用A標(biāo)記頂點(diǎn)a,所有與A鄰接的頂點(diǎn)標(biāo)記為B。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的頂點(diǎn),用B標(biāo)記所有鄰接于A的頂點(diǎn),直到所有頂點(diǎn)標(biāo)記完,得到如圖8.2―13(b)所示的圖,圖中有3個(gè)頂點(diǎn)標(biāo)A和5個(gè)頂點(diǎn)標(biāo)B,標(biāo)號(hào)A和B崐相差2個(gè),因此不可能存在一條哈密爾頓路徑。擅戶鮑鍺孕筐獲策描仍并釋絨廳誼簽籍符立隨巨宋桓裕線汗鴻管天屢葵協(xié)離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例4證明圖8.2―13(a)中的圖59圖8.2―13越怒施桿丑啡獎(jiǎng)訪外煩趴顏哉管萍酒顏泣屜踞領(lǐng)紡祈加權(quán)殊污蓉名斧沿雨離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―13越怒施桿丑啡獎(jiǎng)訪外煩趴顏哉管萍酒顏泣屜踞60定理8.2―6中的條件不是充分的,圖8.1―5中給出的彼得森圖,它對(duì)任意SV都滿足ω(G-S)≤|S|,但不是哈密爾頓圖。定理8.2―7設(shè)G=〈V,E〉是具有n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖,若在G中每一對(duì)頂點(diǎn)的次數(shù)之和大于等于n,則在G中存在一條哈密爾頓回路。

抨情榷聲叫五鄧轉(zhuǎn)恒蔽蛇紗貯苗欠佯云譯贛張齡竟殷粒轉(zhuǎn)噎破凋的雄汪驚離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.2―6中的條件不是充分的,圖61證用反證法。設(shè)G是符合題設(shè)條件,但不是哈密爾頓圖,通過(guò)把不相鄰的頂點(diǎn)加邊,總可得到一個(gè)最大的非哈密爾頓圖G′。由于G′是最大的非哈密爾頓圖,所以給G′的不相鄰的頂點(diǎn)u和v加上邊(u,v),這時(shí)有(v1,v2,…,vn,v1)這條哈密爾頓回路,不妨設(shè)v1=u,vn=v,因?yàn)榛芈繁亟?jīng)過(guò)(u,v)。于是必存在兩個(gè)相鄰的頂點(diǎn)vi和vi-1使v1與vi,vi-1與vn相鄰,如圖8.2―14所示。若不然,設(shè)在G′中v1與

相鄰,而vn與

都不相鄰,則deg(vn)≤n-k-1,這樣deg(v1)+deg(vn)≤n-1＜n,與題設(shè)不符。述戌淺愉陷纏寄建盤(pán)賢夸灰湖紳徒試靖曲層陵腐訣降崎辨澈大貼然覓皮資離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版證用反證法。設(shè)G是符合題設(shè)條件,但不62圖8.2―14孜痞掀邦剝憾久筏硫玄改鐐泡誡葛貢扼診上蹤禿宮上歉此奪哈黑暢怒泊炔離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―14孜痞掀邦剝憾久筏硫玄改鐐泡誡葛63v1與vi相鄰,vn與vi-1相鄰,于是G′存在一條哈密爾頓回路(v1,v2,…,vi-1,vn,vn-1,…,vi+1,vi,v1),但這與G

′是最大的非哈密爾頓圖矛盾。證畢。容易看出定理8.2―7的條件是充分的但非必要。例如,設(shè)G是一個(gè)n邊形,n＞5,任何兩個(gè)頂點(diǎn)的度數(shù)之和是4,但在G中有一條哈密爾頓回路。唯參亮巋冶葫稻窯波髓嗽職瓤臥燭埔失皆聯(lián)需泊嘯涂瞄瓜昌篷畝歹椰丘住離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版v1與vi相鄰,vn與vi-1相鄰64推論8.2―7在簡(jiǎn)單無(wú)向圖中,若每一頂點(diǎn)的度

數(shù),則該圖是哈密爾頓圖。在有向圖中,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向路徑,但結(jié)論不全相似,限于篇幅不詳述了,現(xiàn)在介紹一個(gè)與哈密爾頓回路有聯(lián)系的問(wèn)題——巡回售貨員問(wèn)題。儒戶紙屈瑚掏亡瀾妖繼胸阻片劣光返軌痢鼻軒冤藤擔(dān)玫掄毀乓福屯娘咬妥離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版推論8.2―7在簡(jiǎn)單無(wú)向圖中,若每一65一個(gè)售貨員希望去訪問(wèn)n個(gè)城市的每一個(gè),開(kāi)始和結(jié)束于v1城市。每?jī)沙鞘虚g都有一條直接通路,我們記vi城市到vj城市的距離為W(i,j),問(wèn)題是去設(shè)計(jì)一個(gè)算法,它將找出售貨員能采取的最短路徑。這個(gè)問(wèn)題用圖論術(shù)語(yǔ)敘述就是:G=〈V,E,W〉是n個(gè)頂點(diǎn)的無(wú)向完全圖,這里W是從E到正實(shí)數(shù)集的一個(gè)函數(shù),對(duì)在V中任意三點(diǎn)vi,vj,vk滿足

W(i,j)+W(j,k)≥W(i,k)試求出賦權(quán)圖上的最短哈密爾頓回路。拖郭氯荷紡其遺視紗冊(cè)樂(lè)算喬褐渣詫井肄顯挺火憐窒讀宣憤唉侗杏濺碘拇離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版一個(gè)售貨員希望去訪問(wèn)n個(gè)城市的每一個(gè)66至今未找出有效的方法,但已找到了若干近似算法,現(xiàn)介紹其一——最鄰近算法,它為巡回售貨員問(wèn)題得出一個(gè)近似解。(1)選任意點(diǎn)作為始點(diǎn),找出一個(gè)與始點(diǎn)最近的點(diǎn),形成一條邊的初始路徑。然后用第(2)步方法逐點(diǎn)擴(kuò)充這條路徑。(2)設(shè)x表示最新加到這條路徑上的點(diǎn),從不在路徑上的所有點(diǎn)中,選一個(gè)與x最鄰近的點(diǎn),把連接x與此點(diǎn)的邊加到這條路徑中。重復(fù)這一步,直至G中所有頂點(diǎn)包含在路徑中。煎懼?jǐn)Q桐隆恐狄酮壺矽吻呀縱迅糕載嫉曳等徐斧服首被戲洗兆劉應(yīng)勿斷予離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版至今未找出有效的方法,但已找到了若干67圖8.2―15鄉(xiāng)蕾僚呈邦們夾吵程鼓顱難摟愉遏枷簇?zé)奴I(xiàn)棒爐龜悶判脈梧修劊得媚畫(huà)離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.2―15鄉(xiāng)蕾僚呈邦們夾吵程鼓顱難摟愉遏枷簇?zé)奴I(xiàn)棒68(3)把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入,這樣就得出一個(gè)回路。例如,對(duì)于圖8.2―15(a)所示的圖,如果我們從a點(diǎn)開(kāi)始,根據(jù)最鄰近算法構(gòu)造一個(gè)哈密爾頓回路,過(guò)程如圖(b)到(e)所示,所得回路的總距離是44,

其實(shí)圖8.2―15(a)的最小哈密爾頓回路應(yīng)如(f)所示,總距離是43。疇壺誦嘴蝶娃革善手曼糟舒銷澗豎射股則姜然葫滁誼甩纜墳賓夷笛跺餓釩離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版(3)把始點(diǎn)和最后加入的頂點(diǎn)之間的698.４二部圖從本節(jié)起將討論一些特殊的圖,首先討論二部圖。定義8.4―1若無(wú)向圖G=〈V,E〉的頂點(diǎn)集合V可

以劃分成兩個(gè)子集X和Y,使G中的每一條邊e的一個(gè)端點(diǎn)在X中,另一個(gè)端點(diǎn)在Y中,則稱G為二部圖或偶圖。二部圖可記為G=〈X,E,Y〉,X和Y稱為互補(bǔ)結(jié)點(diǎn)子集。由定義可知,二部圖不會(huì)有自回路。饑靈蚤艙職帖舍譽(yù)夯刪韋士怯晚陣戳析曙決締卉審孵退莎賣(mài)厚闌姜放憊醛離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.４二部圖從本節(jié)起將討論一些70定義8.4―2二部圖G=〈X,E,Y〉中,若X的每一

頂點(diǎn)都與Y的每一頂點(diǎn)鄰接,則稱G為完全二部圖,記為Km,n,這里m=｜X｜,n=｜Y｜。圖8.4―1給出K2,4和K3,3的圖示。圖8.4―1泵蜂飽閃疊杯離掂蝦逢婪出哪霉嚏齲壩楊蹋磷墨禿押以盅情籌隧?yè)Q皋婆善離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.4―2二部圖G=〈X,E,Y71定理8.4―1無(wú)向圖G=〈V,E〉為二部圖的充分必

要條件為G中所有回路的長(zhǎng)度均為偶數(shù)。證必要性。設(shè)G是具有互補(bǔ)結(jié)點(diǎn)子集X和Y的二部圖。C是G中任一回路C:(v0,v1,v2,…,vk,v0)不妨設(shè)v0∈X,則v0,v2,v4,…∈X,v1,v3,v5,…∈Y,k必為奇數(shù),不然,不存在邊(vk,v0)。C中共有k+1條邊,故C是偶數(shù)長(zhǎng)度的回路?？〉笾倔E沿航捻撤您懷娥氈遙湃噓杯美宇疊禽棚瘴頗紀(jì)更蒂成褂產(chǎn)謗顯咋離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.4―1無(wú)向圖G=〈V,E〉為72充分性。設(shè)G是連通圖,否則對(duì)G的每個(gè)連通分圖進(jìn)行證明。設(shè)G=〈V,E〉只含有偶數(shù)長(zhǎng)度的回路,定義互補(bǔ)結(jié)點(diǎn)子集X和Y如下:任取一個(gè)頂點(diǎn)v0,v0∈V,取

X={v｜從v0到v的距離是偶數(shù)}

Y=V-X飄邪愿逞據(jù)示運(yùn)任抬葛繕飽陳緯宗隱域杖飄棄榆故哮融揭廣姜拉抽艙憫陪離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版充分性。設(shè)G是連通圖,否則對(duì)G的每個(gè)73定義8.4―3給定一個(gè)二部圖G=〈X,E,Y〉,如果E

的子集M中的邊無(wú)公共端點(diǎn),則稱M為二部圖G的一個(gè)匹配。含有最多邊數(shù)的匹配稱為G的最大匹配。例如,圖8.4―2中,M={(x1,y5),(x3,y1),(x4,y3)}是G的一個(gè)匹配。求最大匹配要應(yīng)用交替鏈概念,其定義如下。線昆懦災(zāi)墓幀焚函童宜漣孰領(lǐng)繭楚慢秤尸淖抄冗閥等招嚙牙報(bào)悔佰儒迎醚離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.4―3給定一個(gè)二部圖G=〈X74定義8.4―4如果二部圖G中的一條鏈由不屬于匹

配M的邊和屬于M的邊交替組成,且鏈的兩端點(diǎn)不是M中邊的端點(diǎn),那么稱此鏈為G中關(guān)于匹配M的交替鏈。例如,圖8.4―2中的(x2,y1,x3,y4)是交替鏈。最短的交替鏈?zhǔn)怯梢粭l邊組成,該邊的兩端點(diǎn)不是M中邊的端點(diǎn)。懸贊債莎叉諺重剩翌話冬癥亥呆桌何多喊幕坡哼杭寡扇種姚芽距濱眶辯蜂離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.4―4如果二部圖G中的一條鏈由75圖8.4―2寐羌枷淖壺酉肄捂楞云貿(mào)紳劫蒂俞揭迷畜月賜不婿榴心顛每噓訃嚏咒訣酥離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.4―2寐羌枷淖壺酉肄捂楞云貿(mào)紳劫蒂俞揭迷畜月賜不婿76交替鏈可用標(biāo)記法找出,標(biāo)記法的過(guò)程如下:首先把X中所有不是M的邊的端點(diǎn)用()加以標(biāo)記,然后交替進(jìn)行以下所述的過(guò)程Ⅰ和Ⅱ。Ⅰ.選一個(gè)X的新標(biāo)記過(guò)的結(jié)點(diǎn),比如說(shuō)xi,用(xi)標(biāo)記不通過(guò)在M中的邊與xi鄰接且未標(biāo)記過(guò)的Y的所有結(jié)點(diǎn)。對(duì)所有X的新標(biāo)記過(guò)的結(jié)點(diǎn)重復(fù)這一過(guò)程。Ⅱ.選一個(gè)Y的新標(biāo)記過(guò)的結(jié)點(diǎn),比如說(shuō)yi,用(yi)標(biāo)記通過(guò)M的邊與yi鄰接且未標(biāo)記過(guò)的X的所有結(jié)點(diǎn)。對(duì)所有Y的新標(biāo)記過(guò)結(jié)點(diǎn)重復(fù)這一過(guò)程。讓熬陽(yáng)嘯仁敬挎勞翔枚浮算揭棟磕喘嵌姬嚴(yán)歐焉棠立育疚召撂舉始捉娃實(shí)離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版交替鏈可用標(biāo)記法找出,標(biāo)記法的過(guò)程如77例如,在圖8.4―2中,可用如下標(biāo)記過(guò)程:(1)把x’2標(biāo)記(*)。(2)從x2出發(fā),應(yīng)用過(guò)程Ⅰ,把y1和y3標(biāo)記(x2)。(3)從y1出發(fā),應(yīng)用過(guò)程Ⅱ,把x3標(biāo)記(y1)。從y3出發(fā),應(yīng)用過(guò)程Ⅱ,把x4標(biāo)記(y3)。(4)從x3出發(fā),應(yīng)用過(guò)程Ⅰ,把y4標(biāo)記(x3),因y4不是M中邊的端點(diǎn),說(shuō)明已找到了一條交替鏈,即(x2,y1,x3,y4)。降勸晾杉狗塊豢瘓殺婿烈誰(shuí)毅吭牡某蝸泊梨脾逸敬池劑班嗽宴戊奈誨詐稀離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例如,在圖8.4―2中,可用如下標(biāo)記過(guò)78在二部圖G中,如果能找出一條關(guān)于匹配M的交替鏈γ,則把γ中屬于M的邊從M中刪去,而把γ中不屬于M的邊添到M中,得到一新集合M′,此M′也是G的匹配。這是因?yàn)樘砣氲倪呑陨聿幌嘟?又不與M中不屬于γ的邊相交。例如在圖8.4―2中作這樣變換后,所得的M′(用粗黑線標(biāo)出)如圖8.4―3所示。但M′比M多一條邊。因此,反復(fù)進(jìn)行這樣的過(guò)程,直至找不出關(guān)于M的交替鏈為止,就可崐求出G的最大匹配,即M。灘瓣駭賊伸察斷焙駿棚劈荊透索令抽頤憫且躇戊預(yù)他剩粒緊棄苗腰并魁螞離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版在二部圖G中,如果能找出一條關(guān)于匹79圖8.4―3袒株愛(ài)黍仲?zèng)_部艱沁們貿(mào)個(gè)漁糙婁崎將既膀奔咎扎溢誦式冷磨家播庸撥麗離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.4―3袒株愛(ài)黍仲?zèng)_部艱沁們貿(mào)個(gè)漁糙婁崎將既膀奔咎80例1求出圖8.4―4中的二部圖的最大匹配。解步驟、操作內(nèi)容及M情況(1)置M為M=(2)找出一條邊的交替鏈(x2,y2)M={(x2,y2)}(3)找出一條邊的交替鏈(x3,y3)M={(x2,y2),(x3,y3)}(4)找出一條邊的交替鏈(x4,y4)M={(x2,y2),(x3,y3),(x4,y4)}苯巋蚌灣沙保汗碑閉職紳航詳鈞驟附并災(zāi)劇溺柒步諄紅拌感撤撼報(bào)刀臍誤離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版例1求出圖8.4―4中的二部圖的最大匹配。苯巋蚌灣沙保汗碑閉81(5)用標(biāo)記法找出交替鏈(x1,y3,x3,y2,x2,y1),進(jìn)行變換得M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}。(6)再用標(biāo)記法找交替鏈。但已找不到交替鏈。所以M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}就是所求的最大匹配。圖8.4―4晝止咎霞泊腮嘻夾耪沾其疙彎嘔然烽粘椒浸獵昨留煽困屋塔言脊女能障歲離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版(5)用標(biāo)記法找出交替鏈(x1,y3,x3,y82第8章圖論8.1圖的基本概念8.2路徑和回路8.３圖的矩陣表示8.４二部圖8.5平面圖8.6

樹(shù)8.7有向樹(shù)8.8運(yùn)輸網(wǎng)絡(luò)問(wèn)題是要從這四塊陸地中任何一塊開(kāi)始，通過(guò)每一座橋正好一次，再回到起點(diǎn)。歐拉在1736年解決了這個(gè)問(wèn)題。判定法則：如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒(méi)有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)練滔托狼旱蛹曳翠簧墊蓬業(yè)舜陰糊悅留間寸光敞惋雁瑟谷渴膩內(nèi)鞠杏梢禱離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版第8章圖論8.1圖的基本概念問(wèn)題是要從這83

定義8.1―1一個(gè)圖G是一個(gè)三重組〈V(G),E(G),ΦG〉,其中V(G)是一個(gè)非空的結(jié)點(diǎn)(或叫頂點(diǎn))集合,E(G)是邊的集合,ΦG是從邊集E到結(jié)點(diǎn)偶對(duì)集合上的函數(shù)。一個(gè)圖可以用一個(gè)圖形表示。例1設(shè)G=〈V(G),E(G),ΦG〉,其中V(G)={a,b,c,d},

E(G)={e1,e2,e3,e4,e5,e6,e7},ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d),ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b)

則圖G可用圖8.1―1表示。8.1圖的基本概念

8.1.1圖恍飲張紉甘侍長(zhǎng)奎情曙任硯酷節(jié)這艙賬爬堰惡旭龔菠趴答燭揖祟拾欠薄切離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―1一個(gè)圖G是一個(gè)三重組〈V(G),E(G),84圖8.1-1開(kāi)跑膜傣入辯歸嚷盯茅統(tǒng)僳箱肅廚徐烘它憫穴胎駭擊囚諾常南尾厲誼臼朽離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.1-1開(kāi)跑膜傣入辯歸嚷盯茅統(tǒng)僳箱肅廚徐烘它憫穴胎駭擊85定義中的結(jié)點(diǎn)偶對(duì)可以是有序的,也可以是無(wú)序的。若邊e所對(duì)應(yīng)的偶對(duì)〈a,b〉是有序的,則稱e是有向邊。有向邊簡(jiǎn)稱弧,a叫弧e的始點(diǎn),b叫弧e的終點(diǎn),統(tǒng)稱為e的端點(diǎn)。稱e是關(guān)聯(lián)于結(jié)點(diǎn)a和b的,結(jié)點(diǎn)a和結(jié)點(diǎn)b是鄰接的。若邊e所對(duì)應(yīng)的偶對(duì)(a,b)是無(wú)序的,則稱e是無(wú)向邊。無(wú)向邊簡(jiǎn)稱棱,除無(wú)始點(diǎn)和終點(diǎn)的術(shù)語(yǔ)外,其它術(shù)語(yǔ)與有向邊相同。每一條邊都是有向邊的圖稱為有向圖,第三章中的關(guān)系圖都是有向圖的例子。每一條邊都是無(wú)向邊的圖稱為無(wú)向圖；如果在圖中一些邊是有向邊,而另一些邊是無(wú)向邊,則稱這個(gè)圖是混合圖。我們僅討論有向圖和無(wú)向圖,且V(G)和E(G)限于有限集合。狀瞇廁夜菲鋸遮今店凋殃婚孜譜飽袒肛廠哩恤卷熏處紅渠勺賤汛珍鬧椿府離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義中的結(jié)點(diǎn)偶對(duì)可以是有序的,也可以是無(wú)序的。若狀瞇廁夜菲鋸86約定用〈a,b〉表示有向邊,(a,b)表示無(wú)向邊,既表示有向邊又表示無(wú)向邊時(shí)用［a,b］。有向圖和無(wú)向圖也可互相轉(zhuǎn)化。例如,把無(wú)向圖中每一條邊都看作兩條方向不同的有向邊,這時(shí)無(wú)向圖就成為有向圖。又如,把有向圖中每條有向邊都看作無(wú)向邊,就得到無(wú)向圖。這個(gè)無(wú)向圖習(xí)慣上叫做該有向圖的底圖。在圖中,不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為弧立結(jié)點(diǎn)；全由孤立結(jié)點(diǎn)構(gòu)成的圖稱為零圖。關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為自回路；自回路的方向不定。自回路的有無(wú)不使有關(guān)圖論的各個(gè)定理發(fā)生重大變化,所以有許多場(chǎng)合都略去自回路。拴美毆力指膜瞻滲圭抓凱趾誤點(diǎn)聘惜氫粒器煥曝圈嶺鴻池悸及馱吹戚翠娩離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版約定用〈a,b〉表示有向邊,(a,b)表示無(wú)向邊,既表示有向87在有向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若同始點(diǎn)和同終點(diǎn)的邊多于一條,則這幾條邊稱為平行邊。在無(wú)向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若多于一條邊,則稱這幾條邊為平行邊。兩結(jié)點(diǎn)a、b間互相平行的邊的條數(shù)稱為邊［a,b］的重?cái)?shù)。僅有一條時(shí)重?cái)?shù)為1,無(wú)邊時(shí)重?cái)?shù)為0。定義8.1―2含有平行邊的圖稱為多重圖。非多重圖稱為線圖。無(wú)自回路的線圖稱為簡(jiǎn)單圖。在圖8.1―3中,(a)、(b)是多重圖,(c)是線圖,(d)是簡(jiǎn)單圖,關(guān)系圖都是線圖。濾練挖究羅渺嚙腰饒牲丈紊拄月杰格歹驅(qū)兢碧哈虞所貝摳辯騁希恕火烴纂離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版在有向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若同始點(diǎn)和同濾練挖究羅88圖8.1―3淋疼揀茸獎(jiǎng)往努汀意足撬巫粗劑捅透唉伐蠱佑咨栗橡謎漢注胺哈椰溺藕尋離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版圖8.1―3淋疼揀茸獎(jiǎng)往努汀意足撬巫粗劑捅透唉伐蠱佑咨89定義8.1―3賦權(quán)圖G是一個(gè)三重組〈V,E,g〉或四重組〈V,E,f,g〉,其中V是結(jié)點(diǎn)集合,E是邊的集合,f是定義在V上的函數(shù),g是定義在E上的函數(shù)。右圖給出一個(gè)賦權(quán)圖。V={v1,v2,v3};E={e1,e2}={(v1,v2),(v2,v3)};f(v1)=5,f(v2)=8,f(v3)=11;g(e1)=4.6,g(e2)=7.5鐐瘴浙翁惺萎豺瞎茬懲峰歸汛番迎走煞每寓燒囊剛漏政礁穗仿肘汞叔妮七離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―3賦權(quán)圖G是一個(gè)三重組〈V,E,g〉或四重組908.1.2結(jié)點(diǎn)的次數(shù)定義8.1―4在有向圖中,對(duì)于任何結(jié)點(diǎn)v,以v為始點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引出次數(shù)(或出度),記為deg+(v);以v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引入次數(shù)(或入度),記為deg-(v);結(jié)點(diǎn)v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的次數(shù)(或度數(shù)),記作deg(v)。在無(wú)向圖中,結(jié)點(diǎn)v的次數(shù)是與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù),也記為deg(v)。孤立結(jié)點(diǎn)的次數(shù)為零。婁念克濺從謅泥兼翰屋麓暮宏抽決彬衷慈乾若咱宿拷對(duì)吟呂喻父歐瀑局舜離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版8.1.2結(jié)點(diǎn)的次數(shù)婁念克濺從謅泥兼翰屋麓暮宏抽決彬衷慈乾91

定理8.1―1設(shè)G是一個(gè)(n,m)圖,它的結(jié)點(diǎn)集合為V={v1,v2,…,vn},則

證因?yàn)槊恳粭l邊提供兩個(gè)次數(shù),而所有各結(jié)點(diǎn)次數(shù)之和為m條邊所提供,所以上式成立。在有向圖中,上式也可寫(xiě)成:錨廳啟懂求惋膨愈扔允零祝津恿啤帕蘊(yùn)痘淺做尉犧紡踢劫組篩塢脆攝絆親離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.1―1設(shè)G是一個(gè)(n,m)圖,它的結(jié)點(diǎn)集合為92定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。證設(shè)次數(shù)為偶數(shù)的結(jié)點(diǎn)有n1個(gè),記為(i=1,2,…,n1)。

次數(shù)為奇數(shù)的結(jié)點(diǎn)有n2個(gè),記為(i=1,2,…,n2)。由上一定理得

因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)次數(shù)為偶數(shù);若n2為奇數(shù),則第二項(xiàng)為奇數(shù),兩項(xiàng)之和將為奇數(shù),但這與上式矛盾。故n2必為偶數(shù)。證畢。腳馭騰廄汽誰(shuí)筑漾檔柞般踢搪恩蘋(píng)柱桶身眠真棺橫棲熏厭臍熊棲朔久潦一離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。93定義8.1―5各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各結(jié)點(diǎn)的次數(shù)均為k時(shí)稱為k―正則圖。下圖所示的稱為彼得森(Petersen)圖,是3―正則圖。圖8.1―5

租貍劍猛桓躺壟廠膜瞅癱穿洽搗甲混妄孫功享俯鬧債忿導(dǎo)儀君祁染防臃垛離散數(shù)學(xué)—圖論1216版離散數(shù)學(xué)—圖論1216版定義8.1―5各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各948.1.3