文庫發(fā)布：2023圖論1上傳

圖論

第一節(jié)課程概述參考書參考書《圖論引導(dǎo)》，DouglasB.West，機(jī)器工業(yè)出版社教學(xué)周歷圖的基本概念樹、生成樹、最優(yōu)樹、有序二元樹、追捕問題平面圖、Euler公式、灌木生長算法匹配理論、圖的因式分解著色問題、四色證明、Ramsey數(shù)Euler圖、Hamilton圖、郵遞員問題有向圖、強(qiáng)弱連通、循環(huán)賽最大流、2F算法、Dinic分層算法、網(wǎng)絡(luò)流連通度、邊數(shù)最少的k連通圖圖的線性空間與矩陣圖論中的NPC問題及算法分析習(xí)題課與考試考核方法書面作業(yè)及報(bào)告20%課外編程項(xiàng)目10%期末閉卷考試70%課程特點(diǎn)圖論是研究點(diǎn)與線的學(xué)問圖論是組合數(shù)學(xué)的一個(gè)分支圖論交叉運(yùn)用了拓?fù)鋵W(xué)、群論和數(shù)論圖論中的定理證明有的顯而易見、有的令人費(fèi)解圖論是一項(xiàng)強(qiáng)大而靈活的科學(xué)分析工具圖論是形式語言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)理論的數(shù)學(xué)基礎(chǔ)高速數(shù)字計(jì)算機(jī)

5樹3七橋問題歐拉

1游戲博弈問題

2四色猜想4七橋問題如何不重復(fù)的走完七座橋？七橋問題抽象9完全對(duì)偶圖網(wǎng)絡(luò)通訊旅行社航空公司連接游戲博弈問題數(shù)據(jù)結(jié)構(gòu)中的樹四色問題可否用四種顏色標(biāo)示所有的地圖？高速計(jì)算第一章圖圖的應(yīng)用

6圖的性質(zhì)3通路與回路4圖的基本概念1圖的表示、分類2圖的連通性5第一章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解1圖的概念特殊圖圖論的基本定理通路與回路圖的連通性3圖論的典型應(yīng)用

2圖的同構(gòu)圖的構(gòu)成與證明

圖的基本概念圖的定義考慮一張航線地圖，圖中用點(diǎn)表示城市，當(dāng)兩個(gè)城市間有直達(dá)航班時(shí)，就用一條線將相應(yīng)的點(diǎn)連接起來。這種航線地圖的一部分如下圖所示；長春北京成都武漢上海圖的基本概念

假設(shè)有4臺(tái)計(jì)算機(jī)，分別標(biāo)記為A、B、C和D，在計(jì)算機(jī)A和B、C和D以及B和C之間有信息流。這種情形可用下圖表示，通常稱這種圖為通信網(wǎng)絡(luò)；ACDB圖的基本概念

假設(shè)有一群人和一組工作，這群人中的某些人能夠做這組工作中的某些工作。例如，有3個(gè)人A、B和C，3件工作D、E和F，假設(shè)A只能做工作D,B能做工作E和F,C能做工作D和E。則這種情形可用下圖表示，其中，在人和這個(gè)人能夠做的工作之間畫有線。ACFDBE基本思想

用圖形表示一組對(duì)象，其中有些對(duì)象對(duì)是有聯(lián)系的。對(duì)于這種圖形，我們感興趣的只是有多少個(gè)點(diǎn)和哪些結(jié)點(diǎn)之間有線連接，至于連線的長短曲直和結(jié)點(diǎn)的位置卻無關(guān)緊要，只要求每一條線都起始于一個(gè)點(diǎn)，而終止于另一個(gè)點(diǎn)。圖的定義

一個(gè)圖(Graph)是一個(gè)序偶<V,E>，記為G=<V,E>，其中：（1）V={v1,v2,…,vn}是有限非空集合，vi稱為結(jié)點(diǎn)(NodalPoint)，簡(jiǎn)稱點(diǎn)(Point)，V稱為結(jié)點(diǎn)集(NodalSet)。（2）E是有限集合，稱為邊集(FrontierSet)。E中的每個(gè)元素都有V中的結(jié)點(diǎn)對(duì)與之對(duì)應(yīng)，稱之為邊(Edge)。圖的表示形式化：對(duì)于一個(gè)圖G，如果將其記為G=<V,E>，并寫出V和E的集合表示稱為圖的集合表示。圖形化：用小圓圈表示V中的結(jié)點(diǎn)，用由u指向v的有向線段表示有向邊<u,v>無向線段表示無向邊(u,v)，稱為圖的圖形表示。圖論的艱苦從許多實(shí)例中，我們發(fā)現(xiàn)圖論最吸引人的特色是它蘊(yùn)含著大量強(qiáng)有力的思想、漂亮的圖形和巧妙的論證，即使是非常困難的尚未解決的問題也易于表達(dá)。問題外表的簡(jiǎn)單樸素和本質(zhì)上的難以解決，使每個(gè)搞圖論的人在圖論面前必須謹(jǐn)慎嚴(yán)肅地思考問題。常常是貌似簡(jiǎn)單的問題，即使幸運(yùn)地得出證明，證明中包含的細(xì)節(jié)也十分之繁瑣，并且往往運(yùn)用了極艱苦的計(jì)算。鉆石與足球烯足球烯應(yīng)用在超導(dǎo)、太陽能電池、護(hù)膚品數(shù)學(xué)領(lǐng)先其他科學(xué)100年妖怪（snark）妖怪圖每個(gè)點(diǎn)都關(guān)聯(lián)著3條邊，用4種顏色可以把每條邊涂上顏色，使得有公共端點(diǎn)的邊異色，而用3種顏色辦不到，切斷任意3條邊不會(huì)使它斷裂成2個(gè)有邊的圖。單星妖怪雙星妖怪更多妖怪Hamilton旅行游戲貨郎擔(dān)問題TSP（TravelingSalesmanProblem）假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。NPC問題Ramsey定理在一群人數(shù)不少于三的人群中，若任意兩人都剛好只有一個(gè)共同認(rèn)識(shí)的人，這群人中總有一人是所有人都認(rèn)識(shí)的。對(duì)于所有的N頂圖，包含k個(gè)頂?shù)膱F(tuán)或q個(gè)頂?shù)莫?dú)立集。具有這樣性質(zhì)的最小自然數(shù)N就稱為一個(gè)拉姆齊數(shù)，記作R(k,q)萊昂哈德·歐拉(LeonhardEuler)

瑞士的數(shù)學(xué)家和物理學(xué)家。他被稱為歷史上最偉大的兩位數(shù)學(xué)家之一（另一位是卡爾·弗里德里克·高斯）。歐拉出生于瑞士，在那里受教育。他是一位數(shù)學(xué)神童。作為數(shù)學(xué)教授，他先后任教于圣彼得堡(1727-1741)和柏林，爾后再返圣彼得堡(1766)。歐拉的離世也很特別：據(jù)說當(dāng)時(shí)正是下午茶時(shí)間，正在逗孫兒玩的時(shí)候，被一塊蛋糕卡在喉頭窒息而死。歐拉是第一個(gè)使用“函數(shù)”一詞來描述包含各種參數(shù)的表達(dá)式的人，例如：y=F(x)(函數(shù)的定義由萊布尼茲在1694年給出)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。歐拉是有史以來最多產(chǎn)的數(shù)學(xué)家，他的全集共計(jì)75卷。歐拉實(shí)際上支配了18世紀(jì)的數(shù)學(xué)，對(duì)于當(dāng)時(shí)新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還是以驚人的速度產(chǎn)出了生平一半的著作。小行星歐拉2002是為了紀(jì)念歐拉而命名的。Euler卡爾·弗里德里?！じ咚垢咚鼓芡暾乇吵鰣A周率——是倒著背。

高斯口渴時(shí)會(huì)用塔斯基悖論弄出更多橙汁。

高斯不能理解隨機(jī)過程，因?yàn)樗茴A(yù)測(cè)隨機(jī)數(shù)高斯小時(shí)候，老師讓他算從1到100的和。他計(jì)算了這個(gè)無窮級(jí)數(shù)的和，然后一個(gè)一個(gè)地減去從100開始的所用自然數(shù)。而且，是心算。

一位數(shù)學(xué)家、一位物理學(xué)家、一位工程師走進(jìn)酒吧，酒吧招待說：“您好，高斯教授?！?/p>

詢問高斯一個(gè)命題是真的還是假的，構(gòu)成了一個(gè)嚴(yán)格的證明。有一次高斯證明了一條公理，但他不喜歡它，所以他又證明了它是假命題。高斯通過在證明結(jié)束時(shí)省去“QED”來保護(hù)熱帶雨林。有一次高斯在森林里迷路了，于是他加了幾條邊把它變成了一棵樹。高斯用奧卡姆剃刀剃胡子。圖論第一節(jié)課圖的表示有序與無序

定義中的結(jié)點(diǎn)對(duì)即可以是無序的，也可以是有序的。ACFDBE

若邊e與無序結(jié)點(diǎn)對(duì)(u,v)相對(duì)應(yīng)，則稱e為無向邊(UndirectedEdge)，記為e=(u,v)=(v,u)，這時(shí)稱u、v是邊e的兩個(gè)端點(diǎn)(Endpoint)。若邊e與有序結(jié)點(diǎn)對(duì)<u,v>相對(duì)應(yīng)，則稱e為有向邊(DirectedPoint)(或弧)，記為e=<u,v>，這時(shí)稱u為e的始點(diǎn)(InitialPoint)(或弧尾)，v為e的終點(diǎn)(terminalPoint)(或弧頭)，統(tǒng)稱為e的端點(diǎn)。例題

設(shè)圖G=<V,E>，這里V={v1,v2,v3,v4,v5}，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)。試畫出圖G的圖形，并指出哪些是有向邊，哪些是無向邊？解G的圖形如下圖所示。G中的e1、e3、e4、e6是無向邊，e2、e5是有向邊。v3e1e2e3e5v2v1v4e4v5e6例題設(shè)圖G=<V,E>的圖形如下圖所示，試寫出G的集合表示。12345解圖G的