離散數(shù)學(xué)圖論第二講

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

跡：

邊不相同的路

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

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

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

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

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

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

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

定義7-2.5邊割集、割邊設(shè)無向圖G=〈V,E〉為連通的，若有邊集E1E，使得圖G刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構(gòu)成邊割集，則稱該邊為割邊(或橋)。橋: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強連通、單側(cè)連通、弱連通簡單有向圖G=〈V,E〉中，任意一對結(jié)點間，至少有一個結(jié)點到另一個結(jié)點是可達(dá)的，則稱這個圖為單側(cè)連通。如果對于圖G中的任意兩個結(jié)點兩者之間是互相可達(dá)的，則稱這個圖為強連通的。如果在圖G中略去方向，將它看成是無向圖，圖是連通的，則稱該有向圖為弱連通的。定義7