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

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

跡：

邊不相同的路

閉跡：起點(diǎn)=終點(diǎn)通路：點(diǎn)不相同的路

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

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

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

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

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

e,f點(diǎn)割集:{e},{f},割點(diǎn):{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對(duì)于任何一個(gè)圖G=〈V,E〉，有k(G)≤λ(G)≤δ(G)例如(G)=3(G)=3定義7-2.6強(qiáng)連通、單側(cè)連通、弱連通簡單有向圖G=〈V,E〉中，任意一對(duì)結(jié)點(diǎn)間，至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱這個(gè)圖為單側(cè)連通。如果對(duì)于圖G中的任意兩個(gè)結(jié)點(diǎn)兩者之間是互相可達(dá)的，則稱這個(gè)圖為強(qiáng)連通的。如果在圖G中略去方向，將它看成是無向圖，圖是連通的，則稱該有向圖為弱連通的。定義7