圖論及其應(yīng)用楊春全PPT課件

1、單擊此處添加標(biāo)題公司介紹丨品牌宣講LOGOLOGOBUSINESS ANALYSIS REPORT2圖論及其應(yīng)用 作者: 張先迪、李正良 購買地點(diǎn)：教材科第1頁/共854頁3參考文獻(xiàn)1 美，幫迪圖論及其應(yīng)用2 美，Gary Chartrand圖論導(dǎo)引，人民郵電出版社，20073 Bela Bollobas，現(xiàn)代圖論，科學(xué)出版社，2001 中國科學(xué)院研究生教學(xué)叢書4 美，F(xiàn)red Buckley圖論簡明教程，清華大學(xué)出版社，2005 李慧霸 王風(fēng)芹譯第2頁/共854頁45 李尉萱，圖論，湖南科學(xué)技術(shù)出版社，19796 美，Douglas B.West圖論導(dǎo)引，機(jī)械工業(yè)出版社，2007 李建中，駱

2、吉洲譯7 楊洪，圖論常用算法選編，中國鐵道出版社，19888 陳樹柏，網(wǎng)絡(luò)圖論及其應(yīng)用，科學(xué)出版社，1982第3頁/共854頁59 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界圖書出版公司北京公司，200410 王朝瑞，圖論，高等教育出版社，1983第4頁/共854頁6第一章 圖的基本概念本次課主要內(nèi)容圖的概念與圖論模型(一)、圖論課程簡介(二)、圖的定義與圖論模型(三)、圖的同構(gòu)第5頁/共854頁71、研究對象 圖論是研究點(diǎn)與線組成的“圖形”問題的一門科學(xué)。屬于應(yīng)用數(shù)學(xué)分支.(一)、圖論課程簡介2、發(fā)展歷史 圖論起源于18世紀(jì)的173

3、6年，標(biāo)志事件是“哥尼斯堡七橋問題.數(shù)學(xué)家歐拉被稱為“圖論之父”.20世紀(jì)30年代出版第一本圖論著作.第6頁/共854頁83、應(yīng)用狀況 圖論的應(yīng)用已經(jīng)涵蓋了人類學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)、環(huán)境保護(hù)、非線性物理、心理學(xué)、社會(huì)學(xué)、交通管理、電信以及數(shù)學(xué)本身等。 目前，圖論已形成很多分支：如隨機(jī)圖論、網(wǎng)絡(luò)圖論、代數(shù)圖論、拓?fù)鋱D論、極值圖論等。4、教學(xué)安排 主要介紹圖的一些基本概念、基本理論和圖論的典型應(yīng)用。60學(xué)時(shí)。第7頁/共854頁91、圖的定義(二)、圖的定義與圖論模型 一個(gè)圖是一個(gè)序偶，記為G=(V,E),其中：(1) V是一個(gè)有限的非空集合，稱為頂點(diǎn)集合,其元素稱為頂點(diǎn)或點(diǎn)。用|V|表示頂點(diǎn)數(shù)；(

4、2) E是由V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在E中可以重復(fù)出現(xiàn)多次。用|E|表示邊數(shù)。第8頁/共854頁10圖可以用圖形表示：V中的元素用平面上一個(gè)黑點(diǎn)表示，E中的元素用一條連接V中相應(yīng)點(diǎn)對的任意形狀的線表示。例1、設(shè)圖G。這里Vv1,v2,v3,v4Ee1,e2,e3,e4,e5,e6，e1(v1,v2)，e2(v1,v3)，e3(v1,v4)，e4(v2,v3)，e5(v3,v2)，e6(v3,v3)。v1v2v3v4e1e2e3e4e5e6第9頁/共854頁11圖的相關(guān)概念：有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；平凡圖：只有一個(gè)頂點(diǎn)的圖稱為平凡圖；空

5、圖：邊集為空的圖稱為空圖；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)；簡單圖：無環(huán)無重邊的圖稱為簡單圖；其余的圖稱為復(fù)合圖；第10頁/共854頁12頂點(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、圖論模型為了抽象和簡化現(xiàn)實(shí)世界，常建立數(shù)學(xué)模型。圖是關(guān)系的數(shù)學(xué)表示，為了深刻理解事物之間的聯(lián)系，圖是常用的數(shù)學(xué)模型。(1) 化學(xué)中的圖論模型19世紀(jì)，化學(xué)家凱萊用圖論研究簡單烴即碳?xì)浠衔锏?1頁/共854頁13用點(diǎn)抽象分