運(yùn)籌學(xué)11-圖與網(wǎng)絡(luò).ppt

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