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

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

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

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

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

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

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

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

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

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

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

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