管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)(已修改)
2025-01-21 05:27 本頁(yè)面
【正文】 第十八章 圖與網(wǎng)絡(luò) 德國(guó)古城 — 哥 尼斯堡 — 普雷格爾河 — 七 橋問(wèn)題：從任一橋頭出發(fā)，依次走過(guò)每一座 橋，每座橋只走一次，最后回到出發(fā)點(diǎn)。 —— 一筆畫問(wèn)題 2. 中國(guó)郵遞員問(wèn)題 郵遞員送信送報(bào)要走完全部所負(fù)責(zé)的街道，最后回到郵局，如何走路程最短？ 第一節(jié) 圖的基本概念 一、圖的概念 定義 圖是由點(diǎn)與邊組成的集合，記為 G=(V， E)，其中 V表示圖 G中點(diǎn)的集合，是一個(gè)非空集合，記為 V（ G），這些點(diǎn)稱為頂點(diǎn)， E表示圖 G中邊的集合，記為 E（ G）。 例 18— 1 圖 18— 4中的圖可表示為 G=（ V， E），其中 ? ?? ?987654321654321e,e,e,e,e,e,e,e,eEv,v,v,v,v,vV??定義 設(shè) G=（ V， E） （ 1）圖 G中含頂點(diǎn)的個(gè)數(shù)，記為 p（ G），稱 為圖 G的階；圖 G中含邊的條數(shù)，記為 q（ G），稱為圖的邊數(shù)。 （ 2）若 e=[u， v]∈E ，則稱 u， v是邊 e的端 點(diǎn)，稱 e為 u， v的關(guān)聯(lián)邊。 （ 3）若 u和 v是同一條邊相關(guān)聯(lián)，則稱 u和 v 是相鄰的，若邊 ei、 ej有公共的端點(diǎn)， 稱邊 ei和 ej是相鄰的。 （ 4）若 e的兩個(gè)端點(diǎn)重合，則稱 e為環(huán)。 （ 5）若兩點(diǎn)之間多于一條邊，稱之為多重邊。 （ 6）含多重邊的圖，稱為多重圖，無(wú)環(huán)也無(wú)多 重邊的圖，稱為簡(jiǎn)單圖。 （ 7）以頂點(diǎn) v為端點(diǎn)的邊的條數(shù)，稱為點(diǎn) v的 次（或稱度），記為 d（ v）。 （ 8）若 d（ v） =1，則稱 v為懸掛點(diǎn)，與懸掛點(diǎn) 相關(guān)聯(lián)的邊稱為懸掛邊。 （ 9）若 d（ v） =0，則稱 v為孤立點(diǎn)。 （ 10）若 d（ v） =奇數(shù)，則稱 v為奇點(diǎn)，若 d（ v） =偶數(shù)，則稱 v為偶點(diǎn)。 定理 1 在圖 G中，所有頂點(diǎn)次的和，等于邊數(shù)的兩倍。即 這是顯然的，因?yàn)樵谟?jì)算各點(diǎn)的次時(shí)，每條邊都用過(guò)兩次，所以，所有頂點(diǎn)次的和等于邊數(shù)的兩倍。 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 ???Vvq2)v(d二、圖的同構(gòu) 定義 設(shè)是兩個(gè)圖，如果頂點(diǎn)集合 V1與 V2之間以及邊的集合 E1與 E2之間都建立了一一對(duì)應(yīng)關(guān)系，并且圖形的兩頂點(diǎn)之間的邊對(duì)應(yīng)于另一圖形對(duì)應(yīng)頂點(diǎn)的邊，則稱圖 G1與圖 G2是同構(gòu)的。 同構(gòu)的圖被認(rèn)為是相同的。 三、子圖 定義 設(shè) ， 如果 ，則稱 G1是 G2的子圖。 應(yīng)當(dāng)指出，從圖 G2的頂點(diǎn)集合 V2中任選一些頂點(diǎn)，從圖 G2的邊集合 E2中任選一些邊，不一定就能組成G2的子圖 G1而只有當(dāng)所有被選入 G1的邊的端點(diǎn)也都被選入 G1時(shí)， G1才是 G2的子圖。并且： （ 1）若 ,則稱 G1是 G2的一個(gè)部分圖，例如圖 18— 6（ b）就是圖 18— 6（ a）的一個(gè)部分圖。 （ 2）若 ，則稱 G1是 G2的真子圖。例如圖 18— 6（ c）就是圖 18— 6（ a）的一個(gè)真子圖。 2121 EEVV ?? ，），， 222111 EV(G)EV(G ??2121 EEVV ?? ，2121 EEVV ?? ，第二節(jié) 連通圖 定義 設(shè)是一個(gè)圖， Q為 G中一個(gè)由部分頂點(diǎn)和邊交錯(cuò)組成的非空有限序列 其中 則稱 Q為從到的一條鏈，如果 Q中，而且與重合，則稱 Q為圈（或稱閉鏈）。如果鏈（圈） Q中含的邊均不相同，則稱 Q為簡(jiǎn)單鏈（圈）。如果鏈（圈） Q中含的邊與頂點(diǎn)均不相同，則稱 Q為初等鏈（圈）。 ? ?kk iiiiii veevevQ ，，， 12211 ?? ?），，（， 1k321r]vv[e 1rrr iii ??? ? ?定義 如果在圖中的任何兩個(gè)頂點(diǎn)之間都至少有一條連接這兩個(gè)頂點(diǎn)的鏈，則稱圖 G為連通圖，否則，稱 G為非連通圖。 一筆畫問(wèn)題 歐拉鏈：給定一個(gè)連通圖 G,若存在一條鏈，過(guò)每邊一次且僅一
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1