第八章圖論原理

第八章圖論原理第一頁，共七十三頁，編輯于2023年，星期五圖論圖論是用圖的方法研究客觀世界的一門科學(xué).用“結(jié)點”表示事物,用“邊”表示事物之間聯(lián)系,而由結(jié)點與邊所構(gòu)成的圖表示所研究的客觀對象.圖論研究圖的邏輯結(jié)構(gòu)與性質(zhì)，是研究圖的抽象性質(zhì)的一種數(shù)學(xué).第二頁，共七十三頁，編輯于2023年，星期五圖論圖論在語言學(xué)、邏輯學(xué)、物理學(xué)、化學(xué)、電氣工程、計算機網(wǎng)絡(luò)、計算機科學(xué)及數(shù)學(xué)的其他分支中有廣泛應(yīng)用.在計算機科學(xué)中，圖論在形式語言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)及數(shù)據(jù)庫研究中均有很重要的應(yīng)用.本篇結(jié)構(gòu)第八章介紹圖論一般原理第九章介紹一些常用的圖如平面圖、兩步圖以及樹等第三頁，共七十三頁，編輯于2023年，星期五第八章圖論原理本章主要介紹圖論的基本原理，包括圖論中的基本概念、基本方法以及圖論的矩陣計算等內(nèi)容.第四頁，共七十三頁，編輯于2023年，星期五8.1.1圖起源：歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景。

LeonhardEuler，(1707—1783)，瑞士數(shù)學(xué)家、力學(xué)家、天文學(xué)家、物理學(xué)家，圖論的創(chuàng)始人，變分法的奠基人，復(fù)變函數(shù)論的先驅(qū)者，理論流體力學(xué)的創(chuàng)始人。第五頁，共七十三頁，編輯于2023年，星期五8.1.1圖著名的柯尼斯堡七橋問題。在柯尼斯堡的普萊格爾河上有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來，如下圖所示，A、B、C，D表示陸地。問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點。第六頁，共七十三頁，編輯于2023年，星期五8.1.1圖歐拉在1736年解決了這個問題，他用抽象分析法將這個問題化為第一個圖論問題：即把每一塊陸地用一個點來代替，將每一座橋用聯(lián)接相應(yīng)的兩個點的一條線來代替，從而相當(dāng)于得到一個「圖」。歐拉證明了這個問題沒有解，并且推廣了這個問題，給出了對於一個給定的圖可以某種方式走遍的判定法則。這項工作使歐拉成為圖論〔及拓撲學(xué)〕的創(chuàng)始人。第七頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念定義8.1

圖G是由非空結(jié)點集合V={v1,v2,…,vn}以及邊集合E={l1,l2,…,lm}所組成,其中每條邊可用一個節(jié)點對表示,亦即li=(vi1,vi2),i=1,2,…,m 這樣一個圖G可用G=<V,E>表示第八頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念例8.1有4個城市:v1,v2,v3,v4,其中v1與v2間;v1與v4間;v2與v3間有直達長話線路相連,將此試試用圖的方式表示解: 圖中的結(jié)點集為:V={v1,v2,v3,v4} 邊集為E={l1,l2,l3} l1={v1,v2},l2={v1,v4},l3={v2,v3},-------無序結(jié)點對 這個圖可以用G=<V,E>表示

第九頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念例8.2有4個程序p1,p2,p3,p4,它們間有一些調(diào)用關(guān)系：p1調(diào)用p2；p2能調(diào)用p3；p1能調(diào)用p4,試將此事實用圖的方式表示.解： 圖中的結(jié)點集為:V={p1,p2,p3,p4} 邊集為E={c1,c2,c3} c1={p1,p2},c2={p2,p3},c3={p1,p4},-----有序結(jié)點對 這個圖可以用G=<V,E>表示第十頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念一般，用帶有箭頭的邊表示有序結(jié)點對，而用不帶箭頭的邊表示無序結(jié)點對.第十一頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念有序結(jié)點對所對應(yīng)的邊稱為有向邊，無序結(jié)點對所對應(yīng)的邊稱為無向邊有向圖：圖中的所有邊均為有向邊無向圖：圖中的所有邊均為無向邊第十二頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念有向邊lk={vi,vj}中,vi稱為lk的起點,vj稱為lk的終點不管lk是有向還是無向,均稱lk與vi和vj相關(guān)聯(lián),而vi和vj稱為鄰接的.若干條邊關(guān)聯(lián)于同一個結(jié)點,則這些邊稱為鄰接的.第十三頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念一條邊若與兩個相同的結(jié)點相關(guān)聯(lián),則稱為環(huán),即lk={vi,vi}不與任何結(jié)點相鄰的結(jié)點稱為孤立點第十四頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念圖G=<V,E>與G’=<V’,E’>間如果有V’?V,E?E’,則稱G’是G的子圖.如果有V’?V,E?E’,則稱G’是G的真子圖.如果有V’=V,E?E’,則稱G’是G的生成子圖.第十五頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念(n,m)圖:一個具有n個結(jié)點、m條邊所組成的圖零圖:由一些孤立點組成的圖,即(n,0)圖平凡圖:由一個孤立結(jié)點組成的圖,即(1,0)圖完全圖:一個(n,m)圖G如果其n個結(jié)點(n≥2)中的每一個均與其中n-1個結(jié)點鄰接,可記為Kn.m=n(n-1)/2第十六頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念第十七頁，共七十三頁，編輯于2023年，星期五8.1.2圖的基本概念補圖： 設(shè)有一圖G=(V,E),對圖G’=(V,E’),如果有 是完全圖且E∩E’=? 則稱G’是G的補圖.一個圖與其補圖是互補的一個圖的補圖的補圖還是自己第十八頁，共七十三頁，編輯于2023年，星期五8.1.3圖的同構(gòu)定義8.2 設(shè)有圖G=<V,E>與G’=<V’,E’>,如果它們的結(jié)點間存在一一對應(yīng)關(guān)系,而且這種對應(yīng)關(guān)系也反映在表示邊的結(jié)點對中(如果是有向邊,則對應(yīng)的結(jié)點對還保持相同的順序),則稱此兩圖是同構(gòu)的.第十九頁，共七十三頁，編輯于2023年，星期五8.1.3圖的同構(gòu)(a)(b)同構(gòu)，(c)(d)同構(gòu)第二十頁，共七十三頁，編輯于2023年，星期五8.1.4圖中結(jié)點的次數(shù)定義8.3在有向圖中,以結(jié)點v為起點的邊的條數(shù)稱為v的引出次數(shù),記以deg(v);以v為終點的邊的條數(shù)叫v的引入次數(shù),記以deg(v);v的引入次數(shù)與引出次數(shù)之和稱為v的次數(shù)或全次數(shù),記為deg(v).在無向圖中,結(jié)點v的次數(shù)或全次數(shù)是與v相關(guān)聯(lián)的邊的條數(shù),也用deg(v)表示.任一圖的所有結(jié)點的次數(shù)之和必為偶數(shù),且必為圖中邊數(shù)的兩倍,因為每條邊必與兩個結(jié)點相關(guān)聯(lián).第二十一頁，共七十三頁，編輯于2023年，星期五8.1.4圖中結(jié)點的次數(shù)題(8.1)設(shè)V={u,v,w,x,y},畫出圖G=<V,E>： 1)E={(u,v),(u,x),(v,w),(v,y)(x,y)} 2)E={(u,v),(v,w),(w,x),(w,y)(x,y)} 再求每個結(jié)點的次數(shù).解： 1) 2)

1)中結(jié)點：deg(u)=2,deg(v)=3,deg(w)=1,deg(x)=2,deg(y)=2. 2)中結(jié)點：deg(u)=1,deg(v)=2,deg(w)=3,deg(x)=2,deg(y)=2.uwvxyuwvxy第二十二頁，共七十三頁，編輯于2023年，星期五8.1.4圖中結(jié)點的次數(shù)定理8.1圖G=<V,E>是一個(n,m)圖,其中V={v1,v2,…,vn},此時有d次正則圖：所有結(jié)點均有相同次數(shù)d的圖.第二十三頁，共七十三頁，編輯于2023年，星期五8.1.4圖中結(jié)點的次數(shù)例：任何圖G中必有偶數(shù)個() A.引入次數(shù)為奇數(shù)的結(jié)點 B.引出次數(shù)為奇數(shù)的結(jié)點 C.次數(shù)為偶數(shù)的結(jié)點 D.次數(shù)為奇數(shù)的結(jié)點解： 引入次數(shù)與引出次數(shù)均指有向圖,這里是所有圖 因為圖中結(jié)點次數(shù)的總和為偶數(shù),因此次數(shù)為奇數(shù)的結(jié)點數(shù)目為偶數(shù).所以選D.第二十四頁，共七十三頁，編輯于2023年，星期五8.1.5多重圖與帶權(quán)圖多重圖：一個結(jié)點對可對應(yīng)若干條邊,這種邊稱為多重邊方向相反的兩條邊可看成是由不同的結(jié)點對對應(yīng)的.簡單圖：不包含多重邊的圖第二十五頁，共七十三頁，編輯于2023年，星期五8.1.5多重圖與帶權(quán)圖例：三個點可構(gòu)成多少個不同構(gòu)的簡單無向圖？解： 1)有點無邊 2)有一條邊 3)有兩條邊 4)有三條邊 所以一共有4個.第二十六頁，共七十三頁，編輯于2023年，星期五8.1.4圖中結(jié)點的次數(shù)有權(quán)圖：在一個圖中的旁側(cè)可以附加一些數(shù)字來刻畫此邊的某些數(shù)量特征(如兩地距離,車流量限制),稱為邊的權(quán),此邊叫有權(quán)邊,具有有權(quán)邊的圖稱為有權(quán)圖.無權(quán)圖：不具有有權(quán)邊的圖.第二十七頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路設(shè)有向圖G=<V,E>,考慮G中邊的序列(vi1,vi2),(vi2,vi3),…,(vik-1,vik),可簡寫為(vi1,vi2,vi3,…,vik)此序列中可以允許多次出現(xiàn)相同的結(jié)點與邊,在此序列中除vi1和vik外,中間每個結(jié)點均與其前、后結(jié)點相連接,這種邊的序列稱為圖的通路,而vi1和vik分別叫通路的起始結(jié)點與終止結(jié)點,通路中邊的數(shù)目稱為通路的長度.有向圖中各邊全不同的通路稱為簡單通路,各點全不同的稱為基本通路.一條基本通路一定是簡單通路,但一條簡單通路則不一定是基本通路.第二十八頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路例：圖中開始于結(jié)點1結(jié)束于結(jié)點3的通路有： P1:(1,2,3) P2:(1,4,3) P3:(1,2,4,3) P4:(1,2,4,1,2,3) P5:(1,2,4,1,4,3) P6:(1,1,1,2,3)P1,P2,P3均是基本通路P5是簡單回路但不是基本通路第二十九頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路圖中的一條通路如果其起始結(jié)點與終止結(jié)點相同,則稱此通路為回路.回路是一種特殊的通路.圖中各邊全不同的回路稱為簡單回路,各點全不同的稱為基本回路.任一通路如果刪去所有回路，則必得基本回路;任一回路中刪去其中間的所有其余回路,必得基本回路. C1:(1,1) C2:(1,2,1) C2:(1,2,1) C4:(1,2,3,1) 均是基本回路. C5:(1,2,3,2,1) 是簡單回路但不是基本回路.第三十頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路定理8.2 一個有向(n,m)圖中任何基本通路長度均小于或等于n-1,而任何基本回路長度均小于或等于n.資源分配圖：是一個有向圖，表示時刻t時系統(tǒng)中資源分配狀態(tài).當(dāng)進程Pk占有資源Ri而又深情資源Rj時，則從結(jié)點Ri到Ri用一條有向邊相連.第三十一頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路例8.3R={R1,R2,R3,R4}P={P1,P2,P3,P4} 其資源分配狀況是： P1占有資源R4且申請資源R1; P2占有資源R1且申請資源R2及R3; P3占有資源R2且申請資源R3; P4占有資源R3且申請資源R1及R4.解： 其資源分配圖：第三十二頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路例8.4用有向圖刻畫過程間的調(diào)用關(guān)系，來判斷某過程是否是遞歸的. 一個過程集合P={P1,P2,P3,P4,P5} 調(diào)用關(guān)系： P1調(diào)用P2； P2調(diào)用P4； P3調(diào)用P1； P4調(diào)用P5； P5調(diào)用P2；某過程是遞歸的充分必要條件是包括此過程在內(nèi)的結(jié)點構(gòu)成一個回路.(P2,P4,P5,

P2)構(gòu)成一條回路,故過程P2,P4和P5是遞歸的第三十三頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路定義8.4從一有向圖的結(jié)點vi到另一vj如果存在一條通路,則稱從vi到vj是可達的.vi到vj是可達的不一定表示它們間只有一條通路,也可能有若干條通路,它們間最短的通路,這種通路稱為短程線,而短程線的長度則稱從vi到vj間的距離,可用d(vi,vj)表示.第三十四頁，共七十三頁，編輯于2023年，星期五8.2.1通路與回路在無向圖中一條邊lk對應(yīng)于無序結(jié)點對(vi,vj),而此無序結(jié)點對(vi,vj)可以看成兩個有序結(jié)點對(vi,vj)和(vj,vi).即可用方向相反的兩條有向邊取代一條無向邊,這樣,一個無向圖就轉(zhuǎn)換為有向圖了.第三十五頁，共七十三頁，編輯于2023年，星期五8.2.2連通性定義8.5 一個無向圖G,如果它的任何兩結(jié)點間均是可達的,則稱圖G為連通圖;否則,稱為非連通圖.定義8.6 一個有向圖,如果忽略其邊的方向后得到的無向圖是連通的,則稱此有向圖為連通圖;否則,稱為非連通圖.第三十六頁，共七十三頁，編輯于2023年，星期五8.2.2連通性定義8.7 一個有向連通圖G如果其任何兩結(jié)點間均是互相可達的,則稱圖G是強連通的; 如果其任何兩結(jié)點間至少存在一向是可達的,則稱圖G是單向連通的; 如果忽略邊的方向后其無向圖是連通的,則稱圖G是弱連通的.第三十七頁，共七十三頁，編輯于2023年，星期五8.2.2連通性無向圖中的連通性是一種等價關(guān)系其等價類是V的一個劃分第三十八頁，共七十三頁，編輯于2023年，星期五8.2.2連通性例：簡單圖G有n個結(jié)點,e條邊,設(shè)e>(n-1)(n-2)/2,證明G是連通的證明:(反證法) 假設(shè)G=<V,E>不連通,設(shè)G可分成兩個不相連通的連通分支(子圖)G1和G2,并設(shè)G1和G2分別有n1,n2個結(jié)點,顯然n1+n2=n.因為ni≥1,所以ni≤n-1(i=1,2). 與已知相矛盾,因此G是連通的.第三十九頁，共七十三頁，編輯于2023年，星期五例： (1)圖的次數(shù)序列為2,2,3,3,4,則邊數(shù)是多少？ 解:2m=2+2+3+3+4=14,m=7. (2)3,3,2,3;5,2,3,14能成為圖的次數(shù)序列嗎？為什么？ 解:不能.因為這兩個序列中有奇數(shù)個結(jié)點是次數(shù)奇數(shù). (3)圖G有12條邊,次數(shù)為3的結(jié)點有6個,其余結(jié)點次數(shù)均小于3,問圖中至少有幾個結(jié)點？ 解:次數(shù)為3的結(jié)點有6個占去18次數(shù)，還有6個次數(shù)由其余結(jié)點占有，其余結(jié)點的度數(shù)可為，當(dāng)均為2時所用結(jié)點數(shù)最少，所以應(yīng)由3個結(jié)點占有這6度，即圖中至少有9個結(jié)點。第四十頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖定義8.8 圖G的一個回路,若它通過G中的每條邊一次,這樣的回路稱為歐拉回路,具有這種回路的圖叫歐拉圖.定理8.3 無向連通圖G是歐拉圖的充分必要條件是G的每個結(jié)點均具有偶次數(shù),即無奇數(shù)次數(shù)的結(jié)點.第四十一頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖定義8.9

通過圖G中每條邊一次的通路(非回路)稱為歐拉通路.具有這種通路的圖叫歐拉半圖.定理8.4無向連通圖G中結(jié)點vi與vj間存在歐拉通路的充分必要條件是vi與vj的次數(shù)均為奇數(shù)而其他結(jié)點的次數(shù)為偶數(shù).第四十二頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例8.5圖中deg(v1)=deg(v3)=3,deg(v2)=deg(v4)=2,故v1和v3間存在一條歐拉通路,從圖中可以知道這條通路是 C:(v1,v2,v3,v1,v4,v3) 但是這個圖中不存在歐拉回路.第四十三頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例8.6郵遞員從郵局v1出發(fā)沿郵路投遞信件，其郵路圖如圖所示,試問是否存在一條投遞路線使郵遞員從郵局出發(fā)通過所有路線而不重復(fù)且最后回到郵局.第四十四頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖解：此問題就是驗證該圖是否為歐拉圖. 經(jīng)檢驗圖中每個結(jié)點均為偶次數(shù),由定理8.3可知這樣的一條投遞線路是存在的. 我們可以找出這樣一條線路： C:(v1,v5,v11,v7,v12,v8,v10,v6,v9,v11,v12,v10,v9,v5,v2,v6,v4,v8,v3,v7,v1) 該線路不是唯一的.例8.7灑水車從A點出發(fā)執(zhí)行灑水任務(wù),城市街道圖形如圖所示,試問是否存在一條灑水路線使灑水車從A點出發(fā)通過所有街道且不重復(fù)而最后回到車庫B.第四十五頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例8.8判斷圖中4個圖形是否可以一筆連續(xù)畫成而使圖中沒有一部分被重復(fù).圖(a)(c)(d)是歐拉通路,圖(b)是歐拉回路.第四十六頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例：構(gòu)造一個歐拉圖,其結(jié)點數(shù)v和邊數(shù)e分別滿足下述條件: 1)v,e的奇偶性一樣 2)v,e的奇偶性相反 如果不可能,說明原因. 解：構(gòu)造歐拉圖與v,e的奇偶性沒什么必然關(guān)系.第四十七頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例：設(shè)圖G是一個具有k個奇次結(jié)點的圖,問最少加幾條邊到G中,而使所得的圖有一條歐拉回路？解： 添加一條邊能使兩個結(jié)點的次數(shù)改變奇偶性 歐拉回路要使圖中所有的結(jié)點次數(shù)均是偶數(shù) 所以對于k個奇次結(jié)點,要將它們變?yōu)榕即谓Y(jié)點,至少添加k/2條邊才能使它們都變成偶數(shù).第四十八頁，共七十三頁，編輯于2023年，星期五8.3歐拉圖例:

下圖表示的是一個展覽館的平面圖。館里各相鄰房間之間都有門（共16扇）。一個參觀者來到展覽館門外，他想在參觀過程中，把館里所有的門都不重復(fù)地穿行一遍后出來，這個想法能否實現(xiàn)？解:首先建立該問題的圖論模型。將展覽館的5個房間和館外場地用6個結(jié)點表示，兩個端點之間的邊表示它們所在位置之間有一扇門(a)ABCDEF(b)BACDEF圖中有4個奇點圖中有4個奇點A,B,D,F,圖(b)不是歐拉圖,即參觀者的想法不能實現(xiàn)。

第四十九頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖愛爾蘭數(shù)學(xué)家漢密爾頓（WilliamHamilton）爵士1859年提出了一個“周游世界”的游戲。這個游戲把一個正十二面體的二十個頂點看成地球上的二十個城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過所有結(jié)點（即城市）一次且僅一次的回路.第五十頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖定義8.10

若圖G的一個回路通過G中的每個點一次,這樣的回路稱為漢密爾頓圖.定義8.11

通過圖G中每結(jié)點一次的通路(非回路)稱為漢密爾頓通路.定理8.5(必要條件)

設(shè)無向圖G=<V,E>是漢密爾頓圖,??V1?V,則P(G-V1)≤|V1|,其中P(G-V1)是從G中刪去V1(包括V1中相應(yīng)結(jié)點及其關(guān)聯(lián)的邊)后所得到的圖的連通分支數(shù).第五十一頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖漢密爾頓圖的必要條件可用來判定某些圖不是漢密爾頓圖。例:解：圖中共有9個結(jié)點,如果取結(jié)點集V1={3個白點}，即|V1|=3.而這時P(G-V1)=4.這說明該圖不是漢密爾頓圖。 但要注意若一個圖滿足該必要條件也不能保證這個圖一定是漢密爾頓圖,如圖c。o。o。o。(a)(b)(c)第五十二頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖定理8.6(充分條件) 設(shè)G=<V,E>為無向簡單圖,|V|≥3,如果G中每對結(jié)點次數(shù)之和≥|V|,則G必為漢密爾頓圖.滿足這個條件的圖一定是漢密爾頓圖。但不是所有的漢密爾頓圖都滿足這些條件.定理

(充分條件) 設(shè)G=<V,E>為無向簡單圖,|V|≥3,如果G中每對結(jié)點次數(shù)之和大于等于|V|-1,則G存在一條漢密爾頓通路.第五十三頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖例：考慮在七天內(nèi)安排七門課程的考試,使得同一位教師所任的兩門課程考試不排在連接的兩天中,試證明如果沒有教師擔(dān)任多于四門課程,則符合上述要求的考試安排總是可能的.解： 設(shè)G為具有七個結(jié)點的圖,每個結(jié)點對應(yīng)于一門課程考試,如果這兩個結(jié)點對應(yīng)的課程考試是由不同的老師擔(dān)任的,那么這兩個結(jié)點之間有一條邊. 因為每個教師所任課程數(shù)不超過四,故每個節(jié)點的次數(shù)至少是3,任兩個結(jié)點的次數(shù)之和至少是6,故G總是包含一條漢密爾頓通路,它對應(yīng)于一個七門考試課目的一個適當(dāng)?shù)陌才?第五十四頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖例：某次會議有20人參加,其中每人都至少有10個朋友,這20人圍一圓桌入席,要想使每個人相鄰的兩位都是朋友是否可能？根據(jù)是什么？解： 可用結(jié)點代表人,根據(jù)題意,兩人是朋友對,相應(yīng)結(jié)點間連一條邊,則得到一個無向圖G=<V,E>,可轉(zhuǎn)化為求漢密爾頓回路問題. 由于每人至少10個朋友,故對任意結(jié)點u,v∈V,有deg(u)≥10,deg(v)≥10 所以deg(u)+deg(v)≥20.根據(jù)漢密爾頓回路的充分條件定理,可知G為漢密爾頓圖,G中存在漢密爾頓回路,按此回路各點位置入席即為所求.第五十五頁，共七十三頁，編輯于2023年，星期五8.4漢密爾頓圖推銷員問題：設(shè)有某推銷員為推銷商品需要跑遍各大城市且不重復(fù),而最后返回原地,需要找到一條總距離為最短的路線.可以用結(jié)點表示城市,城市間的交通路線用邊表示,而城市間的交通線路距離可用附加于邊的權(quán)表示.而該問題的目的即找一條權(quán)的總和為最短的漢密爾頓回路.第五十六頁，共七十三頁，編輯于2023年，星期五8.5圖的矩陣表示法圖的矩陣表示法的優(yōu)點表示簡單,可以表示較為復(fù)雜的圖將圖的問題變成計算問題，方便借助計算機進行計算.第五十七頁，共七十三頁，編輯于2023年，星期五8.5.1有向圖的鄰接矩陣設(shè)有一有向圖G=<V,E>,其中 V={v1,v2,…,vn} E={e1,e2,…,em} 假設(shè)各結(jié)點按一定順序排列 這時構(gòu)成一矩陣: A=(aij)n×n

其中: 此矩陣稱為圖G的鄰接矩陣.第五十八頁，共七十三頁，編輯于2023年，星期五8.5.1有向圖的鄰接矩陣例：有圖如下，請寫出它的鄰接矩陣解：v1v2v3v4第五十九頁，共七十三頁，編輯于2023年，星期五8.5.1有向圖的鄰接矩陣設(shè)有圖G=<V,E>,其鄰接矩陣為可由鄰接矩陣很容易地辨認其對應(yīng)的圖的一些特性來.環(huán)：矩陣對角線元素有1零圖：矩陣元素全為0完全圖：除對角線元素為0外,其余全為1第六十頁，共七十三頁，編輯于2023年，星期五8.5.1有向圖的鄰接矩陣圖G中結(jié)點vi的引出次數(shù)結(jié)點vi的引入次數(shù)其全次數(shù)C=Al,此時cij表示從vi到vj長度為l的通路數(shù)目,如cij=0,則表示長度為l的通路沒有,而cii給出了從vi出發(fā)的長度為l的回路數(shù)目.第六十一頁，共七十三頁，編輯于2023年，星期五8.5.2可達性矩陣Rn=(rij)n×n Rn=A+A2+A3+…+An 若rij=0,表示從vi到vj是不可達的 若rij≠0,表示從vi到vj是可達的可達性矩陣(通路矩陣) P

=(pij)n×n rij=0時,令pij=0 rij≠0時,令pij=1一個圖G的可達性矩陣給出了圖中各結(jié)點間是否可達以及圖中是否有回路.第六十二頁，共七十三頁，編輯于2023年，星期五8.5.2可達性矩陣可達性矩陣的簡單算法P=A(+)A(2)(+)A(3)(+)…(+)A(n)

A(i)表示在布爾矩陣運算意義下A的i次冪 (+)表示在布爾矩陣運算意義下加法運算第六十三頁，共七十三頁，編輯于2023年，星期五8.5.3無向圖的矩陣表示法將無向圖中的無向邊用兩條方向相反的有向邊替代,使無向圖轉(zhuǎn)換為有向圖. 這樣,有向圖中的鄰接矩陣、可達性矩陣等均適用于無向圖.如：無向圖的鄰接矩陣都是對稱矩陣.第六十四頁，共七十三頁，編輯于