圖與網(wǎng)絡(luò)1(已修改)
2024-10-12 17:10 本頁(yè)面
【正文】 第九章 圖與網(wǎng)絡(luò) 引言 圖論是專門研究圖的理論的一門數(shù)學(xué)分支 ， 屬于離散數(shù)學(xué)范疇 ， 與運(yùn)籌學(xué)有交叉 ， 它有 200多年歷史 ，大體可劃分為 三個(gè)階段 ： 第一階段 是從十八世紀(jì)中葉到十九世紀(jì)中葉 ， 處于萌芽階段 ， 多數(shù)問(wèn)題圍游戲而產(chǎn)生 ， 最有代表性的工作是所謂的 Euler七橋問(wèn)題 ， 即一筆畫問(wèn)題 。 第二階段 是從十九世紀(jì)中葉到二十世紀(jì)中葉 ， 這時(shí) ， 圖論問(wèn)題大量出現(xiàn) ， 如 Hamilton問(wèn)題 ， 地圖染色的四色問(wèn)題以及可平面性問(wèn)題等 ， 這時(shí) ， 也出現(xiàn)用圖解決實(shí)際問(wèn)題 ， 如 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹去研究電網(wǎng)絡(luò)等 . 第三階段 是二十世紀(jì)中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運(yùn)輸 、 計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問(wèn)題 ， 以及大型計(jì)算機(jī)使大規(guī)模問(wèn)題的求解成為可能 ， 特別是以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進(jìn)了圖論對(duì)實(shí)際問(wèn)題的應(yīng)用 。 例 91： 哥尼斯堡七橋問(wèn)題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ） 是歐洲一個(gè)城市 ， Pregei河把該城分成兩部分 ， 河中有兩個(gè)小島 ， 十八世紀(jì)時(shí) ， 河兩邊及小島之間共有七座橋 ， 當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢 ？ A B C D 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個(gè)問(wèn)題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、 B、C、 D四塊陸地分別收縮成四個(gè)頂點(diǎn) ，把橋表示成連接對(duì)應(yīng)頂點(diǎn)之間的邊 ，問(wèn)題轉(zhuǎn)化為從任意一點(diǎn)出發(fā) ， 能不能經(jīng)過(guò)各邊一次且僅一次 ， 最后返回該點(diǎn) 。 這就是著名的 Euler問(wèn)題 。 A C B D 例 92： 有 7個(gè)人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問(wèn)不同的就座方案共有多少種 ？ 用頂點(diǎn)表示人 ， 用邊表示兩者相鄰 ， 因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰 ， 所以任何兩點(diǎn)都可以有邊相連 。 1 2 3 7 6 4 5 假定第一次就座方案是 （ 1， 2， 3， 4， 5， 6， 7， 1） ，那么第二次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 1 2 7 6 4 5 1 2 3 7 6 4 5 假定第二次就座方案是 （ 1， 3， 5， 7， 2， 4， 6， 1） ，那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 假定第三次就座方案是 （ 1， 4， 7， 3， 6， 2， 5， 1） ，那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 ， 只留下 7點(diǎn)孤立點(diǎn) ， 所以該問(wèn)題只有三個(gè)就座方案 。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 例 93： 哈密頓 （ Hamilton） 回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出 ， 給出一個(gè)正 12面體圖形 ，共有 20個(gè)頂點(diǎn)表示 20個(gè)城市 ，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過(guò)每條邊 ） 。 例 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
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1