離散數(shù)學(xué)圖概念路與回路

關(guān)于離散數(shù)學(xué)圖概念路與回路1第1頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五第七章圖論圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門學(xué)科。本章主要講授圖論的基本概念和定理。圖論：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)要求：熟練掌握圖的基本概念和定理并能夠進(jìn)行簡單應(yīng)用。第2頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五7-1圖的基本概念本節(jié)要熟悉下列概念（26個(gè)）：圖、無向邊、有向邊、起始結(jié)點(diǎn)、終止結(jié)點(diǎn)、無向圖、有向圖、混合圖、鄰接點(diǎn)、鄰接邊、孤立結(jié)點(diǎn)、零圖、平凡圖、結(jié)點(diǎn)的度數(shù)、圖的最大度、最小度、結(jié)點(diǎn)的入度、結(jié)點(diǎn)的出度、平行邊、簡單圖、完全圖、補(bǔ)圖、子圖、生成子圖、子圖的相對于圖的補(bǔ)圖、圖的同構(gòu)多重圖、第3頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五圖的定義點(diǎn)的度數(shù)特殊的圖圖同構(gòu)7-1圖的基本概念第4頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五一、圖的定義

定義7-1.1

圖（graph）G由一個(gè)三元組<V(G),E(G),G>表示，其中：

非空集合V(G)={v1,v2,…,vr}

稱為圖G的結(jié)點(diǎn)集，其成員vi(i=1,2,…,r)稱為結(jié)點(diǎn)或頂點(diǎn)（nodes

orvertices）；

集合E(G)={e1,e2,…,es}

稱為圖G的邊集，其成員ej(j=1,2,…s)稱為邊(edges)。函數(shù)G

：E(G)→(V(G),V(G))

，稱為邊與頂點(diǎn)的關(guān)聯(lián)映射（associatvemapping）

第5頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五例1：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)abcde1e2e3e4e5e6

若把圖中的邊ej看作總是和兩個(gè)結(jié)點(diǎn)關(guān)聯(lián)，那么一個(gè)圖亦簡記為G=<V,E>

，其中非空集合V稱為圖G的結(jié)點(diǎn)集，集合E稱為圖G的邊集。若邊ej與結(jié)點(diǎn)無序偶(vj,vk)關(guān)聯(lián)，那么稱該邊為無向邊。若邊ej與結(jié)點(diǎn)序偶<vj,vk>關(guān)聯(lián)，那么稱該邊為有向邊。起始結(jié)點(diǎn)終止結(jié)點(diǎn)第6頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五例2：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)一個(gè)圖與結(jié)點(diǎn)、連接結(jié)點(diǎn)的邊、邊與結(jié)點(diǎn)的關(guān)聯(lián)有關(guān)。第7頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五2、有向邊&無向邊無向邊：如果E中邊ei對應(yīng)V中的結(jié)點(diǎn)對是無序的(u，v)稱ei是無向邊，記ei=(u，v)，稱u，v是ei的兩個(gè)端點(diǎn)。有向邊：如果ei與結(jié)點(diǎn)有序?qū)?lt;u，v>相對應(yīng)，稱ei是有向邊，記ei=<u，v>，稱u為ei的始點(diǎn)，v為ei的終點(diǎn)。第8頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五3、圖的分類：①無向圖：每條邊均為無向邊的圖稱為無向圖。②有向圖：每條邊均為有向邊的圖稱為有向圖。③混合圖：有些邊是無向邊，有些邊是有向邊的圖稱為混合圖。V1’v1v4v5v1v2v3v4V2’V3’V4’(a)無向圖(b)有向圖(c)混合圖(孤立點(diǎn))v2v3環(huán)第9頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五1、G1=<V1，E1>是無向圖，其中V1={V1，V2，V3，V4，V5，V6}，E1={e1，e2，e3，e4，e5，e6}，e1=(V1，V3)，e2=(V1，V4)，e2=(V2，V4)，e3=(V3，V4)，e4=(V3，V6)，e5=(V4，V5)，e6=(V5，V6)3、G3=<V3，e3>是混合圖，V3={V1，V2，V3，V4}，E3={<V1，V1>，(V1，V3)，<V3，V1>，<V1，V2>，(V4，V2)}2、G2=<V2，E2>是有向圖，其中V2={V1，V2，V3，V4}，E={<V3，V1>，<V3，V2>，<V1，V1>，<V1，V2>，<V4，V1>，<V3，V4>，<V4，V3>}練習(xí)：畫出下面的圖。第10頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五4、點(diǎn)和邊的關(guān)聯(lián)：如ei=(u，v)或ei=<u，v>稱u，v與ei關(guān)聯(lián)。5、點(diǎn)與點(diǎn)的相鄰：關(guān)聯(lián)于同一條邊的結(jié)點(diǎn)稱為鄰接點(diǎn)。6、邊與邊的鄰接：關(guān)聯(lián)于同一結(jié)點(diǎn)的邊稱為鄰接邊。7、孤立結(jié)點(diǎn)：不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)。8、零圖：僅有孤立結(jié)點(diǎn)的圖。9、平凡圖：僅有一個(gè)孤立結(jié)點(diǎn)的圖。第11頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五10、自回路(環(huán))：關(guān)聯(lián)于同一結(jié)點(diǎn)的邊稱為自回路，或稱為環(huán)。11、平行邊：在有向圖中，始點(diǎn)和終點(diǎn)均相同的邊稱為平行邊，無向圖中若兩點(diǎn)間有多條邊，稱這些邊為平行邊，兩點(diǎn)間平行邊的條數(shù)稱為邊的重?cái)?shù)。第12頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五圖的定義點(diǎn)的度數(shù)特殊的圖圖同構(gòu)7-1圖的基本概念第13頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五二、點(diǎn)的度數(shù)1、點(diǎn)的度數(shù)的定義定義7-1.2：在圖G=<V，E>，vV，與結(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為該點(diǎn)的度數(shù)，記為deg(v)。孤立結(jié)點(diǎn)的度數(shù)為0。2、出度與入度定義7-1.3：在有向圖中，vV，以v為始點(diǎn)的邊數(shù)稱為該結(jié)點(diǎn)的出度，記作deg+(v);以v為終點(diǎn)的邊數(shù)稱為該結(jié)點(diǎn)的入度，記作deg-(v)。顯然有deg(v)=deg+(v)+deg-(v)第14頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五如：G1是無向圖，deg(v1)=3，deg(v2)=1G2是有向圖，deg+(v1)=3，deg-(v1)=2，deg(v1)=5，v1v2G1v1v3v4v2G2第15頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五3、最大度和最小度：圖G最大度記為(G)=max{deg(v)|vV(G)}，最小度數(shù)記為(G)=min{deg(v)|vV(G)}。4、定理7-1.1：每個(gè)圖中，結(jié)點(diǎn)度數(shù)總和等于邊數(shù)的兩倍。即deg(v)=2|E|

vV

該定理又稱握手定理證明因?yàn)槊織l邊必關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)，而一條邊給予關(guān)聯(lián)的每個(gè)結(jié)點(diǎn)的度數(shù)為1。因此在每個(gè)圖中，結(jié)點(diǎn)度數(shù)總和等于邊數(shù)的兩倍。第16頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五5、定理7-1.2

在任何圖中,度數(shù)為奇數(shù)的結(jié)點(diǎn)必定是偶數(shù)個(gè)。證明：設(shè)G中奇數(shù)度結(jié)點(diǎn)集合為V1,偶數(shù)度結(jié)點(diǎn)集合為V2，則有：deg(v)+deg(v)=deg(v)=2|E|vV1vV2vV由于deg(v)是偶數(shù)之和必為偶數(shù)，而2|E|是偶數(shù)，

vV2故得deg(v)是偶數(shù)，而各個(gè)deg(vi)(viV1

)是奇數(shù)，

vV1這就要求偶數(shù)個(gè)deg(vi)求和，即|V1|是偶數(shù)。第17頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五6、定理7-1.3：在任何有向圖中，所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)的出度之和，且均等于邊數(shù)。證明因?yàn)槊恳粭l有向邊必對應(yīng)一個(gè)入度和一個(gè)出度，若一個(gè)結(jié)點(diǎn)具有一個(gè)入度或出度，則必關(guān)聯(lián)一條有向邊，所以有向圖中，各結(jié)點(diǎn)入度之和等于邊數(shù)，各結(jié)點(diǎn)出度之和也等于邊數(shù)。因此，在任何有向圖中，所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)的出度之和。第18頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五圖的定義點(diǎn)的度數(shù)特殊的圖圖同構(gòu)7-1圖的基本概念第19頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五三、特殊的圖1、多重圖定義7-1.4：含有平行邊的圖稱為多重圖。2、簡單圖：不含平行邊和環(huán)的圖稱為簡單圖。3、完全圖定義7-1.5：簡單圖G=<V，E>中，若每一對結(jié)點(diǎn)間均有邊相連，則稱該圖為完全圖。有n個(gè)結(jié)點(diǎn)的無向完全圖記為Kn。無向完全圖：每一條邊都是無向邊不含有平行邊和環(huán)每一對結(jié)點(diǎn)間都有邊相連第20頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五如果在Kn中，對每一條邊任意確定一個(gè)方向，則稱該圖為n個(gè)結(jié)點(diǎn)的有向完全圖。顯然它的邊數(shù)為n(n-1)/2。

定理7-1.4

在任何圖中,n個(gè)結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為n(n-1)/2。證明：n個(gè)結(jié)點(diǎn)中任取兩個(gè)結(jié)點(diǎn)的組合數(shù)為

Cn2=

n(n-1)/2故的邊數(shù)為

|E|=n(n-1)/2第21頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五5、相對于完全圖的補(bǔ)圖定義7-1.6：給定一個(gè)簡單圖G，由G中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成的圖，稱為G的相對于完全圖的補(bǔ)圖，或簡稱為G的補(bǔ)圖，記為G。即G=<V，E1>，G=<V，E2>，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖K5(b)圖G(c)圖G的補(bǔ)圖G’第22頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五6、子圖定義7-1.7：設(shè)圖G=<V，E>，如果有圖G’=<V’，E’>，且E’E，V’V，則稱G’為G的子圖。當(dāng)V’=V時(shí)，則稱G’為G的生成子圖。例如，下圖，圖(b)的G和圖(c)的G’

都是圖(a)的K5的子圖。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖K5(b)圖G(c)圖G的補(bǔ)圖G’第23頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五7、相對于圖G的補(bǔ)圖定義7-1.8：設(shè)G’=<V’，E’>是G=<V，E>的子圖，若給定另一個(gè)圖G”=<V”，E”>使得E”=E-E’，且V”中僅包含E”的邊所關(guān)聯(lián)的結(jié)點(diǎn)，則稱G”是子圖G’相對于圖G的補(bǔ)圖。例如，上圖(b)的G是圖(c)的G’

相對于圖(a)的K5的補(bǔ)圖。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖K5(b)圖G(c)圖G的補(bǔ)圖G’第24頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五圖的定義點(diǎn)的度數(shù)特殊的圖圖同構(gòu)7-1圖的基本概念第25頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五四、同構(gòu)定義7-1.9：設(shè)圖G=<V，E>及圖G’=<V’，E’>，如果存在一一對應(yīng)的映射g：VV’且e=(vi，vj)(或<vi，vj>)是G的一條邊，當(dāng)且僅當(dāng)e’=(g(vi)，g(vj))(或<g(vi)，g(vj)>)是G’的一條邊，則稱G與G’同構(gòu)，記作G≌G’。第26頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五兩圖同構(gòu)的一些必要條件：1.結(jié)點(diǎn)數(shù)目相同；2.邊數(shù)相等；3.度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。以上幾個(gè)條件不是兩個(gè)圖同構(gòu)的充分條件。見279頁圖7-1.10同構(gòu)必須是結(jié)點(diǎn)和邊分別存在一一對應(yīng)。第27頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五28作業(yè)279頁:(5)（6）第28頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五7-2路與回路

在現(xiàn)實(shí)世界中，常常要考慮這樣的問題：如何從一個(gè)圖中的給定結(jié)點(diǎn)出發(fā)，沿著一些邊連續(xù)移動(dòng)而達(dá)到另一指定結(jié)點(diǎn)，這種依次由點(diǎn)和邊組成的序列，就形成了路的概念。第29頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(22個(gè))：路、路的長度、跡、回路、通路、圈、連通、連通分支、點(diǎn)割集、連通圖、割點(diǎn)、點(diǎn)連通度、邊割集、邊連通度、割邊、可達(dá)、單側(cè)連通、強(qiáng)連通、強(qiáng)分圖、弱連通、弱分圖、單側(cè)分圖掌握5個(gè)定理，一個(gè)推論。第30頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五路無向圖的連通性有向圖的連通性7-2路與回路第31頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五一、路

定義7-2.1

給定圖G=<V,E>,設(shè)v0,v1,…,vnV，e1,…,enE,其中ei是關(guān)聯(lián)于結(jié)點(diǎn)vi-1,vi的邊，交替序列v0e1v1e2…envn稱為結(jié)點(diǎn)v0到vn的路（path）

。v0和vn分別稱為路的起點(diǎn)和終點(diǎn)，邊的數(shù)目n稱作路的長度。當(dāng)v0=vn時(shí)，這條路稱作回路。若一條路中所有的邊e1,…,en均不相同,稱作跡。若一條路中所有的結(jié)點(diǎn)v0,v1,…,vn均不相同,稱作通路。閉的通路,即除v0=vn之外,其余結(jié)點(diǎn)均不相同的路,稱作圈。第32頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3跡：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2第33頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五在簡單圖中一條路v0e1v1e2…envn，由它的結(jié)點(diǎn)序列v0，v1，…，vn確定，所以簡單圖的路，可由其結(jié)點(diǎn)序列表示。在有向圖中，結(jié)點(diǎn)數(shù)大于1的一條路亦可由邊序列e1e2…en表示。第34頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五

定理7-2.1

在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路。證明思路：多于n-1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過n-1條邊。第35頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五

定理7-2.1的證明如果從結(jié)點(diǎn)vj到vk存在一條路，該路上的結(jié)點(diǎn)序列是vj…vi…vk，如果在這條中有l(wèi)條邊，則序列中必有l(wèi)+1個(gè)結(jié)點(diǎn)，若l>n-1，則必有結(jié)點(diǎn)vs，它在序列中不止出現(xiàn)一次，即必有結(jié)點(diǎn)序列vj…vs…vs…vk，在路中去掉從vs到vs的這些邊，仍是vj到vk的一條路，但此路比原來的路邊數(shù)要少，如此重復(fù)進(jìn)行下去，必可得到一條從vj到vk的不多于n-1條邊的路。第36頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五

定理7-2.1

在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路。

推論在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條邊數(shù)小于n的通路。第37頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五如在圖7-2.1中有5個(gè)結(jié)點(diǎn)。v1到v3的一條路為：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有6條邊，去掉e3有路v1e2v3e4v2e6v5e7v3有4條邊。v1到v3最短的路為v1e2v3第38頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五路無向圖的連通性有向圖的連通性7-2路與回路第39頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五二、無向圖的連通性：1、連通

定義7-2.2

在無向圖G中，如果從結(jié)點(diǎn)u和結(jié)點(diǎn)v之間若存在一條路，則稱結(jié)點(diǎn)u和結(jié)點(diǎn)v是連通的（connected）。

結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集V上的等價(jià)關(guān)系，對應(yīng)該等價(jià)關(guān)系，必可將作出一個(gè)劃分，把V分成非空子集V1,V2,…,Vm,使得兩個(gè)結(jié)點(diǎn)vj和vk是連通的，當(dāng)且僅當(dāng)它們屬于同一個(gè)Vi

。把子圖G(V1),G(V2),…,G(Vm)稱為圖G的連通分支（connectedcomponents）,圖G的連通分支數(shù)記為W(G)

。第40頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五41第41頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五2、連通圖定義7-2.3：若圖G只有一個(gè)連通分支，則稱G是連通圖。顯然在連通圖中，任意兩個(gè)結(jié)點(diǎn)之間必是連通的。第42頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五對于連通圖，常常由于刪除了圖中的點(diǎn)或邊，而影響了圖的連通性。刪除結(jié)點(diǎn)：所謂在圖中刪除結(jié)點(diǎn)v，即是把v以及與v關(guān)聯(lián)的邊都刪除。刪除邊：所謂在圖中刪除某條邊，即是把該邊刪除。v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e第43頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五3、割點(diǎn)定義7-2.4設(shè)無向圖G=<V,E>是連通圖,若有結(jié)點(diǎn)集V1V,使圖G中刪除了V1的所有結(jié)點(diǎn)后,所得到的子圖是不連通圖,而刪除了V1的任何真子集后,所得到的子圖仍是連通圖,則稱V1是G的一個(gè)點(diǎn)割集(cut-set

ofnodes)。若某一個(gè)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱該點(diǎn)為割點(diǎn)。sabcdabcdba第44頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五點(diǎn)連通度：是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目，也稱為連通度，記為k(G)。即k(G)=min{|V1||V1是G的點(diǎn)割集}稱為圖G的點(diǎn)連通度(1)若G是平凡圖，則V1=，k(G)=0(2)k(Kn)=n-1(3)若圖存在割點(diǎn)，則k(G)=1(4)規(guī)定非連通圖的連通度k(G)=0v5v1v2v3v4v5v1v3v4點(diǎn)割集V1={v2}第45頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五4、割邊定義7-2.5設(shè)無向圖G=<V,E>是連通圖,若有邊集E1E，使圖

G中刪除了E1的所有邊后，所得到的子圖是不連通圖，而刪除了E1的任何真子集后，所得到的子圖仍是連通圖，則稱E1是G的一個(gè)邊割集(cut-setof

edges)。若某一條邊就構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。割邊e使圖G滿足W(G-e)>W(G)

。第46頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五

邊連通度(edge-connectivity)

(G)定義：非平凡圖的邊連通度為

(G)=min{|E1||E1是G的邊割集}邊連通度

(G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目。(1)若G是平凡圖則E1=，(G)=0(2)若G存在割邊，則(G)=1，(3)規(guī)定非連通圖的邊連通度為(G)=0第47頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五5、定理7-2.2對于任何一個(gè)圖G,有k(G)≤(G)≤δ(G)

。在7-2.2節(jié)定義了圖的最小度：

δ(G)=min(deg(v)，vV)

下面的定理給出了點(diǎn)連通度k(G)、邊連通度(G)和圖的最小度(G)之間的關(guān)系。282頁圖7-2.3(a)k(G)=1,(G)=1,(G)=2282頁圖7-2.4k(G)=1,(G)=2,(G)=2第48頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五證明：若G不連通，則k(G)=(G)=0，故上式成立。若G連通，可分兩步證明上式也成立：

1)先證明(G)≤(G)：如果G是平凡圖，則(G)=0≤(G)，若G是非平凡圖，則因每一結(jié)點(diǎn)的所有關(guān)聯(lián)邊必含一個(gè)邊割集，(因(G)=min{deg(v)|vV}，設(shè)uV使的deg(u)=δ(G)，與u相關(guān)聯(lián)的條邊必包含一個(gè)邊割集，至少這條邊刪除使圖不連通。)故(G)≤(G)。5、定理7-2.2對于任何一個(gè)圖G,有

k(G)≤(G)≤δ(G)

。第49頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五2)再證k(G)≤(G)：(a)設(shè)(G)=1，即G有一割邊，顯然這時(shí)k(G)=l，上式成立。(b)設(shè)(G)≥2，則必可刪去某(G)條邊，使G不連通，而刪去其中(G)-1條邊，它仍是連通的，且有一條橋e=(u，v)。對(G)-1條邊中的每一條邊都選取一個(gè)不同于u，v的端點(diǎn)，把這些端點(diǎn)刪去則必至少刪去(G)-1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤(G)-1<(G)，若這樣產(chǎn)生的圖是連通的，則e仍是橋，此時(shí)再刪去u或v就必產(chǎn)生一個(gè)不連通圖，故k(G)≤(G)。由1)和2)得k(G)≤(G)≤(G)。第50頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五6.定理7-2.3一個(gè)連通無向圖G的結(jié)點(diǎn)v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和w,使得結(jié)點(diǎn)u和w的每一條路都通過v

。證明思路：1)先證:v是割點(diǎn)存在結(jié)點(diǎn)u和w的每條路都通過v

若v是連通圖G=<V,E>割點(diǎn)，設(shè)刪去v得到的子圖G’,則G’至少包含兩個(gè)連通分支G1=<V1,E1>和G2=<V2,E2>

。任取uV1，wV2，因?yàn)镚是連通的，故在G中必有一條連結(jié)u和w的路C，但u和w在G’中屬于兩個(gè)不同的連通分支，故u和w必不連通，因此C必須通過v，故u和w之間的任意一條路都通過v

。

2)再證:存在結(jié)點(diǎn)u和w的每條路都通過v

v是割點(diǎn)若連通圖G中的某兩個(gè)結(jié)點(diǎn)的每一條路都通過v，則刪去v得到子圖G’

，在G’中這兩個(gè)結(jié)點(diǎn)必然不連通，故v是圖G的割點(diǎn)。第51頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五路無向圖的連通性有向圖的連通性7-2路與回路第52頁，共60頁，2022年，5月20日，14點(diǎn)52分，星期五三、有向圖的連通性：1、可達(dá)：在無向圖G中，從結(jié)點(diǎn)u到v若存在一條路，則稱結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的。有向圖的可達(dá)性：對于任何一個(gè)有向圖G=<V,E>,從結(jié)點(diǎn)u和到結(jié)點(diǎn)v有一條路,稱為從u可達(dá)v?？蛇_(dá)性(accesible),是結(jié)點(diǎn)集上的二元關(guān)系，它是自反的和傳遞的，但是一般來說不是對稱的。故可達(dá)性不是等價(jià)關(guān)系。第53頁，共60頁，2022年，5月20