離散數學圖論第二講_第1頁
離散數學圖論第二講_第2頁
離散數學圖論第二講_第3頁
離散數學圖論第二講_第4頁
離散數學圖論第二講_第5頁
已閱讀5頁，還剩7頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

例5Z6={0,1,2,3,4,5},分別為模6乘法

跡：

邊不相同的路

閉跡：起點=終點通路：點不相同的路

圈：起點=終點cae2e1be3e5ede4be2ce1ae1ce3de4de5eae1ce3de4de5eae1ce3de4e路：回路：起點=終點思考：兩條不同路是怎樣的思考：通路一定是跡嗎定理7-2.1在一個具有n個結點的圖中，如果從結點vj到結點vk存在一條路(vkvj)

，則從結點vj到結點vk必存在一條不多于n-1條邊的路。推論在具有n個結點的圈中，若從結點vj到結點vk存在一條路，則必存在一條從結點vj到結點vk邊數小于n的通路。定義7-2.2連通在無向圖G中，結點u和v之間若存在一條路，則結點u和v稱為是連通的。abcdefgh

R={<x,y>|x與y連通}思考:R是什么關系并寫出A/R連通分支：圖G=〈V，E〉可以分解為若干個連通分支Gi=〈Vi，Ei〉(i=1，2，…，k)，G的連通分支數用W(G)來表示。d(u,v)：兩點的距離是從u到v的最短路的長度。cae2e1be3e5ede1e2e3e4e5e6e7dabc[定義]連通圖

若圖G=〈V,E〉的任意兩個結點皆有路連通，則G稱為連通圖。

cae2e1be3e5ede1e2e3e4e5e6e7dabc思考：連通圖有幾個連通分支？定義7-2.4點割集和割點設無向圖G=〈V,E〉為連通的，若有結點集V1V，使得圖G刪除了V1所有結點后，所得的子圖是不連通的，而刪除了V1的任意真子集后，所得的子圖仍然是連通圖。則稱集合V1為圖G的點割集。若某一結點就構成點割集，則稱該結點為割點。

e,f點割集:{e},{f},割點:{c,d}

定義7-2.5邊割集、割邊設無向圖G=〈V,E〉為連通的，若有邊集E1E，使得圖G刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構成邊割集，則稱該邊為割邊(或橋)。橋:e8,e9邊割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}定理7-2.4對于任何一個圖G=〈V,E〉，有k(G)≤λ(G)≤δ(G)例如(G)=3(G)=3定義7-2.6強連通、單側連通、弱連通簡單有向圖G=〈V,E〉中，任意一對結點間，至少有一個結點到另一個結點是可達的，則稱這個圖為單側連通。如果對于圖G中的任意兩個結點兩者之間是互相可達的，則稱這個圖為強連通的。如果在圖G中略去方向，將它看成是無向圖，圖是連通的，則稱該有向圖為弱連通的。定義7

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論