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