離散數(shù)學(xué)(第10.1)陳瑜

1、陳瑜Email：134028388008/6/2022離散數(shù)學(xué)計算機學(xué)院8/6/20221計算機科學(xué)與工程學(xué)院主要內(nèi)容圖的基本概念什么是圖圖的分類結(jié)點的度數(shù) 握手定理子圖與補圖 完全圖補圖圖的同構(gòu)8/6/20222計算機科學(xué)與工程學(xué)院10.1 圖的基本概念無序積的定義：設(shè)A,B 為任意集合，稱集合A&B (a,b)|aA ，bB為A 與B 的無序積 ，（a,b ） 稱為無序?qū)?。與序偶不同，無論a,b是否相等，均有： (a,b)(b,a)。 8/6/20223計算機科學(xué)與工程學(xué)院10.1 圖的基本概念無序積的定義：設(shè)A,B 為任意集合，稱集合A&B (a,b)|aA ，bB為A 與B 的無序積

2、 ，（a,b ） 稱為無序?qū)?。與序偶不同，無論a,b是否相等，均有： (a,b)(b,a)。 8/6/20224計算機科學(xué)與工程學(xué)院圖的定義定義10-1.1一個圖是一個序偶，記為 G，其中： 1）V（G）v1,v2,v3,vn是一個有限的非空集合，vi(i1,2,3,n)稱為結(jié)點,簡稱點，V為結(jié)點集； 2）E（G）e1,e2,e3,em是一個有限的集合，ei(i1,2,3,m)稱為邊，E為邊集，E中的每個元素都是由V中不同結(jié)點所構(gòu)成的無序?qū)?，且不含重?fù)元素。 3）圖G的結(jié)點數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m 。 8/6/20225計算機科學(xué)與工程學(xué)院圖的定義定義1

3、0-1.1一個圖是一個序偶，記為 G，其中： 1）V（G）v1,v2,v3,vn是一個有限的非空集合，vi(i1,2,3,n)稱為結(jié)點,簡稱點，V為結(jié)點集； 2）E（G）e1,e2,e3,em是一個有限的集合，ei(i1,2,3,m)稱為邊，E為邊集，E中的每個元素都是由V中不同結(jié)點所構(gòu)成的無序?qū)Γ也缓貜?fù)元素。 3）圖G的結(jié)點數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m 。8/6/20226計算機科學(xué)與工程學(xué)院圖的定義定義10-1.1一個圖是一個序偶，記為 G，其中： 1）V（G）v1,v2,v3,vn是一個有限的非空集合，vi(i1,2,3,n)稱為結(jié)點,簡稱點，V為結(jié)

4、點集； 2）E（G）e1,e2,e3,em是一個有限的集合，ei(i1,2,3,m)稱為邊，E為邊集，E中的每個元素都是由V中不同結(jié)點所構(gòu)成的無序?qū)Γ也缓貜?fù)元素。 3）圖G的結(jié)點數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m 。 8/6/20227計算機科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無序結(jié)點對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e(u，v)，這時稱u，v是邊e的兩個端點；若邊e與有序結(jié)點對相對應(yīng)，則稱邊e為有向邊，記為e，這時稱u是邊e的始點。v是邊e的終點，統(tǒng)稱為e的端點；e是u的出邊，是v的入邊。每條邊都是無向邊的圖稱為無向圖；每條邊都是有向邊的圖稱為

5、有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點，用由u指向v的有向線段表示，無向線段表示(u,v)。8/6/20228計算機科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無序結(jié)點對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e(u，v)，這時稱u，v是邊e的兩個端點；若邊e與有序結(jié)點對相對應(yīng)，則稱邊e為有向邊，記為e，這時稱u是邊e的始點。v是邊e的終點，統(tǒng)稱為e的端點；e是u的出邊，是v的入邊。每條邊都是無向邊的圖稱為無向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點，用由u指向v的有向線段表示，無向線段表

6、示(u,v)。8/6/20229計算機科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無序結(jié)點對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e(u，v)，這時稱u，v是邊e的兩個端點；若邊e與有序結(jié)點對相對應(yīng)，則稱邊e為有向邊，記為e，這時稱u是邊e的始點。v是邊e的終點，統(tǒng)稱為e的端點；e是u的出邊，是v的入邊。每條邊都是無向邊的圖稱為無向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點，用由u指向v的有向線段表示，無向線段表示(u,v)。8/6/202210計算機科學(xué)與工程學(xué)院圖的分類(按邊的方向)若邊e與無序結(jié)點對(u，v)相對應(yīng)，則稱邊

7、e為無向邊,記為e(u，v)，這時稱u，v是邊e的兩個端點；若邊e與有序結(jié)點對相對應(yīng)，則稱邊e為有向邊，記為e，這時稱u是邊e的始點。v是邊e的終點，統(tǒng)稱為e的端點；e是u的出邊，是v的入邊。每條邊都是無向邊的圖稱為無向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。用小圓圈表示V中的結(jié)點，用由u指向v的有向線段表示，無向線段表示(u,v)。8/6/202211計算機科學(xué)與工程學(xué)院幾個概念在一個圖中，關(guān)聯(lián)結(jié)點vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結(jié)點vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點，否則稱為不鄰接的；關(guān)聯(lián)于同一個結(jié)點的兩條邊稱為鄰接邊；

8、圖中關(guān)聯(lián)同一個結(jié)點的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點；僅由孤立結(jié)點組成的圖稱為零圖；僅含一個結(jié)點的零圖稱為平凡圖；含有n個結(jié)點、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v48/6/202212計算機科學(xué)與工程學(xué)院幾個概念在一個圖中，關(guān)聯(lián)結(jié)點vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結(jié)點vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點，否則稱為不鄰接的；關(guān)聯(lián)于同一個結(jié)點的兩條邊稱為鄰接邊；圖中關(guān)聯(lián)同一個結(jié)點的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點；僅由孤立結(jié)點組成的圖稱為零圖；僅含一個結(jié)點的零圖稱為平凡圖；含有n

9、個結(jié)點、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v48/6/202213計算機科學(xué)與工程學(xué)院幾個概念在一個圖中，關(guān)聯(lián)結(jié)點vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結(jié)點vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點，否則稱為不鄰接的；關(guān)聯(lián)于同一個結(jié)點的兩條邊稱為鄰接邊；圖中關(guān)聯(lián)同一個結(jié)點的邊稱為環(huán)(或自回路)；圖中不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點；僅由孤立結(jié)點組成的圖稱為零圖；僅含一個結(jié)點的零圖稱為平凡圖；含有n個結(jié)點、m條邊的圖稱為(n，m)圖；e1e2e5v3v2v1e3e4e6v5v48/6/202214計算機科學(xué)與工程學(xué)院圖的分類(按邊的重數(shù))在有向圖

10、中，兩個結(jié)點間(包括結(jié)點自身間)若有同始點和同終點的幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點間(包括結(jié)點自身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊的圖稱為多重圖；含有環(huán)的多重圖稱為廣義圖（偽圖）；滿足定義9-1.1的圖稱為簡單圖。將多重圖和廣義圖中的平行邊代之以一條邊，去掉環(huán)，可以得到一個簡單圖，稱為原來圖的基圖。8/6/202215計算機科學(xué)與工程學(xué)院圖的分類(按邊的重數(shù))在有向圖中，兩個結(jié)點間(包括結(jié)點自身間)若有同始點和同終點的幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點間(包括結(jié)點自身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊的圖稱為多重圖；含有環(huán)的多重

11、圖稱為廣義圖（偽圖）；滿足定義10-1.1的圖稱為簡單圖。將多重圖和廣義圖中的平行邊代之以一條邊，去掉環(huán)，可以得到一個簡單圖，稱為原來圖的基圖。8/6/202216計算機科學(xué)與工程學(xué)院圖的分類(按邊的重數(shù))在有向圖中，兩個結(jié)點間(包括結(jié)點自身間)若有同始點和同終點的幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點間(包括結(jié)點自身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊的圖稱為多重圖；含有環(huán)的多重圖稱為廣義圖（偽圖）；滿足定義10-1.1的圖稱為簡單圖。將多重圖和廣義圖中的平行邊代之以一條邊，去掉環(huán)，可以得到一個簡單圖，稱為原來圖的基圖。8/6/202217計算機科學(xué)與工程學(xué)院圖的分類

12、(按權(quán))賦權(quán)圖G是一個三重組，其中V是結(jié)點集合，E是邊的集合，g是邊E上的權(quán)值。非賦權(quán)圖稱為無權(quán)圖。v3v2v1v456678795G18/6/202218計算機科學(xué)與工程學(xué)院結(jié)點的度數(shù) 在無向圖G中，與結(jié)點v(vV)關(guān)聯(lián)的邊的條數(shù)（有環(huán)時計算兩次），稱為該結(jié)點的度數(shù)，記為deg(v)；最大點度和最小點度分別記為和。在有向圖G中，以結(jié)點v為始點引出的邊的條數(shù)，稱為該結(jié)點的出度,記為deg+(v)；以結(jié)點v為終點引入的邊的條數(shù)，稱為該結(jié)點的入度,記為deg-(v)；而結(jié)點的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點的度數(shù)，記為deg(v)，即deg(v)deg+(v)+deg-(v)；8/6/202219

13、計算機科學(xué)與工程學(xué)院結(jié)點的度數(shù) 在無向圖G中，與結(jié)點v(vV)關(guān)聯(lián)的邊的條數(shù)（有環(huán)時計算兩次），稱為該結(jié)點的度數(shù)，記為deg(v)；最大點度和最小點度分別記為和。在有向圖G中，以結(jié)點v為始點引出的邊的條數(shù)，稱為該結(jié)點的出度,記為deg+(v)；以結(jié)點v為終點引入的邊的條數(shù)，稱為該結(jié)點的入度,記為deg-(v)；而結(jié)點的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點的度數(shù)，記為deg(v)，即deg(v)deg+(v)+deg-(v)；8/6/202220計算機科學(xué)與工程學(xué)院對于圖G，度數(shù)為0的結(jié)點稱為孤立結(jié)點；只由孤立結(jié)點構(gòu)成的圖G=（V，）稱為零圖；只由一個孤立結(jié)點構(gòu)成的圖稱為平凡圖；在圖G中，稱度數(shù)為奇

14、數(shù)的結(jié)點為奇度數(shù)結(jié)點，度數(shù)為偶數(shù)的結(jié)點為偶度數(shù)結(jié)點。各點度數(shù)相等的圖稱為正則圖，特別將點度為k的正則圖稱為k度正則圖。8/6/202221計算機科學(xué)與工程學(xué)院對于圖G，度數(shù)為0的結(jié)點稱為孤立結(jié)點；只由孤立結(jié)點構(gòu)成的圖G=（V，）稱為零圖；只由一個孤立結(jié)點構(gòu)成的圖稱為平凡圖；在圖G中，稱度數(shù)為奇數(shù)的結(jié)點為奇度數(shù)結(jié)點，度數(shù)為偶數(shù)的結(jié)點為偶度數(shù)結(jié)點。各點度數(shù)相等的圖稱為正則圖，特別將點度為k的正則圖稱為k度正則圖。8/6/202222計算機科學(xué)與工程學(xué)院對于圖G，度數(shù)為0的結(jié)點稱為孤立結(jié)點；只由孤立結(jié)點構(gòu)成的圖G=（V，）稱為零圖；只由一個孤立結(jié)點構(gòu)成的圖稱為平凡圖；在圖G中，稱度數(shù)為奇數(shù)的結(jié)點為奇

15、度數(shù)結(jié)點，度數(shù)為偶數(shù)的結(jié)點為偶度數(shù)結(jié)點。各點度數(shù)相等的圖稱為正則圖，特別將點度為k的正則圖稱為k度正則圖。8/6/202223計算機科學(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；v3v2v1v5v48/6/202224計算機科學(xué)與工程學(xué)院例10.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)

16、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；v3v2v1v5v48/6/202225計算機科學(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；v3v2v1v5v48/6/202226計算機科學(xué)與工程學(xué)

17、院例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；v3v2v1v5v48/6/202227計算機科學(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；de

18、g(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202228計算機科學(xué)與工程學(xué)院握手定理（Euler,1736年）定理10-1.1（握手定理）對于任何（n,m）圖G =（V，E），所有結(jié)點的度數(shù)的總和等于邊數(shù)的兩倍，即： 證明：根據(jù)結(jié)點度數(shù)的定義，在計算結(jié)點度數(shù)時每條邊對于它所關(guān)聯(lián)的結(jié)點被計算了兩次，因此，G中結(jié)點度數(shù)的總和恰好為邊數(shù)m的2倍。8/6/202229計算機科學(xué)與工程學(xué)院推論10-1.1.1在圖G中，其Vv1,v2,v3,vn，Ee1，e2，em，度數(shù)為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。證明設(shè)V1v|vV且deg(v)奇數(shù)，V2v|vV且deg(v)偶數(shù)。顯然，V1V

19、2，且V1V2V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中的結(jié)點v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點個數(shù)為偶數(shù)。8/6/202230計算機科學(xué)與工程學(xué)院推論10-1.1.1在圖G中，其Vv1,v2,v3,vn，Ee1，e2，em，度數(shù)為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。證明設(shè)V1v|vV且deg(v)奇數(shù)，V2v|vV且deg(v)偶數(shù)。顯然，V1V2，且V1V2V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中的結(jié)點v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點個數(shù)為偶數(shù)。8/

20、6/202231計算機科學(xué)與工程學(xué)院推論10-1.1.1在圖G中，其Vv1,v2,v3,vn，Ee1，e2，em，度數(shù)為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。證明設(shè)V1v|vV且deg(v)奇數(shù)，V2v|vV且deg(v)偶數(shù)。顯然，V1V2，且V1V2V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中的結(jié)點v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點個數(shù)為偶數(shù)。8/6/202232計算機科學(xué)與工程學(xué)院定理10-1.2：對于任何（n,m）有向圖G =（V，E），則所有結(jié)點的引出度數(shù)之和等于所有結(jié)點的引入度數(shù)之和，所有結(jié)點的度數(shù)的總和等于邊數(shù)的兩倍，即：

21、證明：（略）。8/6/202233計算機科學(xué)與工程學(xué)院度數(shù)序列設(shè)Vv1, v2,vn為圖G的結(jié)點集，稱(deg(v1),deg(v2),deg(vn)為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v48/6/202234計算機科學(xué)與工程學(xué)院度數(shù)序列設(shè)Vv1, v2,vn為圖G的結(jié)點集，稱(deg(v1),deg(v2),deg(vn)為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v48/6/202235計算機科學(xué)與工程學(xué)院子圖 定義10-1.4 設(shè)有圖G和圖H。若V2V1，E2E1，則稱H是G的子圖，記為HG。即V2V1或E2E1，則稱H是G

22、的真子圖，記為HG。若V2=V1，則稱H是G的生成子圖。設(shè)V2=V1且E2=E1或E2=，則稱H是G的平凡子圖。設(shè)v是圖G的一個結(jié)點，從G中刪去結(jié)點v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點子圖，簡記為Gv。8/6/202236計算機科學(xué)與工程學(xué)院子圖 定義10-1.4 設(shè)有圖G和圖H。若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的一個結(jié)點，從G中刪去結(jié)點v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點子圖，簡記為Gv。8/6/202237計算機

23、科學(xué)與工程學(xué)院子圖 定義10-1.4 設(shè)有圖G和圖H。若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的一個結(jié)點，從G中刪去結(jié)點v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點子圖，簡記為Gv。8/6/202238計算機科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡記為Ge。圖G ，SV，則G(S)=(S，E)是一個以S為結(jié)點，以E=uv|u,vS,uvE為邊集的圖，稱為G的點誘導(dǎo)子圖。圖G ， TE且T，則G（T）是

24、一個以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點為結(jié)點集的圖，稱為G的邊誘導(dǎo)子圖。 8/6/202239計算機科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡記為Ge。圖G ，SV，則G(S)=(S，E)是一個以S為結(jié)點，以E=uv|u,vS,uvE為邊集的圖，稱為G的點誘導(dǎo)子圖。圖G ， TE且T，則G（T）是一個以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點為結(jié)點集的圖，稱為G的邊誘導(dǎo)子圖。 8/6/202240計算機科學(xué)與工程學(xué)院設(shè)e是圖G的一條邊，從G中刪去邊e后得到的圖稱為G刪邊子圖，簡記為Ge。圖G ，SV，則G(S)=(S，E)是一個以S為結(jié)點，以E=uv|u,vS,u

25、vE為邊集的圖，稱為G的點誘導(dǎo)子圖。圖G ， TE且T，則G（T）是一個以T為邊集，以T中各邊關(guān)聯(lián)的全部結(jié)點為結(jié)點集的圖，稱為G的邊誘導(dǎo)子圖。 8/6/202241計算機科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-e1,e2e3e2e1v2v1G3e3e2e1v2v1刪點子圖刪邊子圖點誘導(dǎo)子圖G3(v1,v2)邊誘導(dǎo)子圖G3(e1,e2,e3)例10.28/6/202242計算機科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-e1,e2e3e2e1v2v1G3e3e2e1v2v1刪點子圖刪邊子圖點誘導(dǎo)子圖G3(v1,v2)邊誘導(dǎo)子圖G3(e1,e2,e3)例10.28/6/202243計算機科

26、學(xué)與工程學(xué)院完全圖設(shè)G為一個具有n個結(jié)點的無向簡單圖，如果G中任一個結(jié)點都與其余n-1個結(jié)點相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G為一個具有n個結(jié)點的有向簡單圖，若對于任意u,vV(uv)，既有有向邊，又有有向邊，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。無向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為= n(n-1)。 8/6/202244計算機科學(xué)與工程學(xué)院完全圖設(shè)G為一個具有n個結(jié)點的無向簡單圖，如果G中任一個結(jié)點都與其余n-1個結(jié)點相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G為一個具有n個結(jié)點的有向簡單圖，若對于任意u,vV(u

27、v)，既有有向邊，又有有向邊，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。無向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為= n(n-1)。 8/6/202245計算機科學(xué)與工程學(xué)院完全圖設(shè)G為一個具有n個結(jié)點的無向簡單圖，如果G中任一個結(jié)點都與其余n-1個結(jié)點相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G為一個具有n個結(jié)點的有向簡單圖，若對于任意u,vV(uv)，既有有向邊，又有有向邊，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。無向完全圖Kn的邊數(shù)為=n(n-1)，有向完全圖Kn的邊數(shù)為= n(n-1)。 8/6/202246計算機科學(xué)與工程學(xué)院

28、補圖設(shè)G為具有n個結(jié)點的簡單圖,從完全圖Kn中刪去G中的所有邊而得到的圖稱為G相對于完全圖Kn的補圖，簡稱G的補圖，記為 。這里，當G為有向圖時，則Kn為有向完全圖；當G為無向圖時，則Kn為無向完全圖。 顯然，G與 互為補圖，即 。 8/6/202247計算機科學(xué)與工程學(xué)院補圖設(shè)G為具有n個結(jié)點的簡單圖,從完全圖Kn中刪去G中的所有邊而得到的圖稱為G相對于完全圖Kn的補圖，簡稱G的補圖，記為 。這里，當G為有向圖時，則Kn為有向完全圖；當G為無向圖時，則Kn為無向完全圖。 顯然，G與 互為補圖，即 。 8/6/202248計算機科學(xué)與工程學(xué)院例10.38/6/202249計算機科學(xué)與工程學(xué)院二

29、部圖 設(shè)圖G=，如果它的結(jié)點集可以劃分成兩個子集X和Y，使得它的每一條邊的一個關(guān)聯(lián)結(jié)點在X中，另一個關(guān)聯(lián)結(jié)點在Y中，則這樣的圖稱為二部圖。 設(shè)|X|=n1，|Y|=n2。如果X中的每一個結(jié)點與Y中的全部結(jié)點都鄰接，則稱G為完全二部圖，并記為Kn1,n2。8/6/202250計算機科學(xué)與工程學(xué)院二部圖 設(shè)圖G=，如果它的結(jié)點集可以劃分成兩個子集X和Y，使得它的每一條邊的一個關(guān)聯(lián)結(jié)點在X中，另一個關(guān)聯(lián)結(jié)點在Y中，則這樣的圖稱為二部圖。 設(shè)|X|=n1，|Y|=n2。如果X中的每一個結(jié)點與Y中的全部結(jié)點都鄰接，則稱G為完全二部圖，并記為Kn1,n2。8/6/202251計算機科學(xué)與工程學(xué)院圖的同構(gòu)abcdabcdabcdabcd8/6/202252計算機科學(xué)與工程學(xué)院定義10-1.6設(shè)兩個圖G=和G=，如果存在雙射函數(shù)g：VV，使得對于任意的e=(vi,vj) （或者）E當且僅當e(g(vi),g(vj) （或者）E，則稱G與G同構(gòu)，記為GG。（同構(gòu)是指兩個圖的邊1-1對應(yīng)）圖的同構(gòu)關(guān)系是圖集上的等價關(guān)系。 8/6/202253計算機科