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

1、陳瑜Email：134028388008/6/2022離散數(shù)學(xué)計(jì)算機(jī)學(xué)院8/6/20221計(jì)算機(jī)科學(xué)與工程學(xué)院主要內(nèi)容圖的基本概念什么是圖圖的分類結(jié)點(diǎn)的度數(shù) 握手定理子圖與補(bǔ)圖 完全圖補(bǔ)圖圖的同構(gòu)8/6/20222計(jì)算機(jī)科學(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計(jì)算機(jī)科學(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計(jì)算機(jī)科學(xué)與工程學(xué)院圖的定義定義10-1.1一個圖是一個序偶，記為 G，其中： 1）V（G）v1,v2,v3,vn是一個有限的非空集合，vi(i1,2,3,n)稱為結(jié)點(diǎn),簡稱點(diǎn)，V為結(jié)點(diǎn)集； 2）E（G）e1,e2,e3,em是一個有限的集合，ei(i1,2,3,m)稱為邊，E為邊集，E中的每個元素都是由V中不同結(jié)點(diǎn)所構(gòu)成的無序?qū)Γ也缓貜?fù)元素。 3）圖G的結(jié)點(diǎn)數(shù)稱為G的階，用n表示，G的邊數(shù)用m表示，也可表示成(G)=m 。 8/6/20225計(jì)算機(jī)科學(xué)與工程學(xué)院圖的定義定義1

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

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

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

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

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

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

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

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

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

12、(按權(quán))賦權(quán)圖G是一個三重組，其中V是結(jié)點(diǎn)集合，E是邊的集合，g是邊E上的權(quán)值。非賦權(quán)圖稱為無權(quán)圖。v3v2v1v456678795G18/6/202218計(jì)算機(jī)科學(xué)與工程學(xué)院結(jié)點(diǎn)的度數(shù) 在無向圖G中，與結(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中，以結(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)；8/6/202219

13、計(jì)算機(jī)科學(xué)與工程學(xué)院結(jié)點(diǎn)的度數(shù) 在無向圖G中，與結(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中，以結(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)；8/6/202220計(jì)算機(jī)科學(xué)與工程學(xué)院對于圖G，度數(shù)為0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖G=（V，）稱為零圖；只由一個孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖；在圖G中，稱度數(shù)為奇

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

15、度數(shù)結(jié)點(diǎn)，度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。各點(diǎn)度數(shù)相等的圖稱為正則圖，特別將點(diǎn)度為k的正則圖稱為k度正則圖。8/6/202223計(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；v3v2v1v5v48/6/202224計(jì)算機(jī)科學(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計(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；v3v2v1v5v48/6/202226計(jì)算機(jī)科學(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計(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；de

18、g(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202228計(jì)算機(jī)科學(xué)與工程學(xué)院握手定理（Euler,1736年）定理10-1.1（握手定理）對于任何（n,m）圖G =（V，E），所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即： 證明：根據(jù)結(jié)點(diǎn)度數(shù)的定義，在計(jì)算結(jié)點(diǎn)度數(shù)時(shí)每條邊對于它所關(guān)聯(lián)的結(jié)點(diǎn)被計(jì)算了兩次，因此，G中結(jié)點(diǎn)度數(shù)的總和恰好為邊數(shù)m的2倍。8/6/202229計(jì)算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1在圖G中，其Vv1,v2,v3,vn，Ee1，e2，em，度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(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ù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個數(shù)為偶數(shù)。8/6/202230計(jì)算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1在圖G中，其Vv1,v2,v3,vn，Ee1，e2，em，度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(shù)為偶數(shù)。證明設(shè)V1v|vV且deg(v)奇數(shù)，V2v|vV且deg(v)偶數(shù)。顯然，V1V2，且V1V2V，于是有：由于上式中的2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個數(shù)為偶數(shù)。8/

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

21、證明：（略）。8/6/202233計(jì)算機(jī)科學(xué)與工程學(xué)院度數(shù)序列設(shè)Vv1, v2,vn為圖G的結(jié)點(diǎn)集，稱(deg(v1),deg(v2),deg(vn)為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v48/6/202234計(jì)算機(jī)科學(xué)與工程學(xué)院度數(shù)序列設(shè)Vv1, v2,vn為圖G的結(jié)點(diǎn)集，稱(deg(v1),deg(v2),deg(vn)為G的度數(shù)序列。上圖的度數(shù)序列為（3,3,5,1,0）。v3v2v1v5v48/6/202235計(jì)算機(jī)科學(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é)點(diǎn)，從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點(diǎn)子圖，簡記為Gv。8/6/202236計(jì)算機(jī)科學(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é)點(diǎn)，從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的全部邊后得到的圖稱為G的刪點(diǎn)子圖，簡記為Gv。8/6/202237計(jì)算機(jī)

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

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

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

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

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

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

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