【正文】 點(diǎn) ， 即無(wú)圈和連通 ，加上最短的要求 ， 方法主要有兩種：一種稱為破圈法 ， 一種稱為生長(zhǎng)法 樹的概念回顧 一個(gè)沒(méi)有圈的圖稱為一個(gè) 無(wú)圈圖 或稱為 林 。 在實(shí)際應(yīng)用中 ， 經(jīng)常碰到需要求一個(gè)賦權(quán)連通圖的最短樹的問(wèn)題 。 網(wǎng)絡(luò) 賦權(quán)的圖 權(quán) 程度的度量 ， 數(shù)量描述 。 一個(gè)連通的無(wú)圈圖則稱為 樹 ，一個(gè)林的每個(gè)連通子圖都是一個(gè)樹。 若 T是圖 G的部分樹 ， 則從 G中去掉 T中所有的邊 ， 所得到的子圖稱為 G中的 T的 余樹 ， 也稱為 G的一個(gè)余樹 。 ⑥ 每一對(duì)頂點(diǎn)之間有一條且僅有一條鏈 。 ④ 無(wú)圈 ， 但若任意增加一條邊 ， 則可得到一個(gè)且僅一個(gè)圈 。 ② 無(wú)圈 ， q=p1。 一個(gè)連通的無(wú)圈圖則稱為 樹 ， 一個(gè)林的每個(gè)連通子圖都是一個(gè)樹 。 除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的回路稱為 初等回路 。 當(dāng)路的起點(diǎn)與終點(diǎn)相同，即 u=v時(shí)，稱作一條 回路 。 從頂點(diǎn) u指向 υ的弧 a， 記作＝ a=(u,v),(u,v)≠(v,u)， 其中u稱為 a的起點(diǎn)， v稱為 a的終點(diǎn)，這樣的圖稱為 有向圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 圖的概念 有向圖 在有些圖中，邊是沒(méi)有方向的，即 [u,v]=[v,u]， 這種圖稱為 無(wú)向圖 。 部分圖 若 V1=V2，E1?E2 ， 則稱 G1為G2的一個(gè) 部分圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 必須指出，并不是從圖G2中任選一些頂點(diǎn)和邊在一起就組成 G2的子圖G1， 而只有在 G2中的一條邊以及連接該邊的兩個(gè)端點(diǎn)均選入 G1時(shí)， G1才是 G2的子圖。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 連通的意義 連通是一個(gè)很重要的概念，如果一個(gè)問(wèn)題所對(duì)應(yīng)的圖是一個(gè)不連通圖，則該問(wèn)題一定可以分解成互不相關(guān)的子問(wèn)題來(lái)加以研究，即可以把不連通圖分解成連通的子圖來(lái)研究。 143746211 , ????? eeee 圖的概念 連通性 若一個(gè)圖 G的任意兩點(diǎn)之間均至少有一條通路（初等鏈）連接起來(lái)，則稱這個(gè)圖 G是一個(gè) 連通圖 ，否則稱作 不連通圖 。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的閉鏈，稱為 初等回路 或稱為 圈 。 例如圖中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 是一條鏈，且是開鏈，也是簡(jiǎn)單鏈，但不是初等鏈，因?yàn)?v1出現(xiàn)兩次。 nnn eee ????? , 122110 ??e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 簡(jiǎn)單鏈 若鏈中所含的邊均不相同，則稱為 簡(jiǎn)單鏈 ；若點(diǎn)均不相同，則稱為 初等鏈 或 通路 。 v0稱為鏈的 起點(diǎn) ， vn稱為鏈的 終點(diǎn) 。 設(shè) V1和 V2分別是圖 G中次數(shù)為奇數(shù)和偶數(shù)的頂點(diǎn)集合。 定理 1 所有頂點(diǎn)的次的和，等于所有邊數(shù)的 2倍。 圖 5－ 1中的點(diǎn) v5即為懸掛點(diǎn) ， 邊 e9即為懸掛邊 ，而點(diǎn) v6則是弧立點(diǎn) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 圖的次 次 點(diǎn) v作為邊的端點(diǎn)的次數(shù)，記作 d(v)， 如圖 5－1中， d(v1)=5, d(v4)=6等 端點(diǎn)次為奇數(shù)的點(diǎn)稱作 奇點(diǎn) ；次為偶數(shù)的點(diǎn)稱作偶點(diǎn) 。 含有多重邊的圖稱作 多重圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 簡(jiǎn)單圖 若一條邊的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn) ， 則稱該邊為環(huán) ；又若兩上端點(diǎn)之間有多于一條邊 ， 則稱為多重邊 或 平行邊 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 點(diǎn)邊關(guān)系 若點(diǎn) u和 v與同一條邊相關(guān)聯(lián) ， 則 u和 v為相鄰點(diǎn) ；若兩條邊ei和 ej有同一個(gè)端點(diǎn) ，則稱 ei與 ej為 相鄰邊 。 若 e=[u,v]∈ E， 則稱 u和 v為 e的 端點(diǎn) ，而稱 e為 u和 v的 關(guān)聯(lián)邊 ，也稱 u，v與邊 e相 關(guān)聯(lián) 。 圖的概念 圖的表示 ],[ 211 ???e ],[ 212 ???e ],[ 413 ?e ],[ 314e ],[315 ???e ],[ 426 ???e ],[ 437 ???e ,[ 448 ???e ],[ 549 ???e),(),( 987654321654321 eeeeeeeeeE ?? ???????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 點(diǎn)與邊 頂點(diǎn)數(shù) 集合 V中元素的個(gè)數(shù) ， 記作 p(G)。運(yùn)籌學(xué)第五章 圖與網(wǎng)絡(luò)理論 交大管理學(xué)院 楊民助 圖與網(wǎng)絡(luò)理論 圖的概念 網(wǎng)絡(luò)概念 網(wǎng)絡(luò)最短樹問(wèn)題 網(wǎng)絡(luò)最短路問(wèn)題 網(wǎng)絡(luò)最大流問(wèn)題 圖的概念 什么是圖 ? 圖的概念 ? 所謂圖，就是頂點(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è)圖相同。 邊數(shù) 集合 E中元素的個(gè)數(shù)，記作 q(G)。 例如圖 5－ 1中的圖 G，p(G)=6， q(G)=9， v1， v2是 e1和 e2的端點(diǎn)，e1和 e2都是 v1和 v2的關(guān)聯(lián)邊。 例如在圖 5－ 1中 v1和v2為相鄰點(diǎn)， v1和v5不相鄰； e1與 e5為相鄰邊， e1和 e7不相鄰。 例如圖 5－ 1的 e8為環(huán) ， e1，e2為兩重邊 ， e4， e5也是兩重邊 。 無(wú)環(huán)也無(wú)多重邊的圖稱作簡(jiǎn)單圖 。 次為 1的點(diǎn)稱為 懸掛點(diǎn) ，與懸掛點(diǎn)連接的邊稱作懸掛邊 ； 次為 0的點(diǎn)稱為 孤立點(diǎn) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 定理 1 若圖 G中所有點(diǎn)都是孤立點(diǎn)，則稱圖 G為 空?qǐng)D 。即 qdV2)( ?????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 定理 2 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。由定理 1有 qddVV2)()(21?? ???? ????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的概念 鏈 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為 鏈 。 若 v0 ≠vn則稱該鏈為 開鏈 ，反之稱為 閉鏈或 回路 。 除起點(diǎn)和終點(diǎn)外