第五章圖論(一)

1、第五章第五章 圖論圖論v 圖論是一門古老的學(xué)科，有200多年的歷史 Euler是圖論之父，他用圖論的方法解決了哥尼斯褒七橋問題v 哥尼斯褒七橋問題 普魯士的哥尼斯堡鎮(zhèn)（現(xiàn)名加里寧格勒，屬于俄羅斯共和國）被普雷格爾河支流分成4 部分：河兩岸、河中心島、兩條支流之間的部分。在18 世紀有7 座橋連接這4部分。 鎮(zhèn)上的人們在周日里穿過鎮(zhèn)子進行長距離的散步。他們想弄明白是否可能從鎮(zhèn)里某個位置出發(fā)不重復(fù)地經(jīng)過所有橋并且返回出發(fā)點。 瑞士數(shù)學(xué)家列昂哈德歐拉解決了這個問題。他的解答在1736年發(fā)表，歐拉利用多重圖來研究這個問題，用頂點表示4個部分，用邊表示橋。圖論所研究的圖是抽象的圖，它是事物及其相互之間的

2、聯(lián)系的圖形表示，不是日常的地理位置，本質(zhì)上就是集合及其上的關(guān)系的圖形表示。（見第3章）所以，表示圖的圖形可以任意變形，只要不改變點之間的連接關(guān)系即可。5.1圖的定義圖的定義v 定義定義1 簡單圖（簡單無向圖）簡單圖（簡單無向圖） G=（V，E），V是頂點集頂點集，E是邊集邊集。V中的元素稱為頂點頂點，E中的元素稱為邊邊。不同的頂點組成的無序偶無序偶稱為邊v 例例 計算機網(wǎng)絡(luò)拓撲圖，用圖為計算機網(wǎng)絡(luò)建模v 定義定義2 多重圖多重圖 G=（V，E，f），V是頂點集頂點集，E是邊集邊集。f：Eu, v u,vV，uv （多）重邊、平行邊（多）重邊、平行邊：f值相同的邊v 例例 計算機網(wǎng)絡(luò)拓撲圖，用圖

3、為計算機網(wǎng)絡(luò)建模v 定義定義3 偽圖偽圖 G=（V，E，f），V是頂點集頂點集，E是邊集邊集。f：Eu, v u,vV 環(huán)環(huán)：f(e)=1v 例例 計算機網(wǎng)絡(luò)拓撲圖，用圖為計算機網(wǎng)絡(luò)建模v 偽圖多重圖簡單圖 v 定義定義4 有向圖（簡單有向圖）有向圖（簡單有向圖） G=（V，E），V是頂點集頂點集，E是邊集邊集。V中的元素稱為頂點頂點，E中的元素稱為邊邊。不同的頂點組成的有序偶有序偶稱為邊v 例例 用圖為電話網(wǎng)絡(luò)建模v 定義定義5 有向多重圖有向多重圖 G=（V，E，f），V是頂點集頂點集，E是邊集邊集。f：E(u, v) u,vV v 例例 計算機網(wǎng)絡(luò)拓撲圖，用圖為計算機網(wǎng)絡(luò)建模v 圖總結(jié)圖總結(jié) “圖圖”：總稱v 例例1. 用圖來為并發(fā)程序建模用圖來為并發(fā)程序建模 解：解：通過并發(fā)地執(zhí)行某些語句，計算機程序可以執(zhí)行得更快。重要的是避免執(zhí)行需要尚未執(zhí)行語句結(jié)果的語句。(接下頁)語句與前面語句的相關(guān)性可以表示成有向圖。用頂點表示每個語句，若在執(zhí)行完第一個頂點所表示的語句之前不能執(zhí)行第二個頂點所表示的語句，則從第一個頂點到第二個頂點有一條邊。這樣的圖稱為優(yōu)先圖。圖7-9顯示計算機程序和優(yōu)先圖。例如，該圖說明在執(zhí)行語句s1、s2和s3之前不能執(zhí)行語句s5。習(xí)題習(xí)題 1.判斷以下所示的圖是否簡單圖、