ch圖的基本概念

第10章圖的基本概念如何找到物流運輸?shù)淖顑?yōu)路徑？如何找到最優(yōu)的網(wǎng)絡通信線路？如果你想周游全國所有城市，如何設計旅游線路？化學化合物分析：結(jié)構(gòu)是否相同？程序結(jié)構(gòu)度量：程序是否結(jié)構(gòu)相似？如何為考試分配教室，使得資源利用率最優(yōu)？如何安排工作流程而達到最高效率？如何設計為眾多的電視臺頻道分配最優(yōu)方案？如何設計通信編碼以提高信息傳輸效率？操作系統(tǒng)中,如何調(diào)度進程而使得系統(tǒng)效率最優(yōu)？如何設計集成電路線路布局而達到最優(yōu)效率？如何設計計算機鼓輪？七枚同重量硬幣與一枚較輕的偽幣，使用天平秤多少次就能找出偽幣？如何設計下棋程序？n-皇后問題最少用幾種顏色就能將世界地圖都著色？如何使箱子盡可能裝滿物體？一個船夫要把一只狼，一只羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。那么他怎樣才能把三者都運過河呢？研究主題旅行商問題：TSP問題中國郵路問題地圖著色問題：四色定理最短路徑問題網(wǎng)絡流匹配組合計數(shù)主要內(nèi)容

1)圖的基本術語；2)結(jié)點的度，子圖，完全圖；3)圖的連通性；4)圖的運算，圖的矩陣表示及其性質(zhì)；5)圖的同構(gòu)；6)歐拉圖與哈密爾頓圖的性質(zhì)及其應用。

10.1圖論概述

圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學手段研究圖的性質(zhì)的理論，但這里的圖不是平面坐標系中的函數(shù)，而是由一些點和連接這些點的線組成的結(jié)構(gòu)。圖論是有許多應用的古老學科，也一直以來都是一個熱門學科，它已經(jīng)被廣泛應用于計算機科學、化學、運籌學、心理學等很多領域。10.2圖與圖模型例10.2時間安排問題。某大學計算機學院的某教研組共有10名教師，他們分別參加7個班級的討論課，每個班級可能同時需要多位教師參加，有的教師可能需要參加多個班級的討論，每個班級必須單獨開展討論課，則如何安排才使得所有班級在最短時間段內(nèi)完成討論課？參加各個班級討論課的教師情況如下（ci為班級編號，數(shù)字1-10為教師編號）：c1={1，2，3}，c2={1，3，4，5}，c3={2，5，6，7}，c4={2，6，7}，c5={4，7，8，9}，c6={8，9，10}，c7={1，3，9，10}。10.2圖與圖模型這樣，一位教師如果給多個班級都授課，則在討論課時間安排方面則不能沖突，如教師1不能同時參加班級c1與班級c2的討論課。這種情況可以用下圖直觀地表示。在上圖中，共用了7個小圓圈來表示班級，圓圈之間的線段表示存在同一個教師參加該二班級的討論課，這樣就不能安排該二班級同時開展討論課。顯然，這就給上述問題構(gòu)建了一個直觀的圖的模型。

c6c5c4c2c3c7c110.2圖與圖模型

定義10.1圖G包括一個非空的對象的集合V與有限的兩個對象構(gòu)成的V的無序?qū)?gòu)成的集合E，前者稱為的結(jié)點集，后者稱為邊集。令V={v1,v2,…,vn}是包含n個結(jié)點的集合，其m條邊的集合E={e1,e2,…,em}，其中，每一條邊都是集合V的二元子集，如邊ei={u，v}，常常簡記為uv或vu，其中u、v稱為邊uv的端點。這樣，一個圖事實上就是V與E構(gòu)成的序偶，常常被記作G=(V,E)。于是，也常常用V(G)和E(G)來表示某一個圖G的結(jié)點集與邊集。當然，也可以使用其它符號來表示圖，如用F或H，甚至G1等等。10.2圖與圖模型

集合V(G)的基數(shù)n表示圖G的階（Order），集合E(G)的基數(shù)m表示圖G的規(guī)模（Size），有時也將圖G記作(n,m)。在圖G中，若邊集E(G)=Ф,則稱G為零圖（NullGraph），此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖（Trivialgraph）。在圖的定義中規(guī)定結(jié)點集V為非空集，但在圖的運算中可能產(chǎn)生結(jié)點集為空集的運算結(jié)果，為此規(guī)定結(jié)點集為空集的圖為空圖（EmptyGraph），并將空圖記為。階為有限的圖稱為有限圖(FiniteGraph)，否則稱為無限圖(InfiniteGraph)。結(jié)點沒有標號的圖稱為非標號圖（UnlabeledGraph），否則為標號圖（LabeledGraph）。

10.2圖與圖模型如果圖中存在某兩條邊的端點都相同，則稱該圖為多重圖(Multigraph)，該兩條邊稱為平行邊。如果一條邊關聯(lián)的兩個結(jié)點是相同的結(jié)點，則稱該邊為圈或自環(huán)(Loop)。不存在平行邊與圈的圖即稱為簡單圖(SimpleGraph)。

10.2圖與圖模型

定義10.2如果uv是圖G的邊，記為e，即uvE(G),則稱結(jié)點u和v鄰接(Adjacent),否則稱結(jié)點u與v非鄰接。這里，也稱結(jié)點u或v與邊e是關聯(lián)（Incident）關系。與同一個結(jié)點關聯(lián)的兩條邊稱為鄰接邊。與結(jié)點v關聯(lián)的邊數(shù)稱為結(jié)點v的度，記作deg(v)。與結(jié)點v關聯(lián)的環(huán)對v的度數(shù)的貢獻要計算兩次。如果結(jié)點v的度為0，則稱之為孤立點(IsolatedVertex)。一度的結(jié)點稱為懸掛點（PendantVertex）。圖G的所有結(jié)點度數(shù)的最小度數(shù)稱為G的最小度，記作(G)，而所有結(jié)點度數(shù)的最大者稱為G的最大度，記作(G)。各結(jié)點的度均相同的圖稱為正則圖（RegularGraph）。各結(jié)點度均為k的正則圖稱為k-正則圖。

10.2圖與圖模型

定義10.3如果圖的每條邊是二結(jié)點構(gòu)成的有序?qū)Γ瑒t該圖稱為有向圖(DirectedGraph)，上文所定義的圖都是無向圖(UndirectedGraph)。有向圖中邊uv與vu是兩條不同的邊，對于邊uv，稱u為始點，v為終點。

有向圖中，結(jié)點v的度分為入度，即與該結(jié)點相關聯(lián)并以該結(jié)點為終點的邊的數(shù)目，以及出度,即與該結(jié)點相關聯(lián)并以該結(jié)點為始點的邊的數(shù)目,分別記作deg+(v)，deg-(v)。

10.2圖與圖模型v1v2e1e2v1v2e1e2無向圖有向圖10.2圖與圖模型環(huán)loop-->(偽圖:非簡單圖simplegraph)邊e2(有向邊<v1,v2>directededge有向圖)關聯(lián)incident結(jié)點v1、v2結(jié)點vertex/vertices(頂點)平行邊/重邊multiedge多重圖multigraph多重圖且偽圖擬圖(pseudograph)孤立點(isolatedvertex)懸掛邊(pendantedge)懸掛點(pendantvertex)分離邊v3結(jié)點度degree為3,與3結(jié)點鄰接adjacent,2出度1入度v3v1v2e1e210睡.2圖與分圖模議型練習1設G=液(V館,E度)是一平無向準圖，V=麗{v1,v2,…槽,現(xiàn)v8}，E=亂{(窩v1,v2),鞭(v2,v3),祝(v3,v1),乒(v1,v5),蠢(v5,v4),縣(芝v4,v3),謠(v7,v8)}（1）畫葛出G的圖結(jié)解；（2）指旗出與V3鄰接侄的結(jié)稈點，雷以及系和V3關聯(lián)仰的邊扔；（3）指質(zhì)出與(v2,v3)鄰接拋的邊除和與(v2,v3)關聯(lián)缸的結(jié)浪點；（4）該闊圖是捷否有壇孤立驗結(jié)點航和孤迷立邊嗽？（5）求亞出各廢結(jié)點熊的度巨數(shù)，潤并判眠斷是堆否是旺完全抖圖和嫩正則傭圖？（6）該(n,掛m)圖中秒，n=？，m=？10抬.2圖與永圖模陜型圖的粗邊數(shù)磨與結(jié)肆點數(shù)傳的關咱系是槍圖最聽為重遲要的成屬性鴨，結(jié)凈點的灶度數(shù)奇滿足掛一個幕非常辜簡單襲的關區(qū)系，便即圖盯的每拐條邊庫都關縱聯(lián)于闊兩個秤結(jié)點躍，則睬每條蠶邊對似圖結(jié)俱點度窩數(shù)之抱和的串貢獻階為2，從扭而有潮下面慚的定務理：定理10鉆.1（歐艙拉定石理）在任奧何圖宵中，眨結(jié)點朵度的萄總和違等于須邊數(shù)帽的兩尊倍。該定次理也駕被稱便為握手愧定理，被辛認為木圖論膏第一研定理妨，可款以用司于證批明圖叫的相煙關性剛質(zhì)。推論10腔.1在任弄意圖五中，扎奇數(shù)億度的恒結(jié)點期個數(shù)米為偶微數(shù)。10早.2圖與河圖模懸型例10吐.3設G=蹲<V落;班E>，|V樓|=撇n,絕|盒E|腳=m，證頃明：(G為)≤直2m摩/n巧≤(G吳)。證明由歐汪拉定默理，de外g(沙v)=2般m。對任隱意的vV，有(G)票≤d晃eg伸(v亭)≤(G)，于是n(G仔)≤d塑eg走(v況)≤n(G)n(G尸)≤期2m捐≤n(G漆)即(G孫)≤仇2m夠/n走≤(G院)。10驚.2圖與貼圖模壩型例10茂.4請證忍明：視有向屋圖中丸，所叢有結(jié)煙點出抬度之渡和等富于所爆有結(jié)鞏點入斬度之桐和。證明在有戒向圖尊中，面任意兩一條魄邊都采有一辣個始博點和別一個施終點籍，因揚而結(jié)倆論成讀立。10嬌.2圖與相圖模庭型練習2設G=趟(V歲,E差)有12條邊例，有6個度邊為3的結(jié)析點，曠其余閥結(jié)點虛的度住數(shù)均按小于3，問G中至彎少有演多少裁個結(jié)渾點？10狹.2圖與鈔圖模債型例10痕.5十字攤路口丹交通稈管理燒問題資。下往圖(a厲)是某尋繁忙凍的城睜市十鄰字路投口交屯通管汁理示僅意圖臉，其欣中c1c9表示釣可能疾的行躍車路她線，灘為安母全考提慮，屠顯然c1、c5可以送同時半進入根十字直路口夾，但c1與c8卻不西能同馳時進筋入十亂字路攜口，糕等等東。本譜問題米可以海用圖斃來建秒模，舅如下鴨圖（b）所示貢。其瞇中，乘結(jié)點通集為昏所有裹行車壯路線該的構(gòu)饑成的塊集合車，結(jié)絞點之業(yè)間的訴邊表野示相住應的脂二行塊車道持不能仍同時舅開通櫻。顯金然此核圖可芹以用呼于十碧字路視口交互通信晝號燈憐的設宗計。c4c5c1

c2c3c8c7c6c3c4c9c1c5c2c7

c6c9c8(a麻)(b栗)10糊.2圖與暫圖模夾型例10扭.6旅行印售貨鴿員問富題。候現(xiàn)有瞇一個欺筆記征本計墳算機符代理亮商要當從其片所在落的城須市北慶京出字發(fā)，穗乘飛仔機去5個城孫市，勺然后暖回到任出發(fā)洗點。弄如右宰圖所肚示。胃圖中奸結(jié)點寫代表穩(wěn)城市蛾，邊喊代表漠城市畝間的銳直達印航線濫。他治怎樣雜才能躁出差替到每劑個城崗市恰寫巧一滑次，繡最后削回到驚北京瀉呢？?？诔啥急本┪錆h廣州上海這個埋問題著的解卻答本偏身比呈較簡頭單，往如可銀以選片擇線別路為也北京-成都-武漢-?？?廣州-上海-北京噴。但閥對于舊更為領復雜仍的情剩況就末很難潮直接炒找到祖好的盞解答壟。本曉問題藏與后拜文將冬研究向的Ha死m(xù)i葵lt極on圖有凳關，灣將在倒那里遭做詳殼細討劫論。10噸.2圖與掃圖模確型例10駕.7優(yōu)先未圖。香通過甚并發(fā)虎地執(zhí)狗行某么些語筆句，攪計算殖機程探序可桶以執(zhí)湯行得工更快幼。如西何確吼定哪擱些語蓋句可赴以并濾發(fā)執(zhí)它行是戶非常巨重要岸的，黃這需迫要分收析清植楚程魯序中豬語句損之間竭的優(yōu)誕先關棋系。襪這種陵優(yōu)先誤關系謙可以借用有駐向圖菠來表肥示。順如用沾結(jié)點貓表示冰語句辛，若涂在執(zhí)秒行完悉第一咱個結(jié)勞點表政示的占語句朗之前川不能厘執(zhí)行禾第二宵個結(jié)尸點表篩示的道語句增所表以示的邊語句續(xù)，則趁在第投一個茶結(jié)點查到第晨二個僚結(jié)點掃之間億添加形一條第邊。絨最后息得到胳的圖餅稱為句優(yōu)先竊圖。下圖就爛是一紅個優(yōu)櫻先圖鼻的例核子。愚該圖園表明眼在執(zhí)游行語兇句S1、S2與S4之前臂不能睬執(zhí)行擦語句S5。S1a=0S2b=1S3c=a+1S4d=b+aS5e=d+1S6e=c+dS4S5S6S3S2S110胞.2圖與解圖模岔型練習3在晚會煩上有n個人餡，他蓮們各蟲自與尋自己助相識績的人碼握一灘次手射。已刷知每書人與揭別人骨握手特的次胃數(shù)都柿是奇捆數(shù)，基問n是奇掩數(shù)還酬是偶求數(shù)。虧為什峽么？解n是偶炸數(shù)。寧用n個頂憂點表傭示n個人為，頂莊點間貼的一懶條邊巷表示灰一次謠握手膜，可病構(gòu)成抗一怨個無跳向圖代。若n是奇趣數(shù)，缸那么睛該圖皮的頂府點度呼數(shù)之射和為訊奇數(shù)準個奇裕數(shù)的征和,即為泳奇數(shù)井，與加圖性瞧質(zhì)矛授盾，賄因此繭，n是偶軋數(shù)。10飄.2圖與慈圖模淋型與集贏合論舒中研席究子摧集，小抽象粗代數(shù)糊中研揀究子疾代數(shù)正類似肥，圖犬論中娛也研生究一小個圖易的子犁圖。界一個麥圖G的子撞圖G′可以賣通過城選取G中的由部分話結(jié)點伴與邊揉構(gòu)成球，但銜要求盤如果王選擇莫了G中的魔邊，石則必奴須選掛擇與東該邊沙向關祥聯(lián)的緊結(jié)點約。這殊樣就捉保證帽了G′能夠夫構(gòu)成勝一個須圖。10農(nóng).2圖與納圖模楊型定義10粉.4令圖G=（V，E），列稱(V稱′,常E′倉)為G的子陶圖（Su漿bg脾ra貢ph），狡當(1盡)VV且EE；(2桑)對任宅意eE，則票與e相關繼聯(lián)的圓結(jié)點u,vV。若G是G的子稱圖,則稱G是G的超圖，記寒作GG。若GG且G≠G炎(即VV或EE)，則青稱G是G的真子耗圖。若GG且VV，則抓稱G是G的生成尊子圖（Sp咱an堤ni梯ngSu對bg殖ra針ph）?？裨OV1V,且V1≠，以V1為結(jié)摩點集佩，以祥兩端賴點均蜘在V1中的辮全體耐邊為俘邊集領的G的子拆圖，哀稱為結(jié)點枯集V1導出輔的導網(wǎng)出子說圖（De門ri差ve誤dSu笛bg摘ra若ph）。萬設E1E,且E1≠，以E1為邊悲集，必以E1中邊冊關聯(lián)描的結(jié)叔點的瓦全體常為結(jié)摸點集G的子刊圖，凝稱為邊集E1導出代的導森出子泳圖。10矛.2圖與伙圖模輔型顯然誦，子右圖或爽導出征子圖追可以括通過凱刪除拜一些除結(jié)點粘或一而些邊準得到動。例10沒.9下圖所悟示的銀圖中徐，G1是G的由臺結(jié)點男導出適的導口出子名圖，G2為G的由魄邊集枝導出盈的導粘出子喇圖。10撒.2圖與歡圖模陽型定義10孝.5設G海=<爭V,適E>是n階圖,若G中任莊何結(jié)矩點都亦與其駕余的n1個結(jié)瘦點相侵鄰，萌則稱G為n階完喂全圖(C胳om托pl轉(zhuǎn)et瀉e窯Gr造ap府h)。記榨作Kn。設D=尸<V停,E杰>為n階有挽向圖,若對蚊于任詞意的斤結(jié)點,u,鏡vV(u≠壩v)押,既有霸有向毅邊<u,肯v>,又有<v,葬u>，則潛稱D為有向喂完全栗圖。容易基得到再如下玻重要遷結(jié)論污：Kn的邊竊數(shù)|E(茫Kn)|饅=n隱(n對-1測)/章2，且對咱于一草般的n個結(jié)速點的創(chuàng)圖G其邊臨數(shù)|E咱(G答)|≤n(柄n-盛1)臺/2。10讓.2圖與葵圖模搶型下圖中抬圖(a宴)為四求個結(jié)予點的老完全安圖，(b膏)不是當完全勁圖，(c障)是有風向完辭全圖刮。(a爪)(b惠)(c扎)10撒.2圖與隸圖模藍型定義10掛.6若圖G的結(jié)屬點可款以分牌為兩謀個非經(jīng)空集有合V1，V2，G中的專邊的磨端點匪分別偉屬于V1，V2，則妄稱G為二分暗圖（Bi匹pa厭rt債it此e夜Gr謎ap旅h），端可簡毛記為G(霧V1，V2)。若V1中結(jié)原點與V2中結(jié)漠點均快鄰接女且V2中結(jié)朵點與V1中結(jié)過點也按均鄰賠接，脊則稱G為完全匠二分尖圖（Co厚mp炸le故te勇B萍ip擋ar末ti以te別G要ra渴ph），脹記為Km,元n，m,盾n分別搭是V1，V2的基匙數(shù)。二分臺圖常緊常被滲應用貸于工孕作分羅配問透題中臉，通捕過對枕二分縫圖的形分析協(xié)，找線出滿可足最英多條禿件的鐘工作袍分配易方案罷。完抄全二嶼分圖K1，n常常奧被用斑來對玩計算含機網(wǎng)凳絡建竿模，豬度為n的結(jié)袋點代執(zhí)表網(wǎng)蜜絡服喚務器煉，其裂余結(jié)歲點代骨表網(wǎng)事絡中躺的n個計渠算機候。10旋.2圖與娛圖模柳型例10尖.1肚0下圖泛所示葬的圖(a援)是二猴分圖,圖（b）是延其的般另一奶種表恩示。v1v6v2v3v5v1v3v2v4v6v4v510劈燕.3路徑命與圖以連通月性圖論北中的秀許多羽概念回和應租用都揭與對怪圖的題遍歷或有關絞，即校是從冷一個稿結(jié)點u出發(fā)潛，到戚達與廊之相戴鄰接顏的結(jié)穴點，略在從延該鄰陵接結(jié)陣點出般發(fā)到撒達其如鄰接隙的結(jié)廊點，江依次具類推兵，最唯后可拿以到墳達圖那中的立某結(jié)臭點v，從而辰就得狠到一澇條從u到v的通傷路。從u到v的通何路W可用襖如下迫的結(jié)濱點的城序列嘉來表等示：W:蛋u燥=v0,v1,v2,…惠,vk=v護，k0。通路W常表術示為u-檔v通路辣。這愈些結(jié)透點序控列中禽任意階相鄰教的結(jié)斥點在差圖中奸是鄰獄接的清關系虎，稱澆結(jié)點vi（i=蒼0，1,委…,優(yōu)k）以及隊邊(vi,vi+難1)主(i江=0沈,1侍,…偶,k魚-1鑼)為通千路W上的結(jié)點與邊。10推.3路徑冶與圖害連通陶性如果襲通路價上首蒼尾結(jié)矮點相悅同，凍則稱囑該通冶路是閉的(C嫁lo則se棉d)，否財則稱毛該通澇路是開的(O賺pe迫ne破d)。如賞果通傍路上步?jīng)]有脈相同爺?shù)倪吇?，則峽稱該鄉(xiāng)豐通路丙為跡(T罵ra末il燦)，如見果跡復上的份開始盈結(jié)點奮與結(jié)葉束結(jié)酸點相伸同，食則稱溜之為回路(C須ir怪cu考it槍)，如煉果回賢路上還除了霉開始掏結(jié)點尋與結(jié)性束結(jié)叢點沒燦有相回同的透結(jié)點唐，則檔稱之撓為環(huán)(C拳yc命le創(chuàng))。如凍果通壤路上直沒有善相同旨的結(jié)賣點，壓則稱病該通洞路為路或路徑(P什at辣h)，有n個結(jié)桿點的概路常袖記作Pn。10封.3路徑港與圖捎連通釘性通路耍遍歷鴿過的滾邊的枝數(shù)目鼓為通位路的槳長度賭，如綿果通畝路長乳度為0，則娃稱之砍為平凡塔通路（Tr泄iv宋ia坦l羞Wa殊lk）。叔兩結(jié)垂點u，v間的盟路可齒能不究只一犁條，滲將其渡中的吊最短額的路迅稱為u，v間的距離。如果地一條庭通路W上有k+往1個結(jié)族點，險即W:唱u策=v0,v1,v2,…養(yǎng),vk=v，k≥0。則岸由于W上的陽邊是蜘由W上相各鄰結(jié)鑄點(vi,vi+罰1)蒼(i紫=0羞,1臣,…交,k壓-1滑)構(gòu)成攜，因胞此W上有k條邊承，即W的長尸度為k。如遼果一益條環(huán)C上有k+暮1個結(jié)蘋點，科即C:蘇v0,v1,v2,…臟,vkv0，k≥0.則由經(jīng)于C上的賀邊是黃由C上相工鄰結(jié)傾點(vi,vi+敵1)(匹i=嬸0,睡1,煮…,芬k-佳1)以及怠（vk,v0）構(gòu)鼠成，黨因此C上有k+挨1條邊陵，即C的長義度為k+歡1。10之.3路徑巧與圖敲連通敢性定理10欠.2如果含圖G上存稠在一寺條u-嘩v通路濟，則截必然癥存在似一條u-朱v路；楊如果G上存芒在一醬條閉燃通路爬，則片必然滿存在慚一條伸回路(環(huán))。這是推因為隙，如供果通調(diào)路上騙存在鴉相同窗的結(jié)竿點vi,vj，則剪可將vi,vj之間含的一戶段通點路刪襯除，勿并合應并vi，vj為一津個結(jié)譯點，宿從而室得到柔一條蘿更短雅的u-僅v通路約。如崗果所跳得到義的u-寇v通路銹上還機存在迫相同塌的結(jié)蘭點，區(qū)則可眠以依翻此繼互續(xù)執(zhí)像行刪糊除操偽作，嘗最終朽一定鋼可以覺得到長一條磨沒有字相同電結(jié)點站的u-折v通路教，也拋就是月一條u-森v路。去類似崇地，拴如果G上存丑在一沫條閉尤通路烤，則澡必然孤存在我一條吉回路警（環(huán)厲）。10飼.3路徑柱與圖勢連通繪性例10腿.1倘1在右戴圖中棕，1)找出何一條棒包含素圖所慚有結(jié)惰點的塞通道凱；2)找出殲一條法包含孟圖所臨有結(jié)疫點的鍛跡；3)找出半所有a-哭d路，角并求忌出其算長度奏；4)找出項圖中艦所有碗的環(huán)潛。解1)包含訓圖所將有結(jié)融點的楚不是陸跡的素通道棄：ae裳bc裕ae滿bd。2)包含爪所有典結(jié)點盞的跡曬：be識ac貌bd。3)武a拒-d路：ae許bd寧,a甜cb滾d,長度揚均為3。4)環(huán)：ac甘be要a，長退度為4。abedc10呀.3路徑規(guī)與圖辟連通山性例10律.1稍2每個燃結(jié)點景的度繞數(shù)至房誠少為2的圖匆必包撐含一么個回竄路。證明設P是圖G中最雹長路奔經(jīng)中傳的一民條，盲并設朵其長之度為m,療P的一聞個端邀點為u?？际夭霨中與u關聯(lián)截的邊況，由劉于G中每娘個結(jié)旨點的者度至鈴少為2，故u必關呢聯(lián)一同條不蠶在P上的杯邊e，從蹦而e的另膽一個妄端點v必然渡在P上，麥否則騎，將越這個極結(jié)點乳加入P上，癢則可冊以得慚到更址長的守路。引于是麗，P上u到v的的詢路與葉邊e構(gòu)成移回路宣。uvP10違.3路徑烤與圖分連通蒸性Di斤jk誘st疊ra最短輛路徑滔算法輸入母：一彼個帶姐權圖G，G的任穿意兩陰個結(jié)線點間陷有路彈徑存鳥在，G中任窗意邊(v,插x)的權映值w(枕v,袍x)>遣0；結(jié)葉點a與z輸出我：L(卵z)，從質(zhì)結(jié)點a到z的最倍短路堤徑長困度1婆Pr亞oc秋ed朱ur紅eDi脈jk孤st丘ra肯(G)2載F甚or所有制結(jié)點x≠暫a3L(腦x)=奔∞;L(帥x)表示a到x的最祖短路急徑長登度4異En橫d撥fo產(chǎn)r;5L(將a)=番0;6探T=罩V(尋G)掌;7咸S=;10菜.3路徑噸與圖黎連通凱性8Wh爆il黨e(馬z∈鹿T)9從T中找爹出具腦有最淺小L(聲v)的結(jié)漁點v;10屢F鳥or所有影與v相鄰兩的結(jié)帝點x∈豈T11L(皆x)=mi采n{煎L(銷x)考,L止(v起)+洞w(膽v,淚x)}12匠En澇d襯Fo漢r13柿T豈=T雷-{信v}裳;14玻S=S∪超{v};15致En就d士Wh疲il肢e16嘴E抹nd預P驕ro均ce綢du章re10磚.3路徑五與圖韻連通遭性例10碑.1產(chǎn)3下圖續(xù)所示河的帶著權圖蚊中，戚根據(jù)挺上述促算法旦可以儀得到貌結(jié)點a到z的最腐短路殲徑為聯(lián)圖中吧加粗威的邊光所示辮，長和度為13。456182az210310杠.3路徑怪與圖婆連通斃性定義10謊.5如果安圖G中結(jié)珍點u到v有一蒸條路鄰徑，效則稱糕結(jié)點u到v是可達嚴的（Ac械ce歪si漸bl須e）或連通垂的（Co叔nn朗ec榴te且d）。代結(jié)點u到其粉自身才也定禮義為吸連通摧的。定義10煤.6如果搶圖G的任倍何兩疊個結(jié)令點都僻是相煩互可皺達的鑄，稱G是連通嗎的（Co仰nn塵ec穗te薄d）,并稱G為連通刺圖(C滔on魂ne得ct瓜ed您G武ra洪ph傳)。對原于有饒向圖G，如痕果G的任零何兩航個結(jié)泰點都在是相跡互可品達的暗，則苗稱有駁向圖G是強連知通的；忽如果G的任查何兩六個結(jié)閑點中比，至拳少從找一個勒結(jié)點皺到另策一個餡結(jié)點準是可喚達的蘭，稱簽有向鬧圖G是單向堂連通的；藏如果G的有搬向邊肆被看袖作無住向邊搭時是庭連通嚇的，朗稱有咳向圖G是弱連條通的。10膛.3路徑純與圖訪連通夏性容易汪判斷麥，強筍連通徐圖必底定是飽單向伯連通況圖，炕單向暗連通海圖必框定是熔弱連膽通圖淘。例10旨.1港4下圖芳中，(a太)為連稼通圖任，(b恢)為由膛兩個雨連通賺分支嘴的非懲連通營圖，c為強罰連通怨圖，d為單偽向連旺通圖聲，e為弱折連通斑圖。a爽b閱c普d赴e10徑.3路徑揭與圖捐連通艇性練習4已知每關于a,拒b,求c,政d,肚e,脊f,犯g的下桐述事條實：a說英晶語；b說英檔語和瘦西班碧牙語房誠；c說英奇語、誼意大貸利語茂和俄迫語；d說日搶語和旱西班寫牙語畏；e說德箏語和紹意大潤利語冬；f說法蛙語、傅日語離和俄頁語；g說法耽語和員德語伐；試問漲：上鋤述7人中腐是否兇任意脅兩人異都能爬交談搭（如憐果必肺要，標可由挪其余5人中險所組崇成的慮譯員況鏈幫咽忙？斧）10請.3路徑續(xù)與圖昏連通副性若將喘圖中瘦兩個芳結(jié)點懸間的戒連通考性看洞作圖曲的結(jié)答點間亞的一攻種關療系，傻容易筍判定貓圖中燒兩個罷結(jié)點閃間的勇連通扯性是凝一個等價非關系，因索為結(jié)搞點u到u是連數(shù)通的島滿足浪自反截性；值若u到v是連惑通的魂，則v到u也是韻連通寄的，病滿足政對稱簽性；貞若u到v連通虎，v到w連通丸，則u到w存在友一條夏通路神，從紛而存新在一毫條u到w的路起徑，融故u到w是連淋通的片，滿攀足傳叉遞性寫。但綱對于碗有向滋圖，遵結(jié)點奏間的荷連通快性不市滿足荷對稱笑性，渠是偏序焰關系。10渣.3路徑擺與圖疫連通及性現(xiàn)在抬可以裝利用駐結(jié)點摘的連刮通性桃對圖G的結(jié)搞點集與進行蠶劃分吧，于證是利團用這克個劃珍分可竿以得漂到G的多第個連碧通子華圖，魚如G[租v]=銜(V[賭v]臘,E證[v])鐘,是結(jié)仁點v所在棉的一迅個連湊通子幕圖，珠其中攀，V[墾v]=唉{x|運x到v可達}，E[總v]為V[沃v]中結(jié)辮點在G中相地應的壞邊之期集合言。G[頑v]具有舉一個錘特點體，即理不存泛在一養(yǎng)個G的真勇子圖G′艙,G[蜓v]為G′的真羨子圖,且G′也是G的連羞通子督圖。燃稱G[廉v]為G的連通鴉分支或連通害分圖（Co妙nn肅ec寨te掉d悼Co替mp炸on析en減t）,也稱蠶為極大旱連通雪子圖。10超.3路徑岔與圖艦連通捐性例10靠.1波5如果紀圖G恰有永兩個稱不同威的奇寨數(shù)度狂的結(jié)臨點u，v，那嗚么u到v必定悶是可丸達的瞇。證明如果u到v不可僵達，拼那么G不是跟連通旁的，u與v必分春屬于場兩個庭連通矛分支G1，G2，而G1，G2是G的子除圖，裁且都庸恰有凈一個文奇數(shù)鵝度結(jié)軌點。銅與推漿論10塵.1矛盾扇。因總而u到v是可饒達的意。10鄰.3路徑陶與圖譜連通擁性定理10峽.3設G是一(n，m)圖，G有ω個分案圖，末則n-革ω≤直m≤油(n誤-ω針)(考n-木ω+柜1)狠/210會.3路徑凳與圖包連通赴性練習5在任雅何n規(guī)(n員≥2零)個頂專點的揉簡單登圖G中，罪至少耗有兩議個頂纖點具幟有相笛同的婚度。證明如果G有兩至個或捷更多留孤立穩(wěn)頂點膽，那逮么它礦們便極是具麗有相淋同的撇度的縣兩個散頂點新。軌如果G恰有孩一個掠孤立聰頂點謀，那桐么我脊們可冒對有n–熟1個頂沖點但雞沒有風孤立變頂點苗的G’（它孤由G刪除宅孤立觸頂點磚后得全到）胸作討輸論；渾如果G有分昆圖，想則也?？梢云拗苯蛹膶Ψ峙麍D進東行討遼論。弱因此亡，不微妨設G沒有頌孤立纖頂點稍，那款么G的n個頂呢點的慢度數(shù)首應是匠：1，2，3，…，n–汗1這n–峽1種可每能之鍵一，教顯然圾，必孔定有借兩個屋頂點輛具有昂相同周的度鬼。10縣.3路徑枝與圖引連通丟性練習6給定勢簡單重圖G=妄<V齡,E或>，且|V捉|=脈n，|E白|＞(n扶-1文)(況n-費2)殺/2，試壇證G是連訪通圖嗽。試共給出|V惱|=援n，|E怪|=稈(n舌-1脂)(線n-栽2)遣/2的簡盲單無墨向圖G=葉<V符,E勒>是不判連通體的例承子。10水.3路徑排與圖訴連通趟性定義10襲.9設S為圖G的結(jié)頁點集V的子畫集，及稱S為G的點割晌集（Cu勾t椒Se布t岔of鑰V此er潛te熔x）,如果訂從G中刪傷除S中的語所有驢結(jié)點山后G的連爭通分熱支數(shù)債增加徑，但S的任辭何真送子集挺均無朋這一緣瑞特性鴨。當捉點割笨集為揪單元宅素集得合{v烘}時，v稱為割點（Cu紐奉t攀Ve蠅rt奮ex）。設S為連錦通圖G邊集E的子親集，利稱S為G的邊割瘋集（Cu柜t抓se丙t穩(wěn)of條E較dg虧e），才如果歲從G中刪暴除S的所究有邊沸后G的連萍通分枝支數(shù)規(guī)增加綁，但S的任披何真遷子集肆均無眾這一陵特性浩。當朋割集陽為單件元素嶺集{e鉆}時，蠻稱e為橋(B雨ri忌dg跳e)或割邊（Cu六t濕Ed乖ge）。10壓.3路徑珍與圖鐮連通短性例10襯.1績7下圖中來的圖是有點疼割集{1，5}，2，3是割史點，惠而{4，7}不是奸點割隊集。{e1,e3},敢{e4,e5},草{e6,e8}等均滋是邊戴割集咸，e9是割慨邊。126735e1e3e2e4e7e8e64e9e510吧.3路徑絡與圖捧連通敗性例10抗.1藝8試證悟明：愧圖G的任狠一邊覆，若諷其不讓是割趁邊，攻則必布出現(xiàn)溉于G的某漫一環(huán)惹里。證明設圖G的邊e=委(vi，vj)不是異分割企邊，饅去掉e后，鄰與vi相連腿接的厚接點所集為V1，與vj相連避接的蓮結(jié)點件集為V2，由紅割邊圖定義妖知，V1∩V2≠。因甩而存援在一廉結(jié)點v∈妥V1∩V2，使不得在興去掉e后，vi與v有路俘相連萄，v與vj有路翻相連割。于考是vi與vj有路扔相連唱接，魔因而樣必存痰在一淺條連粉接vi與vj的路P=勝vi，v1，v2，…，v，…，vj，從膚而P與邊(vi，vj)組成飾一個軍環(huán)。10裁.3路徑業(yè)與圖捧連通港性定義10編.1瓜0圖G的點連久通度（Ve活rt閉ex賓C疼on母ne身ct越iv屋it僅y）是乎指把G變成權非連仆通圖成或平盯凡圖哈至少遞要刪分除的答結(jié)點哀數(shù)，是記作(G妄)舞(讀作咱卡帕)。定盼義中缸的平魯凡圖杯主要宋針對G為完挺全圖趟時而會言的腦，因拼為完額全圖朱無論首刪除泳多少絲式結(jié)點飲都不懶會變祝得不畝連通高。根萌據(jù)定幻玉義，(G紗)可以辱具體唐定義勤如下御：(G信)=10鏟.3路徑隸與圖沫連通旗性類似房誠地，甘有邊辱連通務度的找定義鴉。G的邊連狂通度（Ed廢ge圾C絞on無ne恥ct臥iv情it漆y）是尺指把G變成心非連絮通圖段或平慰凡圖捏至少避要刪面除的爆邊數(shù)色，記耗作λ(揭G)。根真據(jù)定崗義，閣當G為非忍連通括圖或慕為K1時λ(礎G)=息0。例10賓.1胡7中圖底的點拖連通況度為1，邊裁連通脾度為1。顯然滅，點概（邊滴）連減通度樓越小自，圖脹的連折通性坦越脆仍弱。10才.3路徑棚與圖兩連通躬性令δ(匙G)表示監(jiān)圖G中結(jié)伴點度酸數(shù)的晝最小況值（口常稱穴圖G的最小戶度），村那么近我們鴿有以申下定港理。定理10貝.4對于傅圖G，有歪下面爛不等己式成稍立：(G)剪≤λ任(G鄙)≤雹δ(猾G)從直喪觀上熟看，激圖的奴連通覺度應答當與壯圖中稠任兩鼠點之宵間的鋤路的快條數(shù)作有關先。連輔通度圓越高畏，連邁接兩棗點的際路應性當越躲多。10司.3路徑忍與圖喂連通帳性定義10咸.1膨1設G=乳(V，E)是連抬通圖畝，SV，u，v∈浪V。若傳在G-哀S中u，v不可汁達，帝則稱S分離u，v。設FE，若屠在G-壩F中u，v不可秀達，精則稱F分離u，v。定理10蝕.5在一兼?zhèn)€連胖通(p，q)圖中騾，分趣離兩護個不攤相鄰拐接的昏點u，v的點怠集中蜓，點唱的最岸少數(shù)嫂目等送于連知接u，v的不帽相交列的路駁的最泡多數(shù)推。10堡.3路徑伴與圖汪連通甜性證明設G=倡(p，q)，u，v是G中任絡二不叫相鄰挖的結(jié)僚點，點且分失離u，v的點著集至說少有k個點叔，連金接u，v的不塘相交純的路(點不襪相重)共有m條。1)因為矛連接u，v的不振相交藍的路縱共有m條，飄這m條路純除端肺點外須無公鄙共點冷，所燦以要非分離u，v，至誰少要用從每半一條損路上缺去掉霞一個挽點，紡即m≤總k。2)若分脆離u，v的點進集中昆至少筆要k個點他，而摘連接u，v的路偏共有m條，橡則只鐘要在及這m條互錢不相糕交的銀路上左各取貼一點弄，即炮可組諸成一落個由m個點班組成認的點蠻集S，S分離u，v。所菠以k≤私m。由(1糊)、(2穿)結(jié)論控可得k=裹m。證灶畢。10斥.3路徑詠與圖捷連通筒性定理10悶.6若u，v是圖G中兩炒個不蓮同的蝴點，G中連烈接u，v的邊園不相濾交的稼路的卷最多慌數(shù)目葬，等猶于分呆離u，v的邊失集中醬邊的含最少呀數(shù)目籮。以上諒兩個歌定理抱屬于Me緞ng禁er定理尖的圖禾論形若式。Me爽ng功er定理學具有嘴普遍昏意義巴，它輝的圖敞論形張式還租有多筐種。判并且悄，在鍬其它各領域霜中，射類似真的定栗理也帶被一銳再發(fā)少現(xiàn)。往例如承，網(wǎng)撿絡最朗優(yōu)化板理論晴中有植名的財最大要流最索小割信定理西、集他族理晨論中虧的霍兆爾定票理、狂格論叮中關燭于有參限格手中不滅可比顛元素埋的數(shù)嘩目等類于包叮含所螺有元躺素的稈鏈集持中鏈壩的最圍少數(shù)似的定臂理，放等等鴿。這得些定籍理從凡不同欠領域先中發(fā)芹現(xiàn)，森相互總之間湖有著覽內(nèi)在鞠聯(lián)系標，它鍵們都揀是Me英ng較er定理強的變創(chuàng)形。10圈.4圖的宴運算1基本鄉(xiāng)豐運算刪除壟運算從圖G中刪綁除一失邊e所得億到的運子圖驚，記乓為G-新e。從圖G中刪漲除一徒個結(jié)僻點v及其攤關聯(lián)驕的邊筍所得尋到的驢子圖驢，記旗為G-獎v。類似貞地，G-扇E′表示劈燕從G中刪匪除邊墾集E的子盈集E′所得武到的啞子圖就，記瀉為G-棗E′搞=(魄V，E-甲E′暖)。G-攝V′表示蠟從G中刪辜除結(jié)遙點集V的子寒集V′以及隙與它砌們關朝聯(lián)的袋邊所槐得的鳳子圖辯。10萌.4圖的廊運算邊收謀縮運堵算設圖G中邊e=貢(vi，vj)，刪去使邊e，并把vi與vj合并竄成一師個新禽點vi-杰j，使原捉來與vi或vj關聯(lián)炭的邊傅變?yōu)榘昱c點vi-冶j關聯(lián)鴨的邊招，稱鵝邊e被收縮，得笑到的驢新圖市稱為G關于嘴邊e的收溜縮圖聾，記蒙為G/帶e或G/vivj。如下有圖，德圖（b）是對芝圖(a李)的邊鑄（d，e）收縮室后得感到的津圖。adbcead-ebc(a這)(b今)10筆.4圖的思運算并與紐奉和運賤算設G1=(回V1，E1)，G2=(僑V2，E2)是兩壯個給勾定的修圖，瘡則定夏義：G1與G2的并捆為G1∪G2=(柱V1∪V2，E1∪E2)；G1與G2的和G1+G2是在G1與G2的并征的基擇礎上競需增男加G1的每牧個結(jié)愈點與G2的每杰個結(jié)隸點連組接得獵到的光共計mn條邊產(chǎn)，m，n分別飼為G1，G2的階棟。如惕下圖們所示悠，圖(a怠)為K2∪K3，圖(b巷)為K2+K3。aebcdaebcd(a篩)(b炎)10架.4圖的銹運算2補運禾算在集壟合論換與數(shù)殿理邏泳輯中顏都有側(cè)補運物算，嫁圖論懸中的狂補運仰算也纖類似載。圖G=核(V弊,E霜)的絕對挖補圖(簡稱袖圖G的補逃圖，狼記為G’)是相糟對于炕以V為結(jié)刺點集我所構(gòu)享成的擋完全敘圖而伸言，V(犧G’)=植V(遞G)和,且若會邊eKn,但eG，則eG’。如下墻圖所株示，(b樸)為(a理)的補觸圖。似顯然數(shù)，圖(a港)也是(b努)的補抬圖。蠟即有桿：G〞=G。afbdeafbde(a喘)(b曠)10命.4圖的夕運算上面英所定柿義的窗補圖中其實勵是相裙對完鄰全作千圖而擱言，星但事杰實上煩，也繪常常班需要胃求某慨圖G的子失圖G1相對G的補柔，稱偷為相對紹補，即V(愧G1’)=賓V(沿G)副,且若凍邊eG,但eG1，則eG1’。如下圖所弓示，(c壁)為(b強)相對肌于(a惠)的相綁對補滅圖。afbdeabdeafbde(a聯(lián))(b袍)(c啊)10差.4圖的出運算例10脖.1類9對于目任何禮一個哪具有6個結(jié)狀點的貪簡單尖圖G，存胳在一鬼個子澆圖K3或在G’中存磁在子降圖K3.證明考察G中任吵一結(jié)炒點u，u與G的其麗余5個結(jié)嗎點要詳么在G中鄰累接，跨要么差在G’中鄰鍬接。輩由于幕是5個結(jié)禍點，餡因此每，必濫然是性至少秒有3個結(jié)碼點在G中與u鄰接辜，或替者至污少有3個結(jié)衫點在G’中與u鄰接茫。不鋤妨假揀設有3個結(jié)只點x,吐y,蠶z與u在G中鄰抄接。偶若這3個結(jié)云點中猜有兩敲個如x,雷y在G中鄰懶接，充則u,述x,醋y構(gòu)成G的子運圖K3，若x,研y,貌z在G中兩趴兩不貸鄰接冊，則x,濫y,鼠z在G’中兩萌兩鄰圖接，弄即x,經(jīng)y,鹿z構(gòu)成G’中的蜂子圖K3。10昂.4圖的慮運算3笛卡撓爾積設圖G和H的結(jié)秘點集足分別已為{u1,u2,…棟,um}和{v1,v2,…新,vn}，G，H的笛談卡爾嘗積記減作GH,，其稻結(jié)點扇集由積標記攤為(i，j)的mn個結(jié)昨點組朵成，鉗其中1≤隨i≤覽m,沖1≤揭j≤胡n；當林且僅正當滿溝足下稅列兩戀個條奏件之菠一時患，兩章個結(jié)問點（i,田j），(h,垮k)鄰接嫂：1)證i慎=h，且vj和vk在圖H中鄰崗接；2)賺j雜=k蝦,且ui和uh在圖G中鄰向接。對于饅每個i，結(jié)南點集(i,己j)的導且出子桂圖是蓄圖H的副胸本，辱稱為H的第i個副嫩本，其敘中j=汪1,擋2,仇…,思n；對烈于每萬個j，結(jié)瀉點集(i,線j)的導撓出子拘圖是削圖G的副妖本，蝴稱為G的第j個副勿本，其盟中i=蹲1,桂2,朵…,攜m。10乞.4圖的吹運算例10欺.2鄉(xiāng)豐0如下燃圖所維示，GH為G，H的笛搏卡爾切積。橋可以皆看到GH中有G的三辟個副壺本，H的四盛個副伙本。瓦由于v1，v2鄰接辭，因尾此G的副績本1與副享本2的對生應結(jié)篩點鄰鑒接，肢由于v2，v3鄰接大，因輩此G的副局本2與副償本3的對抓應結(jié)蝕點鄰嘗接，鈔但v1，v3不鄰博接，獨因此G的副穿本1與副臨本3的對東應結(jié)垃點不扣鄰接魯。u1u2u3u4v1v2v3(1,1)(2,1)(3,1)(4,1)(4,2)(3,2)(2,2)(1,2)(1,3)(2,3)(3,3)(4,3)10菌.4圖的盞運算4超立蕉方體超立濫方體搬在并慨行計很算中趨的計貢算機挖體系矩結(jié)構(gòu)積中具攔有重鋤要的妥應用沫。超剩立方耗體Qn可以漿由笛株卡爾善積來縫定義常：Q0=K1,Qn=K2Qn-乳1.之所身以稱Qn為超立亭方體，是繞因為n=架3時，Qn可以后畫成晴三維害的立傘方體郵，且市可以擺擴展信到更紛高維綠。下蹄圖給薄出了典前5個超秤立方排體。劇超立金方體Qn的n是指Qn結(jié)點諸標號警所用慢的二這進制鵝位之肢長度良，且巨要求嫁相鄰呆結(jié)點撇標號腔只相尼差一匪位。莫所以Qn有2n個結(jié)把點。Qn這種泊編號趙方式季可用源在計嗚算機躺編碼臨如格樹雷碼愈的設途計方輝面，貧至于含如何旱實現(xiàn)Qn這樣牧的編發(fā)號，有其中骨一種稀方法莫是按丹照后扶文10伍.7節(jié)將賠討論來的找Qn中Ha徹mi稿lt量on環(huán)的例方法愧。10層.4圖的壞運算Q0Q1Q2Q3Q410狼.4圖的食運算5網(wǎng)格網(wǎng)格活也是翁計算孫機處夜理器?；ヂ?lián)筐一種前方式技，利蝦用笛諒卡爾鋤積也箱可以汗構(gòu)造塑網(wǎng)格摘。網(wǎng)窄格也限可以竊稱為網(wǎng)或格。2維網(wǎng)別格M(味m,設n)是由愁路徑Pm與Pn的笛嚴卡爾亞積來釣定義晶，即M(猾m,瓶n)=超PmPn。3維網(wǎng)認格M(主m,不n,漁k)是Pm與Pn、Pk的笛箭卡爾惡積來省定義巴，即M(訪m,頃n)=美PmPnPk。網(wǎng)格凍可以述擴展飽到n維。照圖9.綿21所示鋤的兩期個圖方分別次為網(wǎng)省格M(躲3,陶2)與M(唇3,爬2,忽3)。10告.4圖的劃運算M(3,2)M(3,2,3)10平.5圖的準表示盲與圖刻的同壓構(gòu)1圖的趣表示在集千合論說中，迷曾經(jīng)段用關爆系矩妻陣來紡表示積關系敘，事稠實上增，圖末也是幸一種凝關系漸的表孔示，女但用核計算氏機來啄分析匆一個煮圖時鹿，矩億陣是綱其更滑為形自式化摩的表剃示方漢法，鹽這里蕉主要瞎討論騾鄰接稿矩陣。構(gòu)造框一個魄圖的匯鄰接特矩陣械是很欲容易轟的，閥可以促通過躬下面以的例中子來錢分析蕩。10修.5圖的漁表示補與圖跌的同輕構(gòu)例10汁.2乎1構(gòu)造科下圖院中圖G的鄰墻接矩隱陣。峽顧名檢思義慎，鄰港接矩認陣就靜是表僚示圖粉結(jié)點竹的鄰違接關校系的仆矩陣駛，鄰款接矩碗陣與賠圖是綁一種瞧一一聞對應供關系通。首四先，鴨需要性確定戒圖結(jié)趕點的鄰順序興，本鏡題中樣為a，b，c，d，e。接贈著，幅矩陣葡的元擋素(ij)表示嗽第i個結(jié)嶼點與靜第j個結(jié)懼點的腐鄰接越關系淺，這國里用1或0來表會示，亦如果震鄰接明，則(ij)為1，否物則為0。于河是得旁到圖G的鄰掘接矩留陣A(債G)依=aedcb10把.5圖的炕表示蹈與圖鋪的同挪構(gòu)可以賞看到似，圖G的鄰查接矩井陣是純關于比主對喪角線滔對稱宿的，芒這是淘因為蒼這里彼討論少的圖景是無方向圖刑，但仿有向莊圖的蒙鄰接枝矩陣遞一般香不是顫對稱幕的，掛因此瀉，鄰貌接矩定陣對幕于表悲示有奔向圖光可能龜更有燭效。絲式后文勉繼續(xù)恩對無漏向圖惰展開扎討論扎，相兔關結(jié)課論也話可以含應用醒到有靠向圖伸中。鄰接震矩陣攪可以敵用來迷求解召圖中宗從一圖個結(jié)稠點到匪另一沾個結(jié)各點的族某長泊度的俊路徑津的數(shù)億目，妖如對你于例10仰.2暗1中圖跟的鄰喚接矩殺陣A(盟G)抱,有10壟.5圖的瞇表示岔與圖穗的同嬌構(gòu)A(規(guī)G)2==以A(槳G)2中d行c列的微元素麥為例剪，其議值是A(檔G)中第d行與A(漏G)中第c列運前算得書到，演即=1?1+運0?1+閣1?0+挎0?1+爆1?1=湖210僻.5圖的監(jiān)表示責與圖丟的同自構(gòu)顯然耐，可份以看城到，麗只有G中存支在形匯如(d,右v)與(v,攏c)的邊和，才瘋能形程成了床從d到c長度輛為2的路猴徑(a,序v,等c)。相應幅地，是這兩竭條邊渠在矩尚陣A(鳥G)中的筋值為1，于覆是其忘對A(付G)2的第d行c列元煉素值樓得貢臉獻分乓別為1。如A中存華在邊(d,膛a)以及點邊(a,持c)，從而難有長磁度為2的路籌徑(d,債a,留c)。此外速，還壓存在d到c的路欲徑(d,持e,袍c)。于是涼共存呆在d到c的長固度為2的路鍵徑2條，動因此禁，A(咬G)2的第d行c列元應素值絮為2。10然.5圖的肚表示穩(wěn)與圖逝的同梁構(gòu)定理9.赤7如果A是一藥個圖G的鄰渣接矩英陣，吉那么An（n=面1，2，3，…）中元捏素(ij)等于迎從結(jié)形點i到結(jié)佳點j的長豎度為n的路絨徑的仔數(shù)目箏。10楊.5圖的脅表示只與圖欣的同古構(gòu)2圖的旨同構(gòu)定義10廚.1享2設圖G1=<看V1,E1>，G2=<嘆V2,E2>，若舌存在造雙射f:擁V1V2，滿件足uV1，vV1，(u諷,v婦)E1當且請僅當(f帳(u甲),者f(贏v)脫)E2，則蕉稱G1與G2同構(gòu)，記捏作G1G2，f稱為同構(gòu)醋映射。如果膏討論維有向才圖的堪同構(gòu)冷，則截對應落邊的盟方向迎也必久須一述致。從圖糾的同渡構(gòu)的晴定義翼可知懼，二河圖同愛構(gòu)則釀必有界結(jié)點助數(shù)相簽同，恒邊數(shù)嫩相同刊，兩明圖中得度數(shù)飛相同里的結(jié)豆點的箭個數(shù)幅相同暗。還居可以登知道般，圖國的同離構(gòu)關謙系是綠一種復等價握關系擾。10斜.5圖的叢表示么與圖棋的同簡構(gòu)例10蒜.2黃3下圖中五，G1與G2不同修構(gòu)，木原因浪在于G1中存續(xù)在三廟結(jié)點脫兩兩適相鄰紅，而G2中不帶存在，因藍此不謊可能康建立胸滿足籮定義月的雙狼射關減系。蝦類似猛地，吳圖G4與G2不同么構(gòu)，捧原因估在于G4中存阿在三豪結(jié)點階兩兩戒不相匪鄰，底而G2中卻廚不存悄在這乎樣的俗情況穗。G1與G3同構(gòu)紹。G1G2G3G410吐.5圖的熟表示恩與圖狠的同銅構(gòu)圖的拒同構(gòu)張的判崇斷主舟要是顯建立屑同構(gòu)消映射棟，如左果能民夠建弄立，曾則同管構(gòu)的繩兩個咽圖除套了結(jié)瘡點符恒號相合異外柴，結(jié)紙構(gòu)上六是完躬全一惑樣的繭。因著此，址容易傳想到負考慮承用鄰政接矩免陣來駝進行斃判斷生，即杏：圖G1和G2是同傍構(gòu)的夕當且針僅當森對某做一結(jié)臨點的卻順序齡，其融鄰接星矩陣蹈是一歸樣的頓，最粗基本晃的方緞法是期通過翼變換委矩陣魄行、賓列元滲素的營順序勁來比鹿較二灶鄰接替矩陣依是否申相等遵。盡胡管通扎過判把斷鄰碰接矩煌陣來愁判斷決圖是禾否同靠構(gòu)是匆可行噸的，喊但在震最壞葉情況尋下，暴其搜后索空獵間將緒達到n!分(n為結(jié)狀點數(shù))，具鴉有指門數(shù)級吃算法珍復雜煩性。敘如果n很大除，算感法的卷效率擱是非技常低斜的，華甚至雜不可嘗解。10迎.5圖的補表示乒與圖芒的同掏構(gòu)從例10歡.2復3還可倡以看避到，蘇圖G1和G2同構(gòu)項時，G1具有票的特石性P，G2也應攜該具鑼備這勒個特兼性P。于是囑判斷肉兩個非圖G1和G2不同點構(gòu)的池辦法燥可以斥是：病找到敢一個G1的特貼性P，G2并不譽具備陡。這纖樣的蓬一個滑特性臭稱為剪不變凝量。馳如“胳有10個結(jié)五點”映、“罰有一鐘個度外數(shù)為k的結(jié)沖點”完，以支及例10葵.2澡3中用帳到的盞“有k個結(jié)豈點兩康兩相甚鄰（效或不架相鄰何）”聯(lián)等等服。如治果能年夠找饅到一詳些可趨以簡挺單測渾試的帆同構(gòu)脆圖具刃有且嬌只有險同構(gòu)機圖具鈴有的鉆不變把量，耗那么拳就可句以非放常容菠易的走判斷奔兩個漫圖是洽否同購構(gòu)。夠不幸零的是敗，沒遼有人遍能夠效成功念找到槐這樣偉一些潔不變零量。10跳.5圖的態(tài)表示羞與圖前的同劫構(gòu)例10封.2偽4若圖G與其冠補圖戰(zhàn)同構(gòu)竟，則皂稱G為自補劍圖。請奧找出仗所有其的階賄數(shù)小費于6的自暖補圖衛(wèi)。解所找圖到的既階數(shù)再小于6的自闊補圖哭有4個，眾如下憶圖所膊示。10菌.5圖的子表示超與圖啦的同烈構(gòu)練習7畫出林完全抱圖K5的4條邊戲的所區(qū)有非劍同構(gòu)鐮的生升成子鞋圖。10擾.5圖的友表示猶與圖嘗的同土構(gòu)練習8畫出希所有枕具有5個結(jié)羅點3條邊隔的互癢不同釣構(gòu)的梳簡單虹無向匙圖。10干.5圖的付表示蕩與圖本的同鄭構(gòu)練習9設G是具理有3個結(jié)