電子科大圖論課件第一章

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖論及其應(yīng)用圖論及其應(yīng)用任課教師：楊春任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)科學(xué)學(xué)院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2圖論及其應(yīng)用圖論及其應(yīng)用 作者作者: 張先迪、李正良張先迪、李正良 購買地點(diǎn)：教材科購買地點(diǎn)：教材科 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3參考文獻(xiàn)參考文獻(xiàn)1 美，幫迪圖論及其應(yīng)用美，幫迪圖論及其應(yīng)用2 美，美，G

2、ary Chartrand圖論導(dǎo)引圖論導(dǎo)引，人民郵電，人民郵電出版社，出版社，20073 Bela Bollobas，現(xiàn)代圖論，現(xiàn)代圖論，科學(xué)出版社，科學(xué)出版社，2001 中國科學(xué)院研究生教學(xué)叢書中國科學(xué)院研究生教學(xué)叢書4 美，美，F(xiàn)red Buckley圖論簡明教程圖論簡明教程，清華大學(xué)，清華大學(xué)出版社，出版社，2005 李慧霸李慧霸 王風(fēng)芹譯王風(fēng)芹譯 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 45 李尉萱，圖論，湖南科學(xué)技術(shù)出版社，李尉萱，圖論，湖南科學(xué)技術(shù)出版社，19796 美，美，Douglas B.West圖論導(dǎo)引圖論

3、導(dǎo)引，機(jī)械工業(yè)出，機(jī)械工業(yè)出版社，版社，2007 李建中，駱吉洲譯李建中，駱吉洲譯7 楊洪，圖論常用算法選編，中國鐵道出版社，楊洪，圖論常用算法選編，中國鐵道出版社，19888 陳樹柏，網(wǎng)絡(luò)圖論及其應(yīng)用，科學(xué)出版社，陳樹柏，網(wǎng)絡(luò)圖論及其應(yīng)用，科學(xué)出版社，1982 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 59 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界圖書出版公司北京公司，世界圖書出版公司北京公司，200410 王朝瑞，圖論，高等教育出版社，王朝瑞，圖論，高等教育出版社

4、，1983 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6第一章第一章 圖的基本概念圖的基本概念本次課主要內(nèi)容本次課主要內(nèi)容圖的概念與圖論模型圖的概念與圖論模型(一一)、圖論課程簡介、圖論課程簡介(二二)、圖的定義與圖論模型、圖的定義與圖論模型(三三)、圖的同構(gòu)、圖的同構(gòu) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 71 1、研究對象、研究對象 圖論是研究點(diǎn)與線組成的圖論是研究點(diǎn)與線組成的“圖形圖形”問題的一門科問題的一門科學(xué)。屬于應(yīng)用數(shù)學(xué)分支學(xué)。屬于應(yīng)用數(shù)學(xué)分支.(

5、一一)、圖論課程簡介、圖論課程簡介2 2、發(fā)展歷史、發(fā)展歷史 圖論起源于圖論起源于18世紀(jì)的世紀(jì)的1736年，標(biāo)志事件是年，標(biāo)志事件是“哥尼哥尼斯堡七橋問題斯堡七橋問題.數(shù)學(xué)家歐拉被稱為數(shù)學(xué)家歐拉被稱為“圖論之父圖論之父”.20世紀(jì)世紀(jì)30年代出版第一本圖論著作年代出版第一本圖論著作. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 83 3、應(yīng)用狀況、應(yīng)用狀況 圖論的應(yīng)用已經(jīng)涵蓋了人類學(xué)、計算機(jī)科學(xué)、化圖論的應(yīng)用已經(jīng)涵蓋了人類學(xué)、計算機(jī)科學(xué)、化學(xué)、環(huán)境保護(hù)、非線性物理、心理學(xué)、社會學(xué)、交學(xué)、環(huán)境保護(hù)、非線性物理、心理學(xué)、社會學(xué)、交通

6、管理、電信以及數(shù)學(xué)本身等通管理、電信以及數(shù)學(xué)本身等。 目前，圖論已形成很多分支：如隨機(jī)圖論、網(wǎng)絡(luò)目前，圖論已形成很多分支：如隨機(jī)圖論、網(wǎng)絡(luò)圖論、代數(shù)圖論、拓?fù)鋱D論、極值圖論等。圖論、代數(shù)圖論、拓?fù)鋱D論、極值圖論等。4 4、教學(xué)安排、教學(xué)安排 主要介紹圖的一些基本概念、基本理論和圖論的主要介紹圖的一些基本概念、基本理論和圖論的典型應(yīng)用。典型應(yīng)用。60學(xué)時。學(xué)時。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 91 1、圖的定義、圖的定義(二二)、圖的定義與圖論模型、圖的定義與圖論模型 一個圖是一個序偶一個圖是一個序偶，記，記為為G=(

7、V,E),其中：其中：(1) V是一個有限的非空集合，稱為頂點(diǎn)集合是一個有限的非空集合，稱為頂點(diǎn)集合,其其元素稱為頂點(diǎn)或點(diǎn)。用元素稱為頂點(diǎn)或點(diǎn)。用|V|V|表示頂點(diǎn)數(shù)；表示頂點(diǎn)數(shù)；(2) E是由是由V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在為邊集，其元素稱為邊，且同一點(diǎn)對在E中可以中可以重復(fù)出現(xiàn)多次。用重復(fù)出現(xiàn)多次。用|E|E|表示邊數(shù)。表示邊數(shù)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10圖可以用圖形表示：圖可以用圖形表示：V中的元素用平面上一個黑點(diǎn)表示，中的元素用

8、平面上一個黑點(diǎn)表示，E中的元素用一條連接中的元素用一條連接V中相應(yīng)點(diǎn)對的任意形狀的線表示。中相應(yīng)點(diǎn)對的任意形狀的線表示。例例1、設(shè)圖、設(shè)圖G。這里。這里Vv1,v2,v3,v4Ee1,e2,e3,e4,e5,e6，e e1 1(v(v1 1,v,v2 2) )，e e2 2(v(v1 1,v,v3 3) )，e e3 3(v(v1 1,v,v4 4) )，e e4 4(v(v2 2,v,v3 3) )，e e5 5(v(v3 3,v,v2 2) )，e e6 6(v(v3 3,v,v3 3) )。v1v2v3v4e1e2e3e4e5e6 0.8 1 0.6 0.4 0.2 0 x t 0 0.

9、5 1 1.5 2 1 0.5 0 0.5 1 n 11圖的相關(guān)概念：圖的相關(guān)概念：有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；平凡圖：只有一個頂點(diǎn)的圖稱為平凡圖；平凡圖：只有一個頂點(diǎn)的圖稱為平凡圖；空圖：邊集為空的圖稱為空圖；空圖：邊集為空的圖稱為空圖；n階圖：頂點(diǎn)數(shù)為階圖：頂點(diǎn)數(shù)為n的圖稱為的圖稱為n階圖；階圖；(n, m) 圖：頂點(diǎn)數(shù)為圖：頂點(diǎn)數(shù)為n,邊數(shù)為邊數(shù)為m的圖稱為的圖稱為(n, m) 圖；圖；邊的重數(shù)：連接兩個相同頂點(diǎn)的邊的條數(shù)稱為邊的重數(shù)；邊的重數(shù)：連接兩個相同頂點(diǎn)的邊的條數(shù)稱為邊的重數(shù)；重數(shù)大于重數(shù)大于1的邊稱為重邊；的邊稱為重邊；環(huán)

10、：端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)；環(huán)：端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)；簡單圖：無環(huán)無重邊的圖稱為簡單圖；其余的圖稱為簡單圖：無環(huán)無重邊的圖稱為簡單圖；其余的圖稱為復(fù)合圖；復(fù)合圖； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12頂點(diǎn)頂點(diǎn)u與與v相鄰接：頂點(diǎn)相鄰接：頂點(diǎn)u與與v間有邊相連接；其中間有邊相連接；其中u與與v稱為稱為該邊的兩個端點(diǎn)；該邊的兩個端點(diǎn)；頂點(diǎn)頂點(diǎn)u與邊與邊e相關(guān)聯(lián)：頂點(diǎn)相關(guān)聯(lián)：頂點(diǎn)u是邊是邊e的端點(diǎn)；的端點(diǎn)；邊邊e1與邊與邊e2相鄰接：邊相鄰接：邊e1與邊與邊e2有公共端點(diǎn)；有公共端點(diǎn)；2 2、圖論模型、圖論模型為了抽象和

11、簡化現(xiàn)實(shí)世界，常建立數(shù)學(xué)模型。圖是關(guān)系的為了抽象和簡化現(xiàn)實(shí)世界，常建立數(shù)學(xué)模型。圖是關(guān)系的數(shù)學(xué)表示，為了深刻理解事物之間的聯(lián)系，圖是常用的數(shù)學(xué)數(shù)學(xué)表示，為了深刻理解事物之間的聯(lián)系，圖是常用的數(shù)學(xué)模型。模型。(1) 化學(xué)中的圖論模型化學(xué)中的圖論模型19世紀(jì)，化學(xué)家凱萊用圖論研究簡單烴世紀(jì)，化學(xué)家凱萊用圖論研究簡單烴即碳?xì)浠衔锛刺細(xì)浠衔?0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13用點(diǎn)抽象分子式中的碳原子和氫原子，用邊抽象原子間用點(diǎn)抽象分子式中的碳原子和氫原子，用邊抽象原子間的化學(xué)鍵。的化學(xué)鍵。通過這樣的建模，能很好研究簡單烴

12、的同分異構(gòu)現(xiàn)象通過這樣的建模，能很好研究簡單烴的同分異構(gòu)現(xiàn)象.例如：例如：C4H10的兩種同分異構(gòu)結(jié)構(gòu)圖模型為：的兩種同分異構(gòu)結(jié)構(gòu)圖模型為：hhhhhhhhhhhhhhhhhhhh 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14(2) 商業(yè)中的圖論模型商業(yè)中的圖論模型商業(yè)中，經(jīng)常用圖來對倉庫和零售店進(jìn)行建模商業(yè)中，經(jīng)常用圖來對倉庫和零售店進(jìn)行建模例如：令例如：令V=w1,w2,w3,r1,r2,r3,r4,r5代表代表3個倉庫和個倉庫和5個零售點(diǎn)個零售點(diǎn)E=w1r1, w1r2, w2r2, w2r3, w2r4, w3r3,

13、w3r5代表每個倉庫和每個代表每個倉庫和每個零售店間的關(guān)聯(lián)。則圖模型圖形為：零售店間的關(guān)聯(lián)。則圖模型圖形為：w1r1r2w2r3r4w3r5(3) 最短航線問題最短航線問題 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15用點(diǎn)表示城市，兩點(diǎn)連線當(dāng)且僅當(dāng)兩城市有航線。為了用點(diǎn)表示城市，兩點(diǎn)連線當(dāng)且僅當(dāng)兩城市有航線。為了求出兩城市間最短航線，需要在線的旁邊注明距離值。求出兩城市間最短航線，需要在線的旁邊注明距離值。例如：令例如：令V=a, b, c, d, e代表代表5個城市個城市E=a b, ad, b c , be, de代表城市

14、間的直達(dá)航線代表城市間的直達(dá)航線則航線圖的圖形為：則航線圖的圖形為：abcde500320140430370請求出從請求出從d到到c的最短路的最短路 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16(4) 任務(wù)分配問題任務(wù)分配問題 有一個旅行團(tuán)要組織一批人去旅游，其中一些人是朋友有一個旅行團(tuán)要組織一批人去旅游，其中一些人是朋友他們要乘坐公共汽車去，而車上的位子是成對的。因此他們要乘坐公共汽車去，而車上的位子是成對的。因此為了讓大家旅途更愉快，旅行團(tuán)負(fù)責(zé)人需要將成對的朋為了讓大家旅途更愉快，旅行團(tuán)負(fù)責(zé)人需要將成對的朋友安排在一起。給

15、出一種安排方案。友安排在一起。給出一種安排方案。 該問題可以建立一個圖論模型來解決：旅行團(tuán)的人抽象該問題可以建立一個圖論模型來解決：旅行團(tuán)的人抽象為圖的頂點(diǎn)，兩個頂點(diǎn)連線，當(dāng)且僅當(dāng)兩個頂點(diǎn)代表的為圖的頂點(diǎn)，兩個頂點(diǎn)連線，當(dāng)且僅當(dāng)兩個頂點(diǎn)代表的人是朋友。人是朋友。 問題歸結(jié)于在模型圖中求所謂的問題歸結(jié)于在模型圖中求所謂的“匹配匹配”，關(guān)于圖的匹配，關(guān)于圖的匹配將在第五章介紹。將在第五章介紹。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17(5) 考試時間安排問題考試時間安排問題 一個教授需要對期末考試時間進(jìn)行安排，使得學(xué)生們一個教

16、授需要對期末考試時間進(jìn)行安排，使得學(xué)生們不會有相互沖突的考試。如何解決？不會有相互沖突的考試。如何解決？ 該問題可以建立一個圖論模型來解決：待考的課程可該問題可以建立一個圖論模型來解決：待考的課程可抽象為圖的頂點(diǎn)，連接兩個頂點(diǎn)的邊表示至少有一個學(xué)生抽象為圖的頂點(diǎn)，連接兩個頂點(diǎn)的邊表示至少有一個學(xué)生同時選擇了這兩門課程。同時選擇了這兩門課程。 問題歸結(jié)于在模型圖中求所謂的問題歸結(jié)于在模型圖中求所謂的“頂點(diǎn)著色方案頂點(diǎn)著色方案”問題，問題，該問題將在第七章討論。該問題將在第七章討論。 例如：有例如：有a, b, c ,d, e, f 六門課程。按照上面方法建立六門課程。按照上面方法建立的模型圖如下

17、：的模型圖如下： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 一種可行的安排方案為：第一時間：一種可行的安排方案為：第一時間：a, d, e;第二時間：第二時間：b, f ；最后：；最后：c.abcefd 另一種可行的安排方案為：第一時間：另一種可行的安排方案為：第一時間：a, e;第二時間：第二時間：c, d ；最后：；最后：b, f .(6) 旅行售貨員問題旅行售貨員問題 一電腦代理商要從她所在城市出發(fā)，乘飛機(jī)去六個城市，一電腦代理商要從她所在城市出發(fā)，乘飛機(jī)去六個城市，然后回到出發(fā)點(diǎn)，如果要求每個城市只經(jīng)歷一次，能否辦

18、然后回到出發(fā)點(diǎn)，如果要求每個城市只經(jīng)歷一次，能否辦到？給出行走方案。到？給出行走方案。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 問題歸結(jié)為在模型圖中尋求所謂的問題歸結(jié)為在模型圖中尋求所謂的“哈密爾頓圈哈密爾頓圈”問題。問題。將在第四章介紹。將在第四章介紹。 例如：如果模型圖如下：例如：如果模型圖如下： 該問題可以建立一個圖論模型來解決：城市抽象為該問題可以建立一個圖論模型來解決：城市抽象為圖的頂點(diǎn)，邊代表城市間的直達(dá)航線。圖的頂點(diǎn)，邊代表城市間的直達(dá)航線。abcdef 可行方案可行方案: (1) h, d, e, c,

19、b, a, h (2) h, d, e, c, a, b, h 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 在圖論中，一個很值得研究的問題是如何比較兩個在圖論中，一個很值得研究的問題是如何比較兩個圖的異同，這就是圖的同構(gòu)問題。圖的異同，這就是圖的同構(gòu)問題。 定義：設(shè)有兩個圖定義：設(shè)有兩個圖G1=(V1,E1)和和G2=(V2,E2),若在其頂點(diǎn)若在其頂點(diǎn)集合間存在雙射，使得邊之間存在如下關(guān)系：設(shè)集合間存在雙射，使得邊之間存在如下關(guān)系：設(shè)u1u2v1v2, u1,v1 V1, u2,v2 V2; u1v1 E1,當(dāng)且僅當(dāng)當(dāng)且僅

20、當(dāng)u2v2 E2,且且u1v1與與u2v2的重數(shù)相同。稱的重數(shù)相同。稱G1與與G2同構(gòu)，記為：同構(gòu)，記為： 由定義可以得到圖同構(gòu)的幾個必要條件：由定義可以得到圖同構(gòu)的幾個必要條件：(三三)、圖的同構(gòu)、圖的同構(gòu)12GG (1) 頂點(diǎn)數(shù)相同；頂點(diǎn)數(shù)相同；(2) 邊數(shù)相同；邊數(shù)相同；(3) 關(guān)聯(lián)邊數(shù)相同的頂點(diǎn)關(guān)聯(lián)邊數(shù)相同的頂點(diǎn)個數(shù)相同。個數(shù)相同。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 判定圖的同構(gòu)是很困難的，屬于判定圖的同構(gòu)是很困難的，屬于NP完全問題。對于規(guī)模完全問題。對于規(guī)模不大的兩個圖，判定其是否同構(gòu)，可以采用觀察加推證的不大的兩個圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。方法。 例例2 證明下面兩圖不同構(gòu)。證明下面兩圖不同構(gòu)