離散數(shù)學(xué)第10章陳瑜課件

Email：yu3/16/2023離散數(shù)學(xué)計(jì)算機(jī)學(xué)院3/16/20231§10.1圖的基本概念3/16/20232計(jì)算機(jī)科學(xué)與工程學(xué)院主要內(nèi)容圖的基本概念什么是圖圖的分類結(jié)點(diǎn)的度數(shù)握手定理子圖與補(bǔ)圖完全圖補(bǔ)圖圖的同構(gòu)3/16/20233計(jì)算機(jī)科學(xué)與工程學(xué)院§10.1圖的基本概念無(wú)序積的定義：設(shè)A,B為任意集合，稱集合A&B＝{(a,b)|a∈A

，b∈B}為A與B的無(wú)序積，（a,b

）稱為無(wú)序?qū)?。與序偶不同，無(wú)論a,b是否相等，均有：

(a,b)＝(b,a)。

3/16/20235計(jì)算機(jī)科學(xué)與工程學(xué)院圖的定義定義10-1.1一個(gè)圖是一個(gè)序偶<V,E>，記為G＝<V,E>，其中：

1）V（G）＝{v1,v2,v3,…,vn}是一個(gè)有限的非空集合，vi(i＝1,2,3,…,n)稱為結(jié)點(diǎn),簡(jiǎn)稱點(diǎn)，V為結(jié)點(diǎn)集；

2）E（G）＝{e1,e2,e3,…,em}是一個(gè)有限的集合，ei(i＝1,2,3,…,m)稱為邊，E為邊集，E中的每個(gè)元素都是由V中不同結(jié)點(diǎn)所構(gòu)成的無(wú)序?qū)?，且不含重?fù)元素。3）圖G的結(jié)點(diǎn)數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m。

3/16/20236計(jì)算機(jī)科學(xué)與工程學(xué)院圖的定義定義10-1.1一個(gè)圖是一個(gè)序偶<V,E>，記為G＝<V,E>，其中：

1）V（G）＝{v1,v2,v3,…,vn}是一個(gè)有限的非空集合，vi(i＝1,2,3,…,n)稱為結(jié)點(diǎn),簡(jiǎn)稱點(diǎn)，V為結(jié)點(diǎn)集；

2）E（G）＝{e1,e2,e3,…,em}是一個(gè)有限的集合，ei(i＝1,2,3,…,m)稱為邊，E為邊集，E中的每個(gè)元素都是由V中不同結(jié)點(diǎn)所構(gòu)成的無(wú)序?qū)?，且不含重?fù)元素。

3）圖G的結(jié)點(diǎn)數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m。3/16/20237計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無(wú)序結(jié)點(diǎn)對(duì)(u，v)相對(duì)應(yīng)，則稱邊e為無(wú)向邊,記為e＝(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)；若邊e與有序結(jié)點(diǎn)對(duì)<u，v>相對(duì)應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時(shí)稱u是邊e的始點(diǎn)。v是邊e的終點(diǎn)，統(tǒng)稱為e的端點(diǎn)；e是u的出邊，是v的入邊。每條邊都是無(wú)向邊的圖稱為無(wú)向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無(wú)向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點(diǎn)，用由u指向v的有向線段表示<u,v>，無(wú)向線段表示(u,v)。3/16/20239計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無(wú)序結(jié)點(diǎn)對(duì)(u，v)相對(duì)應(yīng)，則稱邊e為無(wú)向邊,記為e＝(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)；若邊e與有序結(jié)點(diǎn)對(duì)<u，v>相對(duì)應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時(shí)稱u是邊e的始點(diǎn)。v是邊e的終點(diǎn)，統(tǒng)稱為e的端點(diǎn)；e是u的出邊，是v的入邊。每條邊都是無(wú)向邊的圖稱為無(wú)向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無(wú)向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點(diǎn)，用由u指向v的有向線段表示<u,v>，無(wú)向線段表示(u,v)。3/16/202310計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無(wú)序結(jié)點(diǎn)對(duì)(u，v)相對(duì)應(yīng)，則稱邊e為無(wú)向邊,記為e＝(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)；若邊e與有序結(jié)點(diǎn)對(duì)<u，v>相對(duì)應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時(shí)稱u是邊e的始點(diǎn)。v是邊e的終點(diǎn)，統(tǒng)稱為e的端點(diǎn)；e是u的出邊，是v的入邊。每條邊都是無(wú)向邊的圖稱為無(wú)向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無(wú)向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點(diǎn)，用由u指向v的有向線段表示<u,v>，無(wú)向線段表示(u,v)。3/16/202311計(jì)算機(jī)科學(xué)與工程學(xué)院幾個(gè)概念在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無(wú)論是有向的還是無(wú)向的，均稱邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點(diǎn)，否則稱為不鄰接的；關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的兩條邊稱為鄰接邊；圖中關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；僅由孤立結(jié)點(diǎn)組成的圖稱為零圖；僅含一個(gè)結(jié)點(diǎn)的零圖稱為平凡圖；含有n個(gè)結(jié)點(diǎn)、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v43/16/202313計(jì)算機(jī)科學(xué)與工程學(xué)院幾個(gè)概念在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無(wú)論是有向的還是無(wú)向的，均稱邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點(diǎn)，否則稱為不鄰接的；關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的兩條邊稱為鄰接邊；圖中關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；僅由孤立結(jié)點(diǎn)組成的圖稱為零圖；僅含一個(gè)結(jié)點(diǎn)的零圖稱為平凡圖；含有n個(gè)結(jié)點(diǎn)、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v43/16/202314計(jì)算機(jī)科學(xué)與工程學(xué)院幾個(gè)概念在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無(wú)論是有向的還是無(wú)向的，均稱邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點(diǎn)，否則稱為不鄰接的；關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的兩條邊稱為鄰接邊；圖中關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；僅由孤立結(jié)點(diǎn)組成的圖稱為零圖；僅含一個(gè)結(jié)點(diǎn)的零圖稱為平凡圖；含有n個(gè)結(jié)點(diǎn)、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v43/16/202315計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按邊的重?cái)?shù))在有向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有同始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱為平行邊。在無(wú)向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊的圖稱為多重圖；含有環(huán)的多重圖稱為廣義圖（偽圖）；滿足定義10-1.1的圖稱為簡(jiǎn)單圖。將多重圖和廣義圖中的平行邊代之以一條邊，去掉環(huán)，可以得到一個(gè)簡(jiǎn)單圖，稱為原來(lái)圖的基圖。3/16/202317計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按邊的重?cái)?shù))在有向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有同始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱為平行邊。在無(wú)向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊的圖稱為多重圖；含有環(huán)的多重圖稱為廣義圖（偽圖）；滿足定義10-1.1的圖稱為簡(jiǎn)單圖。將多重圖和廣義圖中的平行邊代之以一條邊，去掉環(huán)，可以得到一個(gè)簡(jiǎn)單圖，稱為原來(lái)圖的基圖。3/16/202318計(jì)算機(jī)科學(xué)與工程學(xué)院圖的分類(按權(quán))賦權(quán)圖G是一個(gè)三重組<V,E,g>，其中V是結(jié)點(diǎn)集合，E是邊的集合，g是邊E上的權(quán)值。非賦權(quán)圖稱為無(wú)權(quán)圖。v3v2v1v456678795G13/16/202319計(jì)算機(jī)科學(xué)與工程學(xué)院結(jié)點(diǎn)的度數(shù)

在無(wú)向圖G＝<V，E>中，與結(jié)點(diǎn)v(vV)關(guān)聯(lián)的邊的條數(shù)（有環(huán)時(shí)計(jì)算兩次），稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)；最大點(diǎn)度和最小點(diǎn)度分別記為和。在有向圖G＝<V，E>中，以結(jié)點(diǎn)v為始點(diǎn)引出的邊的條數(shù)，稱為該結(jié)點(diǎn)的出度,記為deg+(v)；以結(jié)點(diǎn)v為終點(diǎn)引入的邊的條數(shù)，稱為該結(jié)點(diǎn)的入度,記為deg-(v)；而結(jié)點(diǎn)的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)，即deg(v)＝deg+(v)+deg-(v)；3/16/202321計(jì)算機(jī)科學(xué)與工程學(xué)院對(duì)于圖G＝<V，E>，度數(shù)為0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖G=（V，）稱為零圖；只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖；在圖G＝<V，E>中，稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn)，度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。各點(diǎn)度數(shù)相等的圖稱為正則圖，特別將點(diǎn)度為k的正則圖稱為k度正則圖。3/16/202322計(jì)算機(jī)科學(xué)與工程學(xué)院對(duì)于圖G＝<V，E>，度數(shù)為0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖G=（V，）稱為零圖；只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖；在圖G＝<V，E>中，稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn)，度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。各點(diǎn)度數(shù)相等的圖稱為正則圖，特別將點(diǎn)度為k的正則圖稱為k度正則圖。3/16/202323計(jì)算機(jī)科學(xué)與工程學(xué)院例10.1deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝1，deg+(v4)＝0，deg-(v4)＝1；deg(v5)＝deg+(v5)＝deg-(v5)＝0；v3v2v1v5v43/16/202325計(jì)算機(jī)科學(xué)與工程學(xué)院例10.1deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝1，deg+(v4)＝0，deg-(v4)＝1；deg(v5)＝deg+(v5)＝deg-(v5)＝0；v3v2v1v5v43/16/202326計(jì)算機(jī)科學(xué)與工程學(xué)院例10.1deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝1，deg+(v4)＝0，deg-(v4)＝1；deg(v5)＝deg+(v5)＝deg-(v5)＝0；v3v2v1v5v43/16/202329計(jì)算機(jī)科學(xué)與工程學(xué)院握手定理（Euler,1736年）定理10-1.1（握手定理）對(duì)于任何（n,m）圖G=（V，E），所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：

證明：根據(jù)結(jié)點(diǎn)度數(shù)的定義，在計(jì)算結(jié)點(diǎn)度數(shù)時(shí)每條邊對(duì)于它所關(guān)聯(lián)的結(jié)點(diǎn)被計(jì)算了兩次，因此，G中結(jié)點(diǎn)度數(shù)的總和恰好為邊數(shù)m的2倍?！?/16/202330計(jì)算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。證明設(shè)V1＝{v|vV且deg(v)＝奇數(shù)}，V2＝{v|vV且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)?！?/16/202331計(jì)算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。證明設(shè)V1＝{v|vV且deg(v)＝奇數(shù)}，V2＝{v|vV且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)?！?/16/202332計(jì)算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。證明設(shè)V1＝{v|vV且deg(v)＝奇數(shù)}，V2＝{v|vV且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)?！?/16/202333計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-1.2：對(duì)于任何（n,m）有向圖G=（V，E），則所有結(jié)點(diǎn)的引出度數(shù)之和等于所有結(jié)點(diǎn)的引入度數(shù)之和，所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：證明：（略）。3/16/202334計(jì)算機(jī)科學(xué)與工程學(xué)院度數(shù)序列設(shè)V＝{v1,v2,…,vn}為圖G的結(jié)點(diǎn)集，稱(deg(v1),deg(v2),…,deg(vn))為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v43/16/202335計(jì)算機(jī)科學(xué)與工程學(xué)院度數(shù)序列設(shè)V＝{v1,v2,…,vn}為圖G的結(jié)點(diǎn)集，稱(deg(v1),deg(v2),…,deg(vn))為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v43/16/202336計(jì)算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2V1，E2E1，則稱H是G的子圖，記為HG。即V2V1或E2E1，則稱H是G的真子圖，記為HG。若V2=V1，則稱H是G的生成子圖。設(shè)V2=V1且E2=E1或E2=，則稱H是G的平凡子圖。設(shè)v是圖G的一個(gè)結(jié)點(diǎn)，從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點(diǎn)子圖，簡(jiǎn)記為G－v。3/16/202337計(jì)算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2V1，E2E1，則稱H是G的子圖，記為HG。即V2V1或E2E1，則稱H是G的真子圖，記為HG。若V2=V1，則稱H是G的生成子圖。設(shè)V2=V1且E2=E1或E2=，則稱H是G的平凡子圖。設(shè)v是圖G的一個(gè)結(jié)點(diǎn)，從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點(diǎn)子圖，簡(jiǎn)記為G－v。3/16/202338計(jì)算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2V1，E2E1，則稱H是G的子圖，記為HG。即V2V1或E2E1，則稱H是G的真子圖，記為HG。若V2=V1，則稱H是G的生成子圖。設(shè)V2=V1且E2=E1或E2=，則稱H是G的平凡子圖。設(shè)v是圖G的一個(gè)結(jié)點(diǎn)，從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點(diǎn)子圖，簡(jiǎn)記為G－v。3/16/202339計(jì)算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡(jiǎn)記為G－e。圖G＝<V，E>

，SV，則G(S)=(S，E′)是一個(gè)以S為結(jié)點(diǎn)，以E′={uv|u,vS,uvE}為邊集的圖，稱為G的點(diǎn)誘導(dǎo)子圖。圖G＝<V，E>

，TE且T≠，則G（T）是一個(gè)以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖，稱為G的邊誘導(dǎo)子圖。

3/16/202340計(jì)算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡(jiǎn)記為G－e。圖G＝<V，E>

，SV，則G(S)=(S，E′)是一個(gè)以S為結(jié)點(diǎn)，以E′={uv|u,vS,uvE}為邊集的圖，稱為G的點(diǎn)誘導(dǎo)子圖。圖G＝<V，E>

，TE且T≠，則G（T）是一個(gè)以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖，稱為G的邊誘導(dǎo)子圖。

3/16/202341計(jì)算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡(jiǎn)記為G－e。圖G＝<V，E>

，SV，則G(S)=(S，E′)是一個(gè)以S為結(jié)點(diǎn)，以E′={uv|u,vS,uvE}為邊集的圖，稱為G的點(diǎn)誘導(dǎo)子圖。圖G＝<V，E>

，TE且T≠，則G（T）是一個(gè)以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖，稱為G的邊誘導(dǎo)子圖。

3/16/202342計(jì)算機(jī)科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-{e1,e2}e3e2e1v2v1G3e3e2e1v2v1刪點(diǎn)子圖刪邊子圖點(diǎn)誘導(dǎo)子圖G3({v1,v2})邊誘導(dǎo)子圖G3({e1,e2,e3})例10.23/16/202343計(jì)算機(jī)科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-{e1,e2}e3e2e1v2v1G3e3e2e1v2v1刪點(diǎn)子圖刪邊子圖點(diǎn)誘導(dǎo)子圖G3({v1,v2})邊誘導(dǎo)子圖G3({e1,e2,e3})例10.23/16/202344計(jì)算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，如果G中任一個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)相鄰接，則稱G為無(wú)向完全圖，簡(jiǎn)稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單圖，若對(duì)于任意u,vV(uv)，既有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。

無(wú)向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為=n(n-1)。3/16/202345計(jì)算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，如果G中任一個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)相鄰接，則稱G為無(wú)向完全圖，簡(jiǎn)稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單圖，若對(duì)于任意u,vV(uv)，既有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。

無(wú)向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為=n(n-1)。3/16/202346計(jì)算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，如果G中任一個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)相鄰接，則稱G為無(wú)向完全圖，簡(jiǎn)稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個(gè)具有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單圖，若對(duì)于任意u,vV(uv)，既有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。

無(wú)向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為=n(n-1)。

3/16/202347計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)圖設(shè)G＝<V，E>為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,從完全圖Kn中刪去G中的所有邊而得到的圖稱為G相對(duì)于完全圖Kn的補(bǔ)圖，簡(jiǎn)稱G的補(bǔ)圖，記為

。這里，當(dāng)G為有向圖時(shí)，則Kn為有向完全圖；當(dāng)G為無(wú)向圖時(shí)，則Kn為無(wú)向完全圖。

顯然，G與互為補(bǔ)圖，即。

3/16/202348計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)圖設(shè)G＝<V，E>為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,從完全圖Kn中刪去G中的所有邊而得到的圖稱為G相對(duì)于完全圖Kn的補(bǔ)圖，簡(jiǎn)稱G的補(bǔ)圖，記為。這里，當(dāng)G為有向圖時(shí)，則Kn為有向完全圖；當(dāng)G為無(wú)向圖時(shí)，則Kn為無(wú)向完全圖。

顯然，G與互為補(bǔ)圖，即。

3/16/202349計(jì)算機(jī)科學(xué)與工程學(xué)院例10.33/16/202350計(jì)算機(jī)科學(xué)與工程學(xué)院二部圖設(shè)圖G=<V,E>，如果它的結(jié)點(diǎn)集可以劃分成兩個(gè)子集X和Y，使得它的每一條邊的一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在X中，另一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在Y中，則這樣的圖稱為二部圖。

設(shè)|X|=n1，|Y|=n2。如果X中的每一個(gè)結(jié)點(diǎn)與Y中的全部結(jié)點(diǎn)都鄰接，則稱G為完全二部圖，并記為Kn1,n2。3/16/202351計(jì)算機(jī)科學(xué)與工程學(xué)院二部圖

設(shè)圖G=<V,E>，如果它的結(jié)點(diǎn)集可以劃分成兩個(gè)子集X和Y，使得它的每一條邊的一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在X中，另一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在Y中，則這樣的圖稱為二部圖。

設(shè)|X|=n1，|Y|=n2。如果X中的每一個(gè)結(jié)點(diǎn)與Y中的全部結(jié)點(diǎn)都鄰接，則稱G為完全二部圖，并記為Kn1,n2。3/16/202352計(jì)算機(jī)科學(xué)與工程學(xué)院圖的同構(gòu)abcdabcdabcdabcd3/16/202353計(jì)算機(jī)科學(xué)與工程學(xué)院定義10-1.6設(shè)兩個(gè)圖G=<V,E>和G′=<V′,E′>，如果存在雙射函數(shù)g：V→V′，使得對(duì)于任意的e=(vi,vj)

（或者<vi,vj>）∈E當(dāng)且僅當(dāng)e′＝(g(vi),g(vj))

（或者<g(vi),g(vj)>）∈E′，則稱G與G′同構(gòu)，記為G≌G′。（同構(gòu)是指兩個(gè)圖的邊1-1對(duì)應(yīng)）圖的同構(gòu)關(guān)系是圖集上的等價(jià)關(guān)系。

3/16/202354計(jì)算機(jī)科學(xué)與工程學(xué)院定義10-1.6設(shè)兩個(gè)圖G=<V,E>和G′=<V′,E′>，如果存在雙射函數(shù)g：V→V′，使得對(duì)于任意的e=(vi,vj)

（或者<vi,vj>）∈E當(dāng)且僅當(dāng)e′＝(g(vi),g(vj))

（或者<g(vi),g(vj)>）∈E′，則稱G與G′同構(gòu)，記為G≌G′。（同構(gòu)是指兩個(gè)圖的邊1-1對(duì)應(yīng)）圖的同構(gòu)關(guān)系是圖集上的等價(jià)關(guān)系。

3/16/202355計(jì)算機(jī)科學(xué)與工程學(xué)院例10.4G1≌G2：a→v1，b→v2，c→v3，d→v4，e→v5abdcev4v1v3v2v5G1G2abdceG3G4v4v1v3v2v5G3≌G4：a→v1，b→v4，c→v2，d→v5，e→v3；3/16/202356計(jì)算機(jī)科學(xué)與工程學(xué)院例10.5G5≌G6：a→v1，b→v2，c→v3，d→v4，e→v7，f→v6，g→v9，h→v8，i→v5，j→v10abdcefgjhiG5G6v8v1v10v2v7v3v4v5v6v9彼得森圖3/16/202357計(jì)算機(jī)科學(xué)與工程學(xué)院兩個(gè)圖同構(gòu)的必要條件結(jié)點(diǎn)數(shù)目相同；邊數(shù)相同；度數(shù)相同的結(jié)點(diǎn)數(shù)相同。注意：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。3/16/202358計(jì)算機(jī)科學(xué)與工程學(xué)院兩個(gè)圖同構(gòu)的必要條件結(jié)點(diǎn)數(shù)目相同；邊數(shù)相同；度數(shù)相同的結(jié)點(diǎn)數(shù)相同。注意：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。yxuvxyvu3/16/202359計(jì)算機(jī)科學(xué)與工程學(xué)院兩個(gè)圖同構(gòu)的必要條件結(jié)點(diǎn)數(shù)目相同；邊數(shù)相同；度數(shù)相同的結(jié)點(diǎn)數(shù)相同。注意：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。yxuvxyvu

若圖的結(jié)點(diǎn)可以任意挪動(dòng)位置，而邊是完全彈性的，只要在不拉斷的條件下，一個(gè)圖可以變形為另一個(gè)圖，那么這兩個(gè)圖是同構(gòu)的。如下圖所示：

3/16/202360計(jì)算機(jī)科學(xué)與工程學(xué)院abcdabcdabdcefv1v2v3v4v5v6G7G8G7與G8不同構(gòu)為什么？例10.63/16/202361計(jì)算機(jī)科學(xué)與工程學(xué)院abcdabcdabdcefv1v2v3v4v5v6G7G8G7與G8不同構(gòu)為什么？例10.63/16/202362計(jì)算機(jī)科學(xué)與工程學(xué)院abcdabcdabdcefv1v2v3v4v5v6G7G8G7與G8不同構(gòu)為什么？例10.6這說(shuō)明上述三個(gè)條件僅僅是必要而不充分3/16/202363計(jì)算機(jī)科學(xué)與工程學(xué)院習(xí)題P2061、3(1)(4)、4、7、83/16/202364計(jì)算機(jī)科學(xué)與工程學(xué)院§10.2道路與回路3/16/202365計(jì)算機(jī)科學(xué)與工程學(xué)院§10.2道路與回路定義10-2.1

圖G＝<V,E>中結(jié)點(diǎn)和邊相繼交錯(cuò)出現(xiàn)的序列P=v0e1v1e2v2…ekvk，若P中邊ei的兩端點(diǎn)是vi-1和vi（G是有向圖時(shí)要求vi-1與vi分別是ei的始點(diǎn)和終點(diǎn)，即方向一致。），則稱P為結(jié)點(diǎn)v0到結(jié)點(diǎn)vk的道路。簡(jiǎn)記為〈v0，vk〉。v0和vk分別稱為此道路的起點(diǎn)和終點(diǎn)，統(tǒng)稱為道路的端點(diǎn)。其余結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。道路中邊的數(shù)目k稱為此道路的長(zhǎng)度。如P=v0，稱為零道路，其長(zhǎng)度為零。若v0≠vk，稱為開道路，否則稱為閉道路。3/16/202366計(jì)算機(jī)科學(xué)與工程學(xué)院§10.2道路與回路定義10-2.1

圖G＝<V,E>中結(jié)點(diǎn)和邊相繼交錯(cuò)出現(xiàn)的序列P=v0e1v1e2v2…ekvk，若P中邊ei的兩端點(diǎn)是vi-1和vi（G是有向圖時(shí)要求vi-1與vi分別是ei的始點(diǎn)和終點(diǎn)，即方向一致。），則稱P為結(jié)點(diǎn)v0到結(jié)點(diǎn)vk的道路。簡(jiǎn)記為〈v0，vk〉。v0和vk分別稱為此道路的起點(diǎn)和終點(diǎn)，統(tǒng)稱為道路的端點(diǎn)。其余結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。道路中邊的數(shù)目k稱為此道路的長(zhǎng)度。如P=v0，稱為零道路，其長(zhǎng)度為零。若v0≠vk，稱為開道路，否則稱為閉道路。3/16/202367計(jì)算機(jī)科學(xué)與工程學(xué)院簡(jiǎn)單道路與基本道路若道路中的所有邊e1，e2，…，ek（有向邊）互不相同，則稱此道路為簡(jiǎn)單道路；閉的簡(jiǎn)單道路稱為回路。若道路中的所有結(jié)點(diǎn)v0，v1，…，vk互不相同（從而所有邊互不相同），則稱此道路為基本道路；若回路中除v0＝vk外的所有結(jié)點(diǎn)v0，v1，…，vk-1互不相同（從而所有邊互不相同），則稱此回路為基本回路或者圈?；镜缆?或基本回路)一定是簡(jiǎn)單道路(或簡(jiǎn)單回路)，但反之則不一定。為什么？3/16/202368計(jì)算機(jī)科學(xué)與工程學(xué)院簡(jiǎn)單道路與基本道路若道路中的所有邊e1，e2，…，ek（有向邊）互不相同，則稱此道路為簡(jiǎn)單道路；閉的簡(jiǎn)單道路稱為回路。若道路中的所有結(jié)點(diǎn)v0，v1，…，vk互不相同（從而所有邊互不相同），則稱此道路為基本道路；若回路中除v0＝vk外的所有結(jié)點(diǎn)v0，v1，…，vk-1互不相同（從而所有邊互不相同），則稱此回路為基本回路或者圈。

基本道路(或基本回路)一定是簡(jiǎn)單道路(或簡(jiǎn)單回路)，但反之則不一定。為什么？3/16/202369計(jì)算機(jī)科學(xué)與工程學(xué)院簡(jiǎn)單道路與基本道路若道路中的所有邊e1，e2，…，ek（有向邊）互不相同，則稱此道路為簡(jiǎn)單道路；閉的簡(jiǎn)單道路稱為回路。若道路中的所有結(jié)點(diǎn)v0，v1，…，vk互不相同（從而所有邊互不相同），則稱此道路為基本道路；若回路中除v0＝vk外的所有結(jié)點(diǎn)v0，v1，…，vk-1互不相同（從而所有邊互不相同），則稱此回路為基本回路或者圈?；镜缆?或基本回路)一定是簡(jiǎn)單道路(或簡(jiǎn)單回路)，但反之則不一定。為什么？3/16/202370計(jì)算機(jī)科學(xué)與工程學(xué)院例10.7在圖G1中：v1e1v2e2v3e3v4e4v5e7v6：基本道路v1e1v2e5v4e3v3e2v2e9v6:簡(jiǎn)單道路V2e10v2e2v3e3v4e5v2:

回路V2e2v3e3v4e5v2:

圈e1v6v1v4v3v2G1e2e5e3e9e7e6e8v5e4v7e103/16/202371計(jì)算機(jī)科學(xué)與工程學(xué)院G2v4v1v3v2v5e1e2e3e4e5e7e8e6e9在圖G2中： v1e2v5e3v2e6v4e8v3e9v3e5v2e1v1：回路

v5e3v2e4v5：圈

3/16/202372計(jì)算機(jī)科學(xué)與工程學(xué)院注：在不會(huì)引起誤解的情況下，一條道路v0e1v1e2v2…envn也可以用邊的序列e1e2…en來(lái)表示，這種表示方法對(duì)于有向圖來(lái)說(shuō)較為方便。在簡(jiǎn)單圖中，一條道路v0e1v1e2v2…envn也可以用結(jié)點(diǎn)的序列v0v1v2…vn來(lái)表示。3/16/202373計(jì)算機(jī)科學(xué)與工程學(xué)院注：在不會(huì)引起誤解的情況下，一條道路v0e1v1e2v2…envn也可以用邊的序列e1e2…en來(lái)表示，這種表示方法對(duì)于有向圖來(lái)說(shuō)較為方便。在簡(jiǎn)單圖中，一條道路v0e1v1e2v2…envn也可以用結(jié)點(diǎn)的序列v0v1v2…vn來(lái)表示。3/16/202374計(jì)算機(jī)科學(xué)與工程學(xué)院道路圖和圈圖若一個(gè)圖能以一條基本道路表示出來(lái)，則稱此圖為道路圖。n階的道路圖記為Pn。若一個(gè)圖能以一個(gè)圈表示出來(lái)，則稱此圖為圈圖。n階的圈圖記為Cn。例10.12P5C63/16/202375計(jì)算機(jī)科學(xué)與工程學(xué)院道路圖和圈圖若一個(gè)圖能以一條基本道路表示出來(lái)，則稱此圖為道路圖。n階的道路圖記為Pn。若一個(gè)圖能以一個(gè)圈表示出來(lái)，則稱此圖為圈圖。n階的圈圖記為Cn。例10.12P5C63/16/202376計(jì)算機(jī)科學(xué)與工程學(xué)院道路圖和圈圖若一個(gè)圖能以一條基本道路表示出來(lái)，則稱此圖為道路圖。n階的道路圖記為Pn。若一個(gè)圖能以一個(gè)圈表示出來(lái)，則稱此圖為圈圖。n階的圈圖記為Cn。例10.12P5C63/16/202377計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條通路，其中vi0=vi，vik=vj。此通路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條通路即為所求。若k＞n－1，則此通路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此通路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的通路，至少去掉一條邊，得通路vi0,vi1,…,vis,vit+1,…vik，此通路比原通路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的通路?！?/16/202378計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條道路，其中vi0=vi，vik=vj。此道路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條道路即為所求。若k＞n－1，則此道路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的道路，至少去掉一條邊，得道路vi0,vi1,…,vis,vit+1,…vik，此道路比原道路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的道路。■3/16/202379計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條道路，其中vi0=vi，vik=vj。此道路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條道路即為所求。若k＞n－1，則此道路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的道路，至少去掉一條邊，得道路vi0,vi1,…,vis,vit+1,…vik，此道路比原道路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的道路?！?/16/202380計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條道路，其中vi0=vi，vik=vj。此道路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條道路即為所求。若k＞n－1，則此道路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的道路，至少去掉一條邊，得道路vi0,vi1,…,vis,vit+1,…vik，此道路比原道路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的道路?！?/16/202381計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條道路，其中vi0=vi，vik=vj。此道路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條道路即為所求。若k＞n－1，則此道路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的道路，至少去掉一條邊，得道路vi0,vi1,…,vis,vit+1,…vik，此道路比原道路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的道路?！?/16/202382計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-2.1在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj

(vi≠vj)存在一條道路，則從vi到vj存在一條不多于n-1條邊的道路。

證明:設(shè)vi0,vi1,…,vik為從vi到vj的長(zhǎng)度為k的一條道路，其中vi0=vi，vik=vj。此道路上有k+1個(gè)結(jié)點(diǎn)。若k≤n-1，這條道路即為所求。若k＞n－1，則此道路上的結(jié)點(diǎn)數(shù)k+1＞n，必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn)，設(shè)vis=vit，其中，0≤s＜t≤k。去掉vis到vit中間的道路，至少去掉一條邊，得道路vi0,vi1,…,vis,vit+1,…vik，此道路比原道路的長(zhǎng)度至少少1。如此重復(fù)進(jìn)行下去，必可得一條從vi到vj不多于n-1條邊的道路。

■3/16/202383計(jì)算機(jī)科學(xué)與工程學(xué)院§10.3圖的連通性3/16/202384計(jì)算機(jī)科學(xué)與工程學(xué)院無(wú)向圖的連通性

定義10-3.1

設(shè)u,v為無(wú)向圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若u,v之間存在道路，則稱結(jié)點(diǎn)u,v是連通的，記為u～v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u～u。

無(wú)向圖中結(jié)點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系。我們可以利用連通關(guān)系對(duì)G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分:{V1，V2，…，Vk}（顯然，Vi是一個(gè)等價(jià)類），使得G中的任意兩個(gè)結(jié)點(diǎn)u和v連通當(dāng)且僅當(dāng)u和v同屬于一個(gè)

Vi(1≤i≤k)。則點(diǎn)誘導(dǎo)子圖G（Vi）(1≤i≤k)是G的極大連通子圖，稱為G的支。圖G的分支數(shù)記為（G）。3/16/202385計(jì)算機(jī)科學(xué)與工程學(xué)院無(wú)向圖的連通性

定義10-3.1設(shè)u,v為無(wú)向圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若u,v之間存在道路，則稱結(jié)點(diǎn)u,v是連通的，記為u～v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u～u。

無(wú)向圖中結(jié)點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系。我們可以利用連通關(guān)系對(duì)G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分:{V1，V2，…，Vk}（顯然，Vi是一個(gè)等價(jià)類），使得G中的任意兩個(gè)結(jié)點(diǎn)u和v連通當(dāng)且僅當(dāng)u和v同屬于一個(gè)

Vi(1≤i≤k)。則點(diǎn)誘導(dǎo)子圖G（Vi）(1≤i≤k)是G的極大連通子圖，稱為G的支。圖G的分支數(shù)記為（G）。3/16/202386計(jì)算機(jī)科學(xué)與工程學(xué)院無(wú)向圖的連通性

定義10-3.1設(shè)u,v為無(wú)向圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若u,v之間存在道路，則稱結(jié)點(diǎn)u,v是連通的，記為u～v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u～u。

無(wú)向圖中結(jié)點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系。我們可以利用連通關(guān)系對(duì)G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分:{V1，V2，…，Vk}（顯然，Vi是一個(gè)等價(jià)類），使得G中的任意兩個(gè)結(jié)點(diǎn)u和v連通當(dāng)且僅當(dāng)u和v同屬于一個(gè)

Vi(1≤i≤k)。則點(diǎn)誘導(dǎo)子圖G（Vi）

(1≤i≤k)是G的極大連通子圖，稱為G的支。圖G的分支數(shù)記為（G）。3/16/202387計(jì)算機(jī)科學(xué)與工程學(xué)院連通圖定義10-3.2

若無(wú)向圖G＝<V，E>中任意兩個(gè)結(jié)點(diǎn)都是連通的，則稱G是連通圖，否則稱G是非連通圖(或分離圖)。定義10-3.2′只有一個(gè)分支的無(wú)向圖稱為連通圖，支數(shù)大于1的無(wú)向圖稱為非連通圖。無(wú)向完全圖Kn（n≥1）都是連通圖，而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖。

3/16/202388計(jì)算機(jī)科學(xué)與工程學(xué)院連通圖定義10-3.2若無(wú)向圖G＝<V，E>中任意兩個(gè)結(jié)點(diǎn)都是連通的，則稱G是連通圖，否則稱G是非連通圖(或分離圖)。定義10-3.2′只有一個(gè)分支的無(wú)向圖稱為連通圖，支數(shù)大于1的無(wú)向圖稱為非連通圖。無(wú)向完全圖Kn（n≥1）都是連通圖，而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖。

3/16/202389計(jì)算機(jī)科學(xué)與工程學(xué)院連通圖定義10-3.2若無(wú)向圖G＝<V，E>中任意兩個(gè)結(jié)點(diǎn)都是連通的，則稱G是連通圖，否則則稱G是非連通圖(或分離圖)。定義10-3.2′只有一個(gè)分支的無(wú)向圖稱為連通圖，支數(shù)大于1的無(wú)向圖稱為非連通圖。無(wú)向完全圖Kn（n≥1）都是連通圖，而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖。

3/16/202390計(jì)算機(jī)科學(xué)與工程學(xué)院例10.10G1是連通圖，所以(G1)＝1。G2是非連通圖，且(G2)＝4。

v2v1v3v5v4v6v10v8v9v7v11G2v2v1v5v4G1v3v6v73/16/202391計(jì)算機(jī)科學(xué)與工程學(xué)院定義10-3.3

在圖G＝<V，E>中，對(duì)vi，vjV，如果從vi到vj存在道路，則稱長(zhǎng)度最短的道路為從vi到vj的距離，記為d(vi,vj)。

d(vi，vj)滿足下列性質(zhì)：d(vi,vj)≥0；d(vi,vi)＝0；d(vi,vk)+d(vk，vj)≥d(vi，vj)；d(vi,vj)＝

(當(dāng)vi到vj不存在道路時(shí))距離3/16/202392計(jì)算機(jī)科學(xué)與工程學(xué)院定義10-3.3在圖G＝<V，E>中，對(duì)vi，vjV，如果從vi到vj存在道路，則稱長(zhǎng)度最短的道路為從vi到vj的距離，記為d(vi,vj)。

d(vi，vj)滿足下列性質(zhì)：d(vi,vj)≥0；（非負(fù)性）d(vi,vi)＝0；（對(duì)稱性）d(vi,vk)+d(vk，vj)≥d(vi，vj);(三角不等式)d(vi,vj)＝

(當(dāng)vi到vj不存在道路時(shí))距離3/16/202393計(jì)算機(jī)科學(xué)與工程學(xué)院例10.9在G1中有：

d(v2,v1)＝1，

d(v3,v1)＝2，

d(v1,v4)＝3，

d(v1,v2)＝2，

d(v1,v3)＝4，

d(v4,v1)＝3；在G2中有：

d(v1,v3)＝2， d(v3,v7)＝3， d(v1,v7)＝4。G1v4v1v3v2v5v6v1v4v3v2G2v5v73/16/202394計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)割集定義10-3.4

設(shè)無(wú)向圖G＝<V,E>。若存在結(jié)點(diǎn)子集V′V，使得刪除V′后，所得子圖G-V′的連通分支數(shù)與G的連通分支數(shù)滿足(G-V′)＞

(G)，則稱V′為G的一個(gè)點(diǎn)割集（割集）；而刪除V′的任何真子集V〞（即V〞V′）后，(G-V〞)＝(G)，則稱V′為G的一個(gè)基本割集。特別地，若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn)v，則稱v為割點(diǎn)。當(dāng)G是無(wú)向連通圖時(shí)，(G)=1。3/16/202395計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)割集定義10-3.4

設(shè)無(wú)向圖G＝<V,E>。若存在結(jié)點(diǎn)子集V′V，使得刪除V′后，所得子圖G-V′的連通分支數(shù)與G的連通分支數(shù)滿足(G-V′)＞(G)，則稱V′為G的一個(gè)點(diǎn)割集（割集）；而刪除V′的任何真子集V〞（即V〞V′）后，(G-V〞)＝(G)，則稱V′為G的一個(gè)基本割集。特別地，若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn)v，則稱v為割點(diǎn)。當(dāng)G是無(wú)向連通圖時(shí)，(G)=1。3/16/202396計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)割集定義10-3.4

設(shè)無(wú)向圖G＝<V,E>。若存在結(jié)點(diǎn)子集V′V，使得刪除V′后，所得子圖G-V′的連通分支數(shù)與G的連通分支數(shù)滿足(G-V′)＞(G)，則稱V′為G的一個(gè)點(diǎn)割集（割集）；而刪除V′的任何真子集V〞（即V〞V′）后，(G-V〞)＝(G)，則稱V′為G的一個(gè)基本割集。特別地，若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn)v，則稱v為割點(diǎn)。當(dāng)G是無(wú)向連通圖時(shí)，

(G)=1。3/16/202397計(jì)算機(jī)科學(xué)與工程學(xué)院例10.11{v3,v5},{v2},{v6},{v2,v4},{v2,v3,v5}…為點(diǎn)割集；{v3,v5},{v2},{v6}為基本割集。v2

、v6為割點(diǎn)。e2v5v1v2v3v4e3e5e1e4e7e6e9v6v7e83/16/202398計(jì)算機(jī)科學(xué)與工程學(xué)院邊割集定義10-3.5

設(shè)無(wú)向圖G＝<V,E>。若存在邊集子集E′E，使得刪除E′后，所得子圖G-E′的連通分支數(shù)與G的連通分支數(shù)滿足(G-E′)＞(G)，則稱E′為G的一個(gè)邊割集；而刪除E′的任何真子集E〞（即E〞E′）后，(G-E〞)＝(G)，則稱E′為G的一個(gè)基本邊割集。特別地，若割集中只有一條邊e，則稱e為割邊。當(dāng)G是無(wú)向連通圖時(shí)，(G)=1。3/16/202399計(jì)算機(jī)科學(xué)與工程學(xué)院邊割集定義10-3.5

設(shè)無(wú)向圖G＝<V,E>。若存在邊集子集E′E，使得刪除E′后，所得子圖G-E′的連通分支數(shù)與G的連通分支數(shù)滿足(G-E′)＞(G)，則稱E′為G的一個(gè)邊割集；而刪除E′的任何真子集E〞（即E〞E′）后，

(G-E〞)＝(G)，則稱E′為G的一個(gè)基本邊割集。特別地，若割集中只有一條邊e，則稱e為割邊。當(dāng)G是無(wú)向連通圖時(shí)，(G)=1。3/16/2023100計(jì)算機(jī)科學(xué)與工程學(xué)院邊割集定義10-3.5

設(shè)無(wú)向圖G＝<V,E>。若存在邊集子集E′E，使得刪除E′后，所得子圖G-E′的連通分支數(shù)與G的連通分支數(shù)滿足(G-E′)＞(G)，則稱E′為G的一個(gè)邊割集；而刪除E′的任何真子集E〞（即E〞E′）后，(G-E〞)＝(G)，則稱E′為G的一個(gè)基本邊割集。特別地，若割集中只有一條邊e，則稱e為割邊。當(dāng)G是無(wú)向連通圖時(shí)，

(G)=1。3/16/2023101計(jì)算機(jī)科學(xué)與工程學(xué)院例10.12{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9},{e6,e7,e9},{e1,e2,e5,e6,e8}等都是邊割集；{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}等都是基本邊割集；e9是割邊。e2v5v1v2v3v4e3e5e1e4e7e6e9v6v7e83/16/2023102計(jì)算機(jī)科學(xué)與工程學(xué)院例10.12{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9},{e6,e7,e9},{e1,e2,e5,e6,e8}等都是邊割集；{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}等都是基本邊割集；e9是割邊。e2v5v1v2v3v4e3e5e1e4e7e6e9v6v7e83/16/2023103計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)連通度、邊連通度定義10-3.6設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|V||V為G的點(diǎn)割集}為G的點(diǎn)連通度，簡(jiǎn)稱連通度。

規(guī)定：完全圖Kn的點(diǎn)連通度為n-1，n≥1；非連通圖的點(diǎn)連通度為0。又若(G)≥k，則稱G為k-連通圖。（顯然，點(diǎn)連通度越大，連通性越好）設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|E||E為G的邊割集}為G的邊連通度。規(guī)定非連通圖的邊連通度為0。又若

(G)≥k，則稱G為k邊-連通圖。3/16/2023104計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)連通度、邊連通度定義10-3.6設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|V||V為G的點(diǎn)割集}為G的點(diǎn)連通度，簡(jiǎn)稱連通度。規(guī)定：完全圖Kn的點(diǎn)連通度為n-1，n≥1；非連通圖的點(diǎn)連通度為0。又若(G)≥k，則稱G為k-連通圖。（顯然，點(diǎn)連通度越大，連通性越好）設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|E||E為G的邊割集}為G的邊連通度。規(guī)定非連通圖的邊連通度為0。又若

(G)≥k，則稱G為k邊-連通圖。3/16/2023105計(jì)算機(jī)科學(xué)與工程學(xué)院點(diǎn)連通度、邊連通度定義10-3.6設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|V||V為G的點(diǎn)割集}為G的點(diǎn)連通度，簡(jiǎn)稱連通度。規(guī)定：完全圖Kn的點(diǎn)連通度為n-1，n≥1；非連通圖的點(diǎn)連通度為0。又若(G)≥k，則稱G為k-連通圖。（顯然，點(diǎn)連通度越大，連通性越好）設(shè)無(wú)向圖連通圖G＝<V,E>，稱(G)＝min{|E||E為G的邊割集}為G的邊連通度。規(guī)定非連通圖的邊連通度為0。又若

(G)≥k，則稱G為k邊-連通圖。3/16/2023106計(jì)算機(jī)科學(xué)與工程學(xué)院例10.13右圖所示圖的點(diǎn)連通度為1，它是1-連通圖，但不是2-連通圖；它的邊連通度為1，它是1邊-連通圖，但不是2邊-連通圖。彼得森圖的點(diǎn)連通度為3，它是1-連通圖、2-連通圖、3-連通圖，但不是4-連通圖；它的邊連通度為3，它是1邊-連通圖、2邊-連通圖、3邊-連通圖，但不是4邊-連通圖。e2v5v1v2v3v4e3e5e1e4e7e6e9v6v7e83/16/2023107計(jì)算機(jī)科學(xué)與工程學(xué)院例10.13右圖所示圖的點(diǎn)連通度為1，它是1-連通圖，但不是2-連通圖；它的邊連通度為1，它是1邊-連通圖，但不是2邊-連通圖。彼得森圖的點(diǎn)連通度為3，它是1-連通圖、2-連通圖、3-連通圖，但不是4-連通圖；它的邊連通度為3，它是1邊-連通圖、2邊-連通圖、3邊-連通圖，但不是4邊-連通圖。e2v5v1v2v3v4e3e5e1e4e7e6e9v6v7e8彼得森圖3/16/2023108計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.1

在非平凡連通圖G中，結(jié)點(diǎn)v為G的割點(diǎn)的充分必要條件是存在結(jié)點(diǎn)u和w，使u到w的每一條道路都以v為內(nèi)部結(jié)點(diǎn)。（P212,定理10-3.1）定理10-3.2

在非平凡連通圖G中，邊e為G的割邊的充分必要條件是e不包含于G的任何圈中。3/16/2023109計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.1

在非平凡連通圖G中，結(jié)點(diǎn)v為G的割點(diǎn)的充分必要條件是存在結(jié)點(diǎn)u和w，使u到w的每一條道路都以v為內(nèi)部結(jié)點(diǎn)。（P212,定理10-3.1）定理10-3.2

在非平凡連通圖G中，邊e為G的割邊的充分必要條件是e不包含于G的任何圈中。割點(diǎn)v是圖中任何道路的必經(jīng)之處！“一夫當(dāng)關(guān)，萬(wàn)夫莫開”3/16/2023110計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.1

在非平凡連通圖G中，結(jié)點(diǎn)v為G的割點(diǎn)的充分必要條件是存在結(jié)點(diǎn)u和w，使u到w的每一條道路都以v為內(nèi)部結(jié)點(diǎn)。定理10-3.2

在非平凡連通圖G中，邊e為G的割邊的充分必要條件是e不包含于G的任何圈中。

（證明略，p212）3/16/2023111計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.3：

對(duì)任意無(wú)向圖G＝<V,E>，均有下面不等式成立：(G)≤(G)≤(G)。其中，(G)、(G)和(G)分別為G的點(diǎn)連通度、邊連通度和結(jié)點(diǎn)的最小度數(shù)。（證明略，p213）推論：對(duì)任意無(wú)向圖G＝<V,E>，若G是k-連通圖，則G必為k邊-連通圖。為什么？3/16/2023112計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.3：

對(duì)任意無(wú)向圖G＝<V,E>，均有下面不等式成立：(G)≤(G)≤(G)。其中，(G)、(G)和(G)分別為G的點(diǎn)連通度、邊連通度和結(jié)點(diǎn)的最小度數(shù)。推論：對(duì)任意無(wú)向圖G＝<V,E>，若G是k-連通圖，則G必為k邊-連通圖。為什么？

理由：(G)≤(G)3/16/2023113計(jì)算機(jī)科學(xué)與工程學(xué)院定理10-3.3：

對(duì)任意無(wú)向圖G＝<V,E>，均有下面不等式成立：(G)≤(G)≤(G)。其中，(G)、(G)和(G)分別為G的點(diǎn)連通度、邊連通度和結(jié)點(diǎn)的最小度數(shù)。推論：對(duì)任意無(wú)向圖G＝<V,E>，若G是k-連通圖，則G必為k邊-連通圖。為什么？

理由：(G)≤(G)3/16/2023114計(jì)算機(jī)科學(xué)與工程學(xué)院有向圖的連通性定義10-3.7設(shè)u,v為有向圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的道路，則稱從結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的，記為u→v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u→u。有向圖結(jié)點(diǎn)之間的可達(dá)關(guān)系具有自反性和傳遞性，但一般說(shuō)來(lái)，可達(dá)關(guān)系沒(méi)有對(duì)稱性。例如右圖中v3到v2可達(dá)，但v2到v3不可達(dá)。因此，可達(dá)關(guān)系不是等價(jià)關(guān)系。v3v1v4v23/16/2023115計(jì)算機(jī)科學(xué)與工程學(xué)院有向圖的連通性定義10-3.7設(shè)u,v為有向圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的道路，則稱從結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的，記為u→v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u→u。有向圖結(jié)點(diǎn)之間的可達(dá)關(guān)系具有自反性和傳遞性，但一般說(shuō)來(lái)，可達(dá)關(guān)系沒(méi)有對(duì)稱性。例如右圖中v3到v2可達(dá)，但v2到v3不可達(dá)。因此，可達(dá)關(guān)系不是等價(jià)關(guān)系。v3v1v4v23/16/2023116計(jì)算機(jī)科學(xué)與工程學(xué)院強(qiáng)連通圖、單向連通圖定義10-3.8

設(shè)有向圖G＝<V,E>是連通圖，

1)若G中任何一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱G是單向連通圖；

2)若G中任何一對(duì)結(jié)點(diǎn)之間都是相互可達(dá)的，則稱G是強(qiáng)連通圖。

3)若G的基圖是連通的，則稱G是弱連通圖。

若有向圖G是強(qiáng)連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。3/16/2023117計(jì)算機(jī)科學(xué)與工程學(xué)院強(qiáng)連通圖、單向連通圖定義10-3.8

設(shè)有向圖G＝<V,E>是連通圖，

1)若G中任何一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱G是單向連通圖；

2)若G中任何一對(duì)結(jié)點(diǎn)之間都是相互可達(dá)的，則稱G是

強(qiáng)連通圖。

3)若G的基圖是連通的，則稱G是弱連通圖。

若有向圖G是強(qiáng)連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。3/16/2023118計(jì)算機(jī)科學(xué)與工程學(xué)院強(qiáng)連通圖、單向連通圖定義10-3.8

設(shè)有向圖G＝<V,E>是連通圖，

1)若G中任何一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱G是單向連通圖；

2)若G中任何一對(duì)結(jié)點(diǎn)之間都是相互可達(dá)的，則稱G是強(qiáng)連通圖。

3)若G的基圖是連通的，則稱G是弱連通圖。

若有向圖G是強(qiáng)連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。一個(gè)有向圖的基圖是當(dāng)去掉邊的方向后得道的無(wú)向圖（可含有平行邊和環(huán)）3/16/2023119計(jì)算機(jī)科學(xué)與工程學(xué)院強(qiáng)連通圖、單向連通圖定義10-3.8

設(shè)有向圖G＝<V,E>是連通圖，

1)若G中任何一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則