第十一章圖與網(wǎng)絡規(guī)劃11.1圖與網(wǎng)絡的基本概念11.2樹及最小樹問題11.3最短路問題11.4網(wǎng)絡最大流問題11.1圖與網(wǎng)絡的基本概念圖的概念所謂圖，就是頂點和邊的集合，點的集合記為V，邊的集合記為E，則圖可以表示為：G（V，E），點代表被研究的事物，邊代表事物之間的聯(lián)系，因此，邊不能離開點而獨立存在，每條邊都有兩個端點。在畫圖時，頂點的位置、邊和長短形狀都是無關(guān)緊要的，只要兩個圖的頂點及邊是對應相同的，則兩個圖相同。圖的表示,211e,212e,413e,314e,315e,426e,437e,448e,549e),(),(987654321654321eeeeeeeeeEe1e2e3e4e5v2v3v1v4v5v6e6e7e8e9點與邊頂點數(shù)集合V中元素的個數(shù)，記作p(G)。邊數(shù)集合E中元素的個數(shù)，記作q(G)。若e=u,vE，則稱u和v為e的端點，而稱e為u和v的關(guān)聯(lián)邊，也稱u，v與邊e相關(guān)聯(lián)。例如圖中的圖G，p(G)=6，q(G)=9，v1，v2是e1和e2的端點，e1和e2都是v1和v2的關(guān)聯(lián)邊。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9點邊關(guān)系若點u和v與同一條邊相關(guān)聯(lián)，則u和v為相鄰點；若兩條邊ei和ej有同一個端點，則稱ei與ej為相鄰邊。例如在圖中v1和v2為相鄰點，v1和v5不相鄰；e1與e5為相鄰邊，e1和e7不相鄰。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9簡單圖若一條邊的兩個端點是同一個頂點，則稱該邊為環(huán)；又若兩上端點之間有多于一條邊，則稱為多重邊或平行邊。例如圖的e8為環(huán)，e1，e2為兩重邊，e4，e5也是兩重邊。含有多重邊的圖稱作多重圖。無環(huán)也無多重邊的圖稱作簡單圖。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9圖的次次點v作為邊的端點的次數(shù)，記作d(v)，如圖中，d(v1)=5,d(v4)=6等端點次為奇數(shù)的點稱作奇點；次為偶數(shù)的點稱作偶點。次為1的點稱為懸掛點，與懸掛點連接的邊稱作懸掛邊；次為0的點稱為孤立點。圖中的點v5即為懸掛點，邊e9即為懸掛邊，而點v6則是弧立點。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理若圖G中所有點都是孤立點，則稱圖G為空圖。定理1所有頂點的次的和，等于所有邊數(shù)的2倍。即qdV2)(e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理2在任一圖中，奇點的個數(shù)必為偶數(shù)。設V1和V2分別是圖G中次數(shù)為奇數(shù)和偶