圖與網(wǎng)絡(luò)（1）-全文預(yù)覽
【正文】 ?稱為圖的 三要素 。 解： 以每門課程為一個(gè)頂點(diǎn) ， 共同被選修的課程之間用邊相連 ， 得圖 ， 按題意 ，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試 ， 不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試 ， 因此 ，作圖的補(bǔ)圖 ， 問題是在圖中尋找一條哈密頓道路 ， 如 C— E— A— F— D— B， 就是一個(gè)符合要求的考試課程表 。 1 2 7 6 4 5 1 2 3 7 6 4 5 假定第二次就座方案是 （ 1， 3， 5， 7， 2， 4， 6， 1） ，那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 例 91： 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ） 是歐洲一個(gè)城市 ， Pregei河把該城分成兩部分 ， 河中有兩個(gè)小島 ， 十八世紀(jì)時(shí) ， 河兩邊及小島之間共有七座橋 ， 當(dāng)時(shí)人們提出這樣的問題：有沒有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過各橋一次且僅一次最后回到原地呢 ？ A B C D 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個(gè)問題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、 B、C、 D四塊陸地分別收縮成四個(gè)頂點(diǎn) ，把橋表示成連接對(duì)應(yīng)頂點(diǎn)之間的邊 ，問題轉(zhuǎn)化為從任意一點(diǎn)出發(fā) ， 能不能經(jīng)過各邊一次且僅一次 ， 最后返回該點(diǎn) 。 第二階段 是從十九世紀(jì)中葉到二十世紀(jì)中葉 ， 這時(shí) ， 圖論問題大量出現(xiàn) ， 如 Hamilton問題 ， 地圖染色的四色問題以及可平面性問題等 ， 這時(shí) ， 也出現(xiàn)用圖解決實(shí)際問題 ， 如 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹去研究電網(wǎng)絡(luò)等 . 第三階段 是二十世紀(jì)中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運(yùn)輸 、 計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問題 ， 以及大型計(jì)算機(jī)使大規(guī)模問題的求解成為可能 ， 特別是以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進(jìn)了圖論對(duì)實(shí)際問題的應(yīng)用 。 1 2 3 7 6 4 5 假定第一次就座方案是 （ 1， 2， 3， 4， 5， 6， 7， 1） ，那么第二次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 例 94： 一個(gè)班級(jí)的學(xué)生共計(jì)選修 A、B、 C、 D、 E、 F六門課程 ， 其中一部分人同時(shí)選修 D、 C、 A， 一部分人同時(shí)選修 B、 C、 F， 一部分人同時(shí)選修 B、E， 還有一部分人同時(shí)選修 A、 B， 期終考試要求每天考一門課 ， 六天內(nèi)考完 ， 為了減輕學(xué)生負(fù)擔(dān) ， 要求每人都不會(huì)連續(xù)參加考試 ， 試設(shè)計(jì)一個(gè)考試日程表 。 ?是描述邊與頂點(diǎn)之間關(guān)系的函數(shù) 稱 G=（ V， E， ?）為 一個(gè)圖，如果它滿足： （ 1） V非空； （ 2） E是一個(gè)不與 V 中頂點(diǎn)相交的邊集合； （ 3） ?是關(guān)聯(lián)函數(shù)。 定理 91：在一個(gè)圖中，所有頂點(diǎn)次的和等于邊的兩倍。 定義 ： 設(shè) G=（ V， E， ?）和 G1=（ V1， E1， ?1）。 定義（鏈）如果圖中的某些點(diǎn)、邊可以排列成點(diǎn)和邊的交錯(cuò)序列，則稱此為一條鏈。 v1 v2 v3 v4 2 5 6 4 3 4 v1 v2 v3 v4 v1 0 1 1 1 v2 1 1 1 0 v3 1 1 0 1 v4 1 0 1 0 無向圖的鄰接矩陣是對(duì)稱矩陣
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1