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