圖論基礎與計劃編制方法課件

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

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

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

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

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

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

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

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

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

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

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