圖論基礎(chǔ)與計(jì)劃編制方法課件

1、第11章 圖論基礎(chǔ)與計(jì)劃編制方法111 圖論基礎(chǔ)112 工程項(xiàng)目計(jì)劃的橫道圖表示法113 網(wǎng)絡(luò)計(jì)劃技術(shù)的概念及其表示114 網(wǎng)絡(luò)計(jì)劃的優(yōu)化第11章 圖論基礎(chǔ)與計(jì)劃編制方法111 圖論基礎(chǔ)1111 圖論基礎(chǔ)111 圖論基礎(chǔ)基礎(chǔ)知識(shí)1、圖的基本概念 引例1公路網(wǎng) 有6個(gè)城鎮(zhèn)A、B、C、D、E、F，它們之間有公路直通的情況是：（A，B）、（A，C）、（A，E）、（A，F(xiàn)）、（B，C）、（B，D）、（D，F(xiàn)）、（E，F(xiàn)）. 試將它們的關(guān)系用圖表示出來(lái). 分析 我們把6個(gè)城鎮(zhèn)A、B、C、D、E、F分別用點(diǎn)表示. 若兩城鎮(zhèn)之間有公路直通，則用線(xiàn)相連結(jié)，否則不連結(jié)，可得到右圖，即為所作的關(guān)系圖. ABCDE

2、F基礎(chǔ)知識(shí)1、圖的基本概念 引例1公路網(wǎng) 把A、B、C、D、E、F對(duì)應(yīng)的點(diǎn)看成一個(gè)集合，“線(xiàn)”是這個(gè)集合中“點(diǎn)”之間的關(guān)系，那么，圖論正是研究像這樣的有限集合及其關(guān)系的一門(mén)數(shù)學(xué)科學(xué). 在這里，“線(xiàn)”是不論其曲直形狀的，通常稱(chēng)為邊，“點(diǎn)”是不論其上下位置的，通常稱(chēng)為結(jié)點(diǎn). 由這樣的結(jié)點(diǎn)和邊構(gòu)成的整體，就叫做圖. A、B兩點(diǎn)有線(xiàn)相連，稱(chēng)A和B是鄰接的點(diǎn)；而連線(xiàn)稱(chēng)為與A、B兩點(diǎn)相關(guān)聯(lián)的邊，記作(A,B). 結(jié)點(diǎn)鄰接點(diǎn)相關(guān)聯(lián)的邊ABCDEF把A、B、C、D、E、F對(duì)應(yīng)的點(diǎn)看成一個(gè)集合，“線(xiàn)”是這個(gè)集 若圖中一邊的兩個(gè)相關(guān)聯(lián)的結(jié)點(diǎn)相同，則稱(chēng)為環(huán). 若圖中兩邊具有相同的一對(duì)結(jié)點(diǎn)，則稱(chēng)為平行邊. 沒(méi)有環(huán)和平

3、行邊的圖稱(chēng)為簡(jiǎn)單圖. ABCDEF環(huán)平行邊討論：以上兩圖中哪一個(gè)為簡(jiǎn)單圖？ABCDEF 若圖中一邊的兩個(gè)相關(guān)聯(lián)的結(jié)點(diǎn)相同，則稱(chēng)為環(huán). 這里的圖與平面幾何里的圖形是不相同的. 這里的圖只考慮結(jié)點(diǎn)、邊以及邊與結(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，因此當(dāng)兩個(gè)圖的形狀看似不同，但若它們的結(jié)點(diǎn)集、邊集及邊與結(jié)點(diǎn)的關(guān)聯(lián)關(guān)系都相同時(shí)，則可將它們看作同一個(gè)圖. 這時(shí)，稱(chēng)這兩個(gè)圖是同構(gòu)的. 同構(gòu)點(diǎn)與點(diǎn)1-1對(duì)應(yīng)，線(xiàn)與線(xiàn)1-1對(duì)應(yīng) 這里的圖與平面幾何里的圖形是不相同的. 這里與A點(diǎn)關(guān)聯(lián)的所有邊的條數(shù)稱(chēng)為A點(diǎn)的次數(shù)，記作degA. ABCDEF孤立點(diǎn)次數(shù)為零的結(jié)點(diǎn)稱(chēng)為孤立點(diǎn). ABCDEFdegA=4，degB=degF=3，degC=

4、degD=degE=2.例：求圖中各點(diǎn)的次數(shù)問(wèn)：下圖中F點(diǎn)的次數(shù)是多少？與A點(diǎn)關(guān)聯(lián)的所有邊的條數(shù)稱(chēng)為A點(diǎn)的次數(shù)，記作degA. AB定理1 任一圖中點(diǎn)的次數(shù)之和等于邊數(shù)的兩倍. 定理2 任一圖中次數(shù)為奇數(shù)的點(diǎn)的個(gè)數(shù)必為偶數(shù). 討論：圖中點(diǎn)的次數(shù)與邊數(shù)有何聯(lián)系？ABCDEF定理1 任一圖中點(diǎn)的次數(shù)之和等于邊數(shù)的兩倍. 討論：圖中點(diǎn) 引例2程序調(diào)用 有4個(gè)程序 ，它們的調(diào)用關(guān)系是： 能調(diào)用 ； 能調(diào)用 ， 能調(diào)用 . 試將它們的關(guān)系用圖表示出來(lái). 分析 將4個(gè)程序分別用點(diǎn)來(lái)表示. 由于調(diào)用是有順序的，因此它們之間的調(diào)用關(guān)系用一條有方向的線(xiàn)相連結(jié)，得到下圖，即為所作的關(guān)系圖. p1p2p3p4 圖中

5、的邊帶有方向，通常稱(chēng)為有向邊. 若一個(gè)圖中所有邊均是有向邊，則稱(chēng)這圖為有向圖. 若一個(gè)圖中所有邊均是無(wú)向邊，則稱(chēng)這圖為無(wú)向圖. 引例2程序調(diào)用 有4個(gè)程序 引例3輸油管網(wǎng)絡(luò) 有5個(gè)城市A、B、C、D、E，它們之間有輸油管相連（A，B），（A，C），（A，E），（B，C），（C，D）. 而這些油管的長(zhǎng)度分別為：100km，120km，60km，80km，90km. 試將它們的關(guān)系用圖表示出來(lái).ABCDE 分析 我們把5個(gè)城市A、B、C、D、E分別用點(diǎn)表示. 若兩城市之間有輸油管相聯(lián)，則用線(xiàn)連結(jié)，否則不連結(jié). 為了表示里程數(shù)，將各輸油管長(zhǎng)度標(biāo)在相應(yīng)的邊上，可得到右圖，即為所作的關(guān)系圖. 10080

6、9060120 引例3輸油管網(wǎng)絡(luò) 有5個(gè)城市A、B、C、D、EABCDE100809060120 若一個(gè)圖的每條邊均附有數(shù)量信息，則這圖稱(chēng)為賦權(quán)圖，而附加的數(shù)量信息稱(chēng)為相應(yīng)邊的權(quán)數(shù). 賦權(quán)圖ABCDE100809060120 若一個(gè)圖的ABCDEF111320.50.5 例1 某產(chǎn)品的生產(chǎn)流程為：第一車(chē)間和第二車(chē)間都從原材料庫(kù)領(lǐng)取原材料，用時(shí)都為1h；第一車(chē)間加工后的半成品送到第二車(chē)間，用時(shí)3 h；經(jīng)第二車(chē)間加工后部分送到總裝車(chē)間，用時(shí)0.5 h，部分送到第三車(chē)間再加工，用時(shí)2 h，然后再送到總車(chē)間總裝，用時(shí)0. 5 h；經(jīng)總裝后的成品送入成品庫(kù)，用時(shí)1 h. 試將這一流程用圖表示. ABCD

7、EF111320.50.5 例1 某產(chǎn)品的生2連通圖看右邊圖：v1v2v3v4v5v1v2v3v4 這種由首尾連結(jié)的邊構(gòu)成的序列叫做圖的通路. 通路中的邊數(shù)叫做通路的長(zhǎng)度. 將通路中的結(jié)點(diǎn)依次排成的序列來(lái)表示這條通路，其第一個(gè)點(diǎn)為通路的起點(diǎn)，最后一個(gè)點(diǎn)為通路的終點(diǎn). 討論：圖中的下面幾條通路有何特點(diǎn)，長(zhǎng)度為多少？v1v2v3v4v5, v1v2v4v5, v2v3v4v2, v3v4v2v32連通圖看右邊圖：v1v2v3v4v5v1v2v3v4 起點(diǎn)與終點(diǎn)相同的通路稱(chēng)為圖的回路. 任意兩點(diǎn)之間均有通路的圖稱(chēng)為連通圖. v1v2v3v4v5連通圖起點(diǎn)與終點(diǎn)相同的通路稱(chēng)為圖的回路. 任意兩點(diǎn)之間均

8、有通路的圖ABCDE100809060120討論：下圖是否為連通圖？ABCDEF賦權(quán)連通圖稱(chēng)為網(wǎng)絡(luò). ABCDE100809060120討論：下圖是否為連通圖？A下面研究一類(lèi)特殊的連通圖歐拉圖。ABCD問(wèn)：一筆可以畫(huà)出下面的圖嗎？ABFDCDE 若一個(gè)圖中存在經(jīng)過(guò)每一條邊一次且僅一次的通路，則此路稱(chēng)為歐拉通路。 若一個(gè)圖中存在經(jīng)過(guò)每一條邊一次且僅一次的回路，則此回路稱(chēng)為歐拉回路. 具有歐拉回路的圖稱(chēng)為歐拉圖. 下面研究一類(lèi)特殊的連通圖歐拉圖。ABCD問(wèn)：一筆可以畫(huà)出問(wèn)：如何判定一個(gè)圖為歐拉圖呢？ 定理3 無(wú)向連通圖中結(jié)點(diǎn)vi和vj間存在歐拉通路的充分必要條件是vi和vj的次數(shù)均為奇數(shù)，而其他結(jié)

9、點(diǎn)的次數(shù)均為偶數(shù). 定理4 無(wú)向連通圖是歐拉圖的充要條件是每個(gè)結(jié)點(diǎn)的次數(shù)均為偶數(shù).問(wèn)：如何判定一個(gè)圖為歐拉圖呢？ 定理3 無(wú)向ABFDCDE例：判斷下面的圖是否為歐拉圖？ABDCEABFDCDE例：判斷下面的圖是否為歐拉圖？ABDCE3樹(shù) 定義 若一個(gè)圖是連通的，且不包含回路，則這樣的圖稱(chēng)為樹(shù). 例3 試判斷圖中哪些是樹(shù)，哪些不是樹(shù)，并說(shuō)明理由. AAACBEDCBEDCBED（1）（2）（3）不連通有回路 在圖3中，若去掉邊CE，則可得到圖2. 因此，圖2可看作是由圖3的一部分（稱(chēng)為子圖）構(gòu)成的樹(shù)，稱(chēng)為生成樹(shù). 3樹(shù) 定義 若一個(gè)圖是連通的，且不包含回路小結(jié)：1、圖的基本概念（1）圖；（2）

10、簡(jiǎn)單圖；（3）有向圖，無(wú)向圖；（4）賦權(quán)圖。2、連通圖（1）通路，回路；（2）連通圖；（3）網(wǎng)絡(luò)；（4）歐拉通路，歐拉回路，歐拉圖。3、樹(shù)（1）樹(shù)；（2）生成樹(shù)。小結(jié)：1、圖的基本概念2、連通圖3、樹(shù)應(yīng)用案例 案例1灑水路線(xiàn) 某城市街道如圖所示. 灑水車(chē)從A點(diǎn)出發(fā)，執(zhí)行灑水任務(wù). 問(wèn)：是否存在一條灑水路徑，使灑水車(chē)從A點(diǎn)出發(fā)通過(guò)所有街道且不重復(fù)而最后回到車(chē)庫(kù)B？ ABFGCDEFACDEFBGCFGA歐拉回路應(yīng)用案例 案例1灑水路線(xiàn) 某城市街道如圖所示. 案例2（七橋問(wèn)題） 哥尼斯堡城的居民有郊游的習(xí)慣. 在城郊的普雷格爾河畔，河中有兩個(gè)小島C、D，七座橋?qū)蓚€(gè)小島與河岸A、B連接（見(jiàn)圖）.

11、問(wèn)是否存在這樣的游玩路徑：從A、B、C、D中任一地出發(fā)，不重復(fù)走遍七座橋，再回到原出發(fā)地？答：這樣的路線(xiàn)不存在。ADBC 案例2（七橋問(wèn)題） 哥尼斯堡城的居民有郊游 案例3（保衛(wèi)油網(wǎng)） 設(shè)有6個(gè)城市A、B、C、E、F、G，它們間有輸油管連通，其分布如圖所示（圖中的數(shù)字表示油管的長(zhǎng)度）. 為了保衛(wèi)油管不受破壞，在每段油管間需派一連士兵看守. 問(wèn)：至少需派多少連士兵，他們應(yīng)駐在哪些油管處？ABCDEF25411222443 案例3（保衛(wèi)油網(wǎng)） 設(shè)有6個(gè)城市A、B、C（2）將原圖所有邊刪去，保留所有結(jié)點(diǎn). （3）按表中的次序?qū)⑦吋尤雸D中.（4）如出現(xiàn)回路，則刪去權(quán)為最大的邊，即得最短樹(shù). 解：尋找最短生成樹(shù)問(wèn)題。（1）將所有邊排序：邊ACCDABCEBDEFDFADEDCFBC權(quán)11222234445ABCDEF25411222443（2）將原圖所有邊刪去，保留所有結(jié)點(diǎn). （3）按表中的次序?qū)BCDEFFABCDE2112ABCDE