圖論課件第一章圖的基本概念

圖論課件第一章圖的基本概念1第1頁，共41頁，2023年，2月20日，星期六《圖論及其應(yīng)用》

作者:張先迪、李正良

購買地點(diǎn)：教材科2第2頁，共41頁，2023年，2月20日，星期六參考文獻(xiàn)[1]美，幫迪《圖論及其應(yīng)用》[2]美，GaryChartrand《圖論導(dǎo)引》，人民郵電出版社，2007[3]BelaBollobas，《現(xiàn)代圖論》，科學(xué)出版社，2001中國科學(xué)院研究生教學(xué)叢書[4]美，F(xiàn)redBuckley《圖論簡(jiǎn)明教程》，清華大學(xué)出版社，2005李慧霸王風(fēng)芹譯3第3頁，共41頁，2023年，2月20日，星期六[5]李尉萱，《圖論》，湖南科學(xué)技術(shù)出版社，1979[6]美，DouglasB.West《圖論導(dǎo)引》，機(jī)械工業(yè)出版社，2007李建中，駱吉洲譯[7]楊洪，《圖論常用算法選編》，中國鐵道出版社，1988[8]陳樹柏，《網(wǎng)絡(luò)圖論及其應(yīng)用》，科學(xué)出版社，19824第4頁，共41頁，2023年，2月20日，星期六[9]ChrisGodsil，GordonRoyle《AlgebraicGraphTheory》，世界圖書出版公司北京公司，2004[10]王朝瑞，《圖論》，高等教育出版社，19835第5頁，共41頁，2023年，2月20日，星期六第一章圖的基本概念本次課主要內(nèi)容圖的概念與圖論模型(一)、圖論課程簡(jiǎn)介(二)、圖的定義與圖論模型(三)、圖的同構(gòu)(五)、頂點(diǎn)的度與圖的度序列(四)、完全圖、偶圖與補(bǔ)圖6第6頁，共41頁，2023年，2月20日，星期六1、研究對(duì)象圖論是研究點(diǎn)與線組成的“圖形”問題的一門科學(xué)。屬于應(yīng)用數(shù)學(xué)分支。(一)、圖論課程簡(jiǎn)介2、發(fā)展歷史圖論起源于18世紀(jì)的1736年，標(biāo)志事件是“哥尼斯堡七橋問題數(shù)學(xué)家歐拉被稱為“圖論之父”20世紀(jì)30年代出版第一本圖論著作7第7頁，共41頁，2023年，2月20日，星期六3、應(yīng)用狀況圖論的應(yīng)用已經(jīng)涵蓋了人類學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)、環(huán)境保護(hù)、流體動(dòng)力學(xué)、心理學(xué)、社會(huì)學(xué)、交通管理、電信以及數(shù)學(xué)本身等。目前，圖論已形成很多分支：如結(jié)構(gòu)圖論、網(wǎng)絡(luò)圖論、代數(shù)圖論、拓?fù)鋱D論等4、教學(xué)安排主要介紹圖的一些基本概念、基本理論和圖論的典型應(yīng)用。60學(xué)時(shí)。8第8頁，共41頁，2023年，2月20日，星期六1、圖的定義(二)、圖的定義與圖論模型一個(gè)圖是一個(gè)序偶<V,E>，記為G=(V,E),其中：(1)V是一個(gè)有限的非空集合，稱為頂點(diǎn)集合,其元素稱為頂點(diǎn)或點(diǎn)。用|V|表示頂點(diǎn)數(shù)；(2)E是由V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對(duì)在E中可以重復(fù)出現(xiàn)多次。用|E|表示邊數(shù)。9第9頁，共41頁，2023年，2月20日，星期六圖可以用圖形表示：V中的元素用平面上一個(gè)黑點(diǎn)表示，E中的元素用一條連接V中相應(yīng)點(diǎn)對(duì)的任意形狀的線表示。例1、設(shè)圖G＝<V,E>。這里V＝{v1,v2,v3,v4}E＝{e1,e2,e3,e4,e5,e6}，e1＝(v1,v2)，e2＝(v1,v3)，e3＝(v1,v4)，e4＝(v2,v3)，e5＝(v3,v2)，e6＝(v3,v3)。v1v2v3v4e1e2e3e4e5e610第10頁，共41頁，2023年，2月20日，星期六圖的相關(guān)概念：有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；平凡圖：只有一個(gè)頂點(diǎn)的圖稱為平凡圖；空?qǐng)D：邊集為空的圖稱為空?qǐng)D；n階圖：頂點(diǎn)數(shù)為n的圖稱為n階圖；(n,m)圖：頂點(diǎn)數(shù)為n,邊數(shù)為m的圖稱為(n,m)圖；邊的重?cái)?shù)：連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)稱為邊的重?cái)?shù)；重?cái)?shù)大于1的邊稱為重邊；環(huán)：端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)；簡(jiǎn)單圖：無環(huán)無重邊的圖稱為簡(jiǎn)單圖；其余的圖稱為復(fù)合圖；11第11頁，共41頁，2023年，2月20日，星期六頂點(diǎn)u與v相鄰接：頂點(diǎn)u與v間有邊相連接；其中u與v稱為該邊的兩個(gè)端點(diǎn)；頂點(diǎn)u與邊e相關(guān)聯(lián)：頂點(diǎn)u是邊e的端點(diǎn)；邊e1與邊e2相鄰接：邊e1與邊e2有公共端點(diǎn)；2、圖論模型為了抽象和簡(jiǎn)化現(xiàn)實(shí)世界，常建立數(shù)學(xué)模型。圖是關(guān)系的數(shù)學(xué)表示，為了深刻理解事物之間的聯(lián)系，圖是常用的數(shù)學(xué)模型。(1)化學(xué)中的圖論模型19世紀(jì)，化學(xué)家凱萊用圖論研究簡(jiǎn)單烴——即碳?xì)浠衔?2第12頁，共41頁，2023年，2月20日，星期六用點(diǎn)抽象分子式中的碳原子和氫原子，用邊抽象原子間的化學(xué)鍵。通過這樣的建模，能很好研究簡(jiǎn)單烴的同分異構(gòu)現(xiàn)象例如：C4H10的兩種同分異構(gòu)結(jié)構(gòu)圖模型為：hhhhhhhhhhhhhhhhhhhh13第13頁，共41頁，2023年，2月20日，星期六(2)商業(yè)中的圖論模型商業(yè)中，經(jīng)常用圖來對(duì)倉庫和零售店進(jìn)行建模例如：令V={w1,w2,w3,r1,r2,r3,r4,r5}代表3個(gè)倉庫和5個(gè)零售點(diǎn)E={w1r1,w1r2,w2r2,w2r3,w2r4,w3r3,w3r5}代表每個(gè)倉庫和每個(gè)零售店間的關(guān)聯(lián)。則圖模型圖形為：w1r1r2w2r3r4w3r5(3)最短航線問題14第14頁，共41頁，2023年，2月20日，星期六用點(diǎn)表示城市，兩點(diǎn)連線當(dāng)且僅當(dāng)兩城市有航線。為了求出兩城市間最短航線，需要在線的旁邊注明距離值。例如：令V={a,b,c,d,e}代表5個(gè)城市}E={ab,ad,bc,be,de}代表城市間的直達(dá)航線則航線圖的圖形為：abcde500320140430370請(qǐng)求出從d到c的最短路15第15頁，共41頁，2023年，2月20日，星期六(4)任務(wù)分配問題有一個(gè)旅行團(tuán)要組織一批人去旅游，其中一些人是朋友他們要乘坐公共汽車去，而車上的位子是成對(duì)的。因此為了讓大家旅途更愉快，旅行團(tuán)負(fù)責(zé)人需要將成對(duì)的朋友安排在一起。給出一種安排方案。該問題可以建立一個(gè)圖論模型來解決：旅行團(tuán)的人抽象為圖的頂點(diǎn)，兩個(gè)頂點(diǎn)連線，當(dāng)且僅當(dāng)兩個(gè)頂點(diǎn)代表的人是朋友。問題歸結(jié)于在模型圖中求所謂的“匹配”，關(guān)于圖的匹配將在第五章介紹。16第16頁，共41頁，2023年，2月20日，星期六(5)考試時(shí)間安排問題一個(gè)教授需要對(duì)期末考試時(shí)間進(jìn)行安排，使得學(xué)生們不會(huì)有相互沖突的考試。如何解決？該問題可以建立一個(gè)圖論模型來解決：待考的課程可抽象為圖的頂點(diǎn)，連接兩個(gè)頂點(diǎn)的邊表示至少有一個(gè)學(xué)生同時(shí)選擇了這兩門課程。問題歸結(jié)于在模型圖中求所謂的“頂點(diǎn)著色方案”問題，該問題將在第七章討論。例如：有a,b,c,d,e,f六門課程。按照上面方法建立的模型圖如下：17第17頁，共41頁，2023年，2月20日，星期六一種可行的安排方案為：第一時(shí)間：a,d,e;第二時(shí)間：b,f；最后：c.abcefd另一種可行的安排方案為：第一時(shí)間：a,e;第二時(shí)間：c,d；最后：b,f.(6)旅行售貨員問題一電腦代理商要從她所在城市出發(fā)，乘飛機(jī)去六個(gè)城市，然后回到出發(fā)點(diǎn)，如果要求每個(gè)城市只經(jīng)歷一次，能否辦到？給出行走方案。18第18頁，共41頁，2023年，2月20日，星期六問題歸結(jié)為在模型圖中尋求所謂的“哈密爾頓圈”問題。將在第四章介紹。例如：如果模型圖如下：該問題可以建立一個(gè)圖論模型來解決：城市抽象為圖的頂點(diǎn)，邊代表城市間的直達(dá)航線。abcdef可行方案:(1)h,d,e,c,b,a,h(2)h,d,e,c,a,b,h19第19頁，共41頁，2023年，2月20日，星期六在圖論中，一個(gè)很值得研究的問題是如何比較兩個(gè)圖的異同，這就是圖的同構(gòu)問題。定義：設(shè)有兩個(gè)圖G1=(V1,E1)和G2=(V2,E2),若在其頂點(diǎn)集合間存在雙射，使得邊之間存在如下關(guān)系：設(shè)u1?u2v1?v2,u1,v1V1,u2,v2V2;u1v1E1,當(dāng)且僅當(dāng)u2v2E2,且u1v1與u2v2的重?cái)?shù)相同。稱G1與G2同構(gòu)，記為：由定義可以得到圖同構(gòu)的幾個(gè)必要條件：(三)、圖的同構(gòu)

(1)頂點(diǎn)數(shù)相同；(2)邊數(shù)相同；(3)關(guān)聯(lián)邊數(shù)相同的頂點(diǎn)個(gè)數(shù)相同。20第20頁，共41頁，2023年，2月20日，星期六判定圖的同構(gòu)是很困難的，屬于NP完全問題。對(duì)于規(guī)模不大的兩個(gè)圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。例2證明下面兩圖不同構(gòu)。u1v1證明:u1的兩個(gè)鄰接點(diǎn)與v1的兩個(gè)鄰接點(diǎn)狀況不同。所以，兩圖不同構(gòu)。21第21頁，共41頁，2023年，2月20日，星期六例3證明下面兩圖同構(gòu)。證明:作映射f:vi?ui(i=1,2….10)容易證明，對(duì)vivjE((a)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由圖的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。22第22頁，共41頁，2023年，2月20日，星期六例4指出4個(gè)頂點(diǎn)的非同構(gòu)的所有簡(jiǎn)單圖。分析：四個(gè)頂點(diǎn)的簡(jiǎn)單圖最少邊數(shù)為0，最多邊數(shù)為6，所以可按邊數(shù)進(jìn)行枚舉。23第23頁，共41頁，2023年，2月20日，星期六(四)、完全圖、偶圖與補(bǔ)圖1、每?jī)蓚€(gè)不同的頂點(diǎn)之間都有一條邊相連的簡(jiǎn)單圖稱為完全圖.在同構(gòu)意義下，n個(gè)頂點(diǎn)的完全圖只有一個(gè)，記為KnK2K3K5容易求出：24第24頁，共41頁，2023年，2月20日，星期六

2、所謂具有二分類（X,Y）的偶圖（或二部圖）是指一個(gè)圖，它的點(diǎn)集可以分解為兩個(gè)(非空)子集X和Y，使得每條邊的一個(gè)端點(diǎn)在X中，另一個(gè)端點(diǎn)在Y中.完全偶圖是指具有二分類（X,Y）的簡(jiǎn)單偶圖，其中X的每個(gè)頂點(diǎn)與Y的每個(gè)頂點(diǎn)相連，若|X|=m，|Y|=n，則這樣的偶圖記為Km,n

圖1圖2圖1與圖2均是偶圖，圖2是K2,325第25頁，共41頁，2023年，2月20日，星期六3、對(duì)于一個(gè)簡(jiǎn)單圖G=（V,E），令集合則圖H=（V，E1\E）稱為G的補(bǔ)圖，記為

例如，如下兩個(gè)圖是互補(bǔ)的。定理：若n階圖G是自補(bǔ)圖(),則有：證明：n階圖G是自補(bǔ)圖，則有：26第26頁，共41頁，2023年，2月20日，星期六所以：由于n是正整數(shù)，所以：(五)、頂點(diǎn)的度與圖的度序列G的頂點(diǎn)v的度d(v)是指G中與v關(guān)聯(lián)的邊的數(shù)目，每個(gè)環(huán)計(jì)算兩次。1、頂點(diǎn)的度及其性質(zhì)分別用δ(G)和Δ(G)表示圖G的最小與最大度。27第27頁，共41頁，2023年，2月20日，星期六奇數(shù)度的頂點(diǎn)稱為奇點(diǎn)，偶數(shù)度的頂點(diǎn)稱偶點(diǎn)。設(shè)G=(V,E)為簡(jiǎn)單圖，如果對(duì)所有，有d(v)=k，稱圖G為k-正則圖

定理：圖G=(V,E)中所有頂點(diǎn)的度的和等于邊數(shù)m的2倍，即：證明：由頂點(diǎn)度的定義知：圖中每條邊給圖的總度數(shù)貢獻(xiàn)2度，所以，總度數(shù)等于邊數(shù)2倍。注：該定理稱為圖論第一定理，是由歐拉提出的。歐拉一身發(fā)表論文886篇，著作90部。該定理還有一個(gè)名字：“握手定理”。28第28頁，共41頁，2023年，2月20日，星期六推論1在任何圖中，奇點(diǎn)個(gè)數(shù)為偶數(shù)。證明：設(shè)V1,V2分別是G中奇點(diǎn)集和偶點(diǎn)集.則由握手定理有：是偶數(shù)，由于是偶數(shù)，所以是偶數(shù)，于是是偶數(shù)。推論2正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。證明：設(shè)G是k-正則圖，若k為奇數(shù)，則由推論1知正則圖G的點(diǎn)數(shù)必為偶數(shù)例4Δ與δ是簡(jiǎn)單圖G的最大度與最小度，求證：29第29頁，共41頁，2023年，2月20日，星期六證明：由握手定理有：所以有：2、圖的度序列及其性質(zhì)一個(gè)圖G的各個(gè)點(diǎn)的度d1,d2,…,dn構(gòu)成的非負(fù)整數(shù)組

(d1,d2,…,dn)稱為G的度序列。任意一個(gè)圖G對(duì)應(yīng)唯一一個(gè)度序列，圖的度序列是刻畫圖的特征的重要“拓?fù)洳蛔兞俊薄?0第30頁，共41頁，2023年，2月20日，星期六圖G的“拓?fù)洳蛔兞俊笔侵概c圖G有關(guān)的一個(gè)數(shù)或數(shù)組(向量)。它對(duì)于與圖G同構(gòu)的所有圖來說，不會(huì)發(fā)生改變。一個(gè)圖G可以對(duì)應(yīng)很多拓?fù)洳蛔兞?。如果某組不變量可完全決定一個(gè)圖，稱它為不變量的完全集。定理：非負(fù)整數(shù)組(d1,d2,….,dn)是圖的度序列的充分必要條件是：為偶數(shù)。證明：必要性由握手定理立即得到。如果為偶數(shù)，則數(shù)組中為奇數(shù)的數(shù)字個(gè)數(shù)必為偶數(shù)。按照如下方式作圖G:若di為偶數(shù)，則在與之對(duì)應(yīng)的點(diǎn)作di/2個(gè)環(huán)；對(duì)于剩下的偶數(shù)個(gè)奇數(shù)，31第31頁，共41頁，2023年，2月20日，星期六兩兩配對(duì)后分別在每配對(duì)點(diǎn)間先連一條邊，然后在每個(gè)頂點(diǎn)畫dj-1/2個(gè)環(huán)。該圖的度序列就是已知數(shù)組。一個(gè)非負(fù)數(shù)組如果是某簡(jiǎn)單圖的度序列，我們稱它為可圖序列，簡(jiǎn)稱圖序列。關(guān)于圖序列，主要研究3個(gè)問題：(1)存在問題：什么樣的整數(shù)組是圖序列？(2)計(jì)數(shù)問題：一個(gè)圖序列對(duì)應(yīng)多少不同構(gòu)的圖？(3)構(gòu)造問題：如何畫出圖序列對(duì)應(yīng)的所有不同構(gòu)圖？研究現(xiàn)狀:(1)徹底解決了，(2)解決得不好，(3)沒有解決。32第32頁，共41頁，2023年，2月20日，星期六定理：非負(fù)整數(shù)組是圖序列的充分必要條件是：是圖序列。證明：設(shè)G是Π對(duì)應(yīng)的簡(jiǎn)單圖，d(vi)=di情形1：點(diǎn)v1與點(diǎn)v2,v3,…,vd1+1鄰接，則G-v1的度序列正好為Π133第33頁，共41頁，2023年，2月20日，星期六情形2：點(diǎn)v1與點(diǎn)vd1+2，….vn的某些頂點(diǎn)鄰接。在這種情況下，作如下假設(shè)：設(shè)v1與vj0鄰接，但當(dāng)k>j0時(shí)，v1與vk不鄰接；又設(shè)v1與vi0不鄰接，但當(dāng)k<i0時(shí)，v1與點(diǎn)vk鄰接。v1v2v3vi0-1vj0vi0vn則在圖中，必然存在點(diǎn)vm，使得vm與vi0鄰接，但是它與vj0不鄰接，否則，有dj0≥di0+1,矛盾！現(xiàn)在，在圖中去掉邊v1vj0和vi0vm,加上邊vj0vm和v1vi0,顯然新圖與原圖度序列相同，但j0減小了，i0增大了！34第34頁，共41頁，2023年，2月20日，星期六如此進(jìn)行下去，最后可以變情形2為情形1。是顯然的。例5是否為圖序列？如果是，作出對(duì)應(yīng)的一個(gè)簡(jiǎn)單圖。解：由于