圖與網(wǎng)絡(luò)ppt課件(已修改)
2025-05-24 07:51 本頁(yè)面
【正文】 第四章 圖與網(wǎng)絡(luò) 圖和網(wǎng)絡(luò) ? 圖論廣泛地應(yīng)用與物理學(xué)、化學(xué)、控制論、信息、科學(xué)管理、電子計(jì)算機(jī)等領(lǐng)域。很多實(shí)際問(wèn)題可以采用圖論的理論和方法來(lái)解決。 ? 圖論的歷史最早可以追溯到 1736年瑞士數(shù)學(xué)家 。 哥尼斯堡七橋問(wèn)題 ? 18世紀(jì)在哥尼斯堡城 (今俄羅斯加里寧格勒 )的普萊格爾河上有 7座橋，將河中的兩個(gè)島和河岸連結(jié)，如圖 1所示。 ? 城中的居民經(jīng)常沿河過(guò)橋散步，于是提出了一個(gè)問(wèn)題：能否一次走遍 7座橋，而每座橋只許通過(guò)一次，最后仍回到起始地點(diǎn)。這就是七橋問(wèn)題，一個(gè)著名的圖論問(wèn)題。 哥尼斯堡七橋問(wèn)題 圖與網(wǎng)絡(luò)的基本概念 V1 V2 V3 d e2 e3 e6 e4 e5 V4 V5 e1 V={v1, v2,v3,v4,v5} E={e1, e2,e3,e4,e5} G=(V,E) 端點(diǎn)；關(guān)聯(lián)邊 無(wú)向邊；有向邊（弧） 環(huán)（自回路） 多重邊 簡(jiǎn)單圖；多重圖 懸掛點(diǎn) 網(wǎng)絡(luò) 連通圖 ? 點(diǎn)邊序列；點(diǎn)邊交替序列； ? 在點(diǎn)邊交替系列中，順序排列的任意兩條邊均為相鄰邊，則稱(chēng)該點(diǎn)邊交替序列為鏈； ? 點(diǎn)邊列中沒(méi)有重復(fù)的點(diǎn)和重復(fù)邊者稱(chēng)為初等鏈 ? 圈（回路） V1 V2 V3 V4 V5 V6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 鏈、路 (1) 鏈、路 (2) v1 a1 v2 a2 v3 a7 v4 v5 a4 a3 a8 a9 ? 路：在一條鏈中，每條弧的方向與序列的走向一致，則稱(chēng)該鏈為路。 ? 回路：起點(diǎn)和終點(diǎn)重合與同一節(jié)點(diǎn)的路?；芈放c圈的區(qū)別是所有弧的方向一致。 圖、子圖、支撐子圖 樹(shù) ? 一個(gè)無(wú)圈的連通圖稱(chēng)為 樹(shù) 。 樹(shù) ? 例：五個(gè)城市之間架設(shè)電話(huà)線。要求任何兩個(gè)城市都可以相互通話(huà)（允許通過(guò)其他城市），并且電話(huà)線的根數(shù)最少。 V2 V1 V3 V4 V5 圖的基本概念小結(jié) ? 邊、弧 ? 無(wú)向圖、有向圖 – 無(wú)向圖 :(1)端點(diǎn)、相鄰、關(guān)聯(lián)邊 (2)環(huán)、多重邊、簡(jiǎn)單圖 (3)懸掛點(diǎn) (4)鏈、圈、初等鏈 (5)連通圖、支撐子圖 – 有向圖 :(1)始點(diǎn)、終點(diǎn) (2)路、回路 割集 v2 v1 v3 v4 v5 v6 a b c d e f g h k v1 v2 v6 v3 v4 v5 ? 在一個(gè)連通圖中割集是一些邊的集合，從 G中移去這些邊，則 G不連通，并且不存在這些邊的真子集使圖不連通 最短路問(wèn)題 ? 設(shè) G=(V,E)為連通圖，圖中各邊 (vi,vj)有權(quán) lij (lij=∞表示 vi,vj之間無(wú)邊 )， vs,vt為圖中任意兩點(diǎn)，求一條路 μ，使它是從 vs到 vt的所有路中總權(quán)數(shù)最小的路。 ( , )()ijijvvLl???? ?最短路問(wèn)題 1 2 3 4 3 4 5 6 3 2 3 4 2 2 1 Edsger Wybe Dijkstra ? 中文名： 艾茲格 迪科斯徹 ? 家鄉(xiāng)： 荷蘭 ? 出生年月： 1930年 5月 11日 ? 去世年月： 2022年 8月 6日 ? 成就： – 1972年獲得過(guò)素有計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)之稱(chēng)的圖靈獎(jiǎng) – 1989年 ACM SIGCSE計(jì)算機(jī)科學(xué)教育教學(xué)杰出貢獻(xiàn)獎(jiǎng) – 2022年 ACM PODC最具影響
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1