離散數(shù)學(xué)(第10.1)陳瑜省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

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

，（a,b）稱為無序?qū)?/p>

。與序偶不一樣，不論a,b是否相等，都有：(a,b)＝(b,a)。

3/639/16/20233計算機(jī)科學(xué)與工程學(xué)院§10.1圖基本概念無序積定義：設(shè)A,B為任意集合，稱集合A&B＝{(a,b)|a∈A，b∈B}為A與B無序積，（a,b）稱為無序?qū)?。與序偶不一樣，不論a,b是否相等，都有：(a,b)＝(b,a)。

4/639/16/20234計算機(jī)科學(xué)與工程學(xué)院圖定義定義10-1.1

一個圖是一個序偶<V,E>，記為G＝<V,E>，其中：

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

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

5/639/16/20235計算機(jī)科學(xué)與工程學(xué)院圖定義定義10-1.1

一個圖是一個序偶<V,E>，記為G＝<V,E>，其中：

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

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

3）圖G結(jié)點(diǎn)數(shù)稱為G階，用n表示，G邊數(shù)用m表示，也可表示成(G)=m。6/639/16/20236計算機(jī)科學(xué)與工程學(xué)院圖定義定義10-1.1

一個圖是一個序偶<V,E>，記為G＝<V,E>，其中：

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

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

3）圖G結(jié)點(diǎn)數(shù)稱為G階，用n表示，G邊數(shù)用m表示，也可表示成(G)=m。

7/639/16/20237計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊方向)若邊e與無序結(jié)點(diǎn)對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e兩個端點(diǎn)；若邊e與有序結(jié)點(diǎn)對<u，v>相對應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時稱u是邊e始點(diǎn)。v是邊e終點(diǎn)，統(tǒng)稱為e端點(diǎn)；e是u出邊，是v入邊。每條邊都是無向邊圖稱為無向圖；每條邊都是有向邊圖稱為有向圖；有些邊是無向邊，而另一些是有向邊圖稱為混合圖。用小圓圈表示V中結(jié)點(diǎn)，用由u指向v有向線段表示<u,v>，無向線段表示(u,v)。8/639/16/20238計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊方向)若邊e與無序結(jié)點(diǎn)對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e兩個端點(diǎn)；若邊e與有序結(jié)點(diǎn)對<u，v>相對應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時稱u是邊e始點(diǎn)。v是邊e終點(diǎn)，統(tǒng)稱為e端點(diǎn)；e是u出邊，是v入邊。每條邊都是無向邊圖稱為無向圖；每條邊都是有向邊圖稱為有向圖；有些邊是無向邊，而另一些是有向邊圖稱為混合圖。用小圓圈表示V中結(jié)點(diǎn)，用由u指向v有向線段表示<u,v>，無向線段表示(u,v)。9/639/16/20239計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊方向)若邊e與無序結(jié)點(diǎn)對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e兩個端點(diǎn)；若邊e與有序結(jié)點(diǎn)對<u，v>相對應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時稱u是邊e始點(diǎn)。v是邊e終點(diǎn)，統(tǒng)稱為e端點(diǎn)；e是u出邊，是v入邊。每條邊都是無向邊圖稱為無向圖；每條邊都是有向邊圖稱為有向圖；有些邊是無向邊，而另一些是有向邊圖稱為混合圖。用小圓圈表示V中結(jié)點(diǎn)，用由u指向v有向線段表示<u,v>，無向線段表示(u,v)。10/639/16/202310計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊方向)若邊e與無序結(jié)點(diǎn)對(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e兩個端點(diǎn)；若邊e與有序結(jié)點(diǎn)對<u，v>相對應(yīng)，則稱邊e為有向邊，記為e＝<u，v>，這時稱u是邊e始點(diǎn)。v是邊e終點(diǎn)，統(tǒng)稱為e端點(diǎn)；e是u出邊，是v入邊。每條邊都是無向邊圖稱為無向圖；每條邊都是有向邊圖稱為有向圖；有些邊是無向邊，而另一些是有向邊圖稱為混合圖。用小圓圈表示V中結(jié)點(diǎn)，用由u指向v有向線段表示<u,v>，無向線段表示(u,v)。11/639/16/202311計算機(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)圖；e1e2e5v3v2v1e3e4e6v5v412/639/16/202312計算機(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)圖；e1e2e5v3v2v1e3e4e6v5v413/639/16/202313計算機(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)圖；e1e2e5v3v2v1e3e4e6v5v414/639/16/202314計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊重數(shù))在有向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有同始點(diǎn)和同終點(diǎn)幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊圖稱為多重圖；含有環(huán)多重圖稱為廣義圖（偽圖）；滿足定義9-1.1圖稱為簡單圖。將多重圖和廣義圖中平行邊代之以一條邊，去掉環(huán)，能夠得到一個簡單圖，稱為原來圖基圖。15/639/16/202315計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊重數(shù))在有向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有同始點(diǎn)和同終點(diǎn)幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊圖稱為多重圖；含有環(huán)多重圖稱為廣義圖（偽圖）；滿足定義10-1.1圖稱為簡單圖。將多重圖和廣義圖中平行邊代之以一條邊，去掉環(huán)，能夠得到一個簡單圖，稱為原來圖基圖。16/639/16/202316計算機(jī)科學(xué)與工程學(xué)院圖分類(按邊重數(shù))在有向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有同始點(diǎn)和同終點(diǎn)幾條邊，則這幾條邊稱為平行邊。在無向圖中，兩個結(jié)點(diǎn)間(包含結(jié)點(diǎn)本身間)若有幾條邊，則這幾條邊稱為平行邊；含有平行邊圖稱為多重圖；含有環(huán)多重圖稱為廣義圖（偽圖）；滿足定義10-1.1圖稱為簡單圖。將多重圖和廣義圖中平行邊代之以一條邊，去掉環(huán)，能夠得到一個簡單圖，稱為原來圖基圖。17/639/16/202317計算機(jī)科學(xué)與工程學(xué)院圖分類(按權(quán))賦權(quán)圖G是一個三重組<V,E,g>，其中V是結(jié)點(diǎn)集合，E是邊集合，g是邊E上權(quán)值。非賦權(quán)圖稱為無權(quán)圖。v3v2v1v456678795G118/639/16/202318計算機(jī)科學(xué)與工程學(xué)院結(jié)點(diǎn)度數(shù)

在無向圖G＝<V，E>中，與結(jié)點(diǎn)v(v

V)關(guān)聯(lián)邊條數(shù)（有環(huán)時計算兩次），稱為該結(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)；19/639/16/202319計算機(jī)科學(xué)與工程學(xué)院結(jié)點(diǎn)度數(shù)

在無向圖G＝<V，E>中，與結(jié)點(diǎn)v(v

V)關(guān)聯(lián)邊條數(shù)（有環(huán)時計算兩次），稱為該結(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)；20/639/16/202320計算機(jī)科學(xué)與工程學(xué)院對于圖G＝<V，E>，度數(shù)為0結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)組成圖G=（V，）稱為零圖；只由一個孤立結(jié)點(diǎn)組成圖稱為平凡圖；在圖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度正則圖。21/639/16/202321計算機(jī)科學(xué)與工程學(xué)院對于圖G＝<V，E>，度數(shù)為0結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)組成圖G=（V，）稱為零圖；只由一個孤立結(jié)點(diǎn)組成圖稱為平凡圖；在圖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度正則圖。22/639/16/202322計算機(jī)科學(xué)與工程學(xué)院對于圖G＝<V，E>，度數(shù)為0結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)組成圖G=（V，）稱為零圖；只由一個孤立結(jié)點(diǎn)組成圖稱為平凡圖；在圖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度正則圖。23/639/16/202323計算機(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；v3v2v1v5v424/639/16/202324計算機(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；v3v2v1v5v425/639/16/202325計算機(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；v3v2v1v5v426/639/16/202326計算機(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；v3v2v1v5v427/639/16/202327計算機(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；v3v2v1v5v428/639/16/202328計算機(jī)科學(xué)與工程學(xué)院握手定理（Euler,1736年）定理10-1.1（握手定理）對于任何（n,m）圖G=（V，E），全部結(jié)點(diǎn)度數(shù)總和等于邊數(shù)兩倍，即：

證實：依據(jù)結(jié)點(diǎn)度數(shù)定義，在計算結(jié)點(diǎn)度數(shù)時每條邊對于它所關(guān)聯(lián)結(jié)點(diǎn)被計算了兩次，所以，G中結(jié)點(diǎn)度數(shù)總和恰好為邊數(shù)m2倍。■29/639/16/202329計算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1

在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)。證實設(shè)V1＝{v|v

V且deg(v)＝奇數(shù)}，V2＝{v|v

V且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：因為上式中2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)?！?0/639/16/202330計算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1

在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)。證實

設(shè)V1＝{v|v

V且deg(v)＝奇數(shù)}，V2＝{v|v

V且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：因為上式中2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)?！?1/639/16/202331計算機(jī)科學(xué)與工程學(xué)院推論10-1.1.1

在圖G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度數(shù)為奇數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)。證實

設(shè)V1＝{v|v

V且deg(v)＝奇數(shù)}，V2＝{v|v

V且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：因為上式中2m和|V2|(偶數(shù)之和為偶數(shù))均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因為V1中結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)結(jié)點(diǎn)個數(shù)為偶數(shù)?！?2/639/16/202332計算機(jī)科學(xué)與工程學(xué)院定理10-1.2：對于任何（n,m）有向圖G=（V，E），則全部結(jié)點(diǎn)引出度數(shù)之和等于全部結(jié)點(diǎn)引入度數(shù)之和，全部結(jié)點(diǎn)度數(shù)總和等于邊數(shù)兩倍，即：證實：（略）。33/639/16/202333計算機(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）。v3v2v1v5v434/639/16/202334計算機(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）。v3v2v1v5v435/639/16/202335計算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2

V1，E2

E1，則稱H是G子圖，記為H

G。即V2

V1或E2

E1，則稱H是G真子圖，記為H

G。若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)子圖，簡記為G－v。36/639/16/202336計算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2

V1，E2

E1，則稱H是G子圖，記為H

G。即V2

V1或E2

E1，則稱H是G真子圖，記為H

G。若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)子圖，簡記為G－v。37/639/16/202337計算機(jī)科學(xué)與工程學(xué)院子圖定義10-1.4

設(shè)有圖G＝<V1,E1>和圖H＝<V2,E2>。若V2

V1，E2

E1，則稱H是G子圖，記為H

G。即V2

V1或E2

E1，則稱H是G真子圖，記為H

G。若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)子圖，簡記為G－v。38/639/16/202338計算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G一條邊，從G中刪去邊e后得到圖稱為G刪邊子圖，簡記為G－e。圖G＝<V，E>

，S

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

，T

E且T≠

，則G（T）是一個以T為邊集，以T中各邊關(guān)聯(lián)全部結(jié)點(diǎn)為結(jié)點(diǎn)集圖，稱為G邊誘導(dǎo)子圖。39/639/16/202339計算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G一條邊，從G中刪去邊e后得到圖稱為G刪邊子圖，簡記為G－e。圖G＝<V，E>

，S

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

，T

E且T≠

，則G（T）是一個以T為邊集，以T中各邊關(guān)聯(lián)全部結(jié)點(diǎn)為結(jié)點(diǎn)集圖，稱為G邊誘導(dǎo)子圖。40/639/16/202340計算機(jī)科學(xué)與工程學(xué)院設(shè)e是圖G一條邊，從G中刪去邊e后得到圖稱為G刪邊子圖，簡記為G－e。圖G＝<V，E>

，S

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

，T

E且T≠

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

41/639/16/202341計算機(jī)科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-{e1,e2}e3e2e1v2v1G3e3e2e1v2v1刪點(diǎn)子圖刪邊子圖點(diǎn)誘導(dǎo)子圖G3({v1,v2})邊誘導(dǎo)子圖G3({e1,e2,e3})例10.242/639/16/202342計算機(jī)科學(xué)與工程學(xué)院G1vG1-VG2e1e2G2-{e1,e2}e3e2e1v2v1G3e3e2e1v2v1刪點(diǎn)子圖刪邊子圖點(diǎn)誘導(dǎo)子圖G3({v1,v2})邊誘導(dǎo)子圖G3({e1,e2,e3})例10.243/639/16/202343計算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)無向簡單圖，假如G中任一個結(jié)點(diǎn)都與其余n-1個結(jié)點(diǎn)相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)有向簡單圖，若對于任意u,v

V(u

v)，現(xiàn)有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解情況下，也記為Kn。

無向完全圖Kn邊數(shù)為=n(n-1)，有向完全圖Kn邊數(shù)為=n(n-1)。44/639/16/202344計算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)無向簡單圖，假如G中任一個結(jié)點(diǎn)都與其余n-1個結(jié)點(diǎn)相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)有向簡單圖，若對于任意u,v

V(u

v)，現(xiàn)有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解情況下，也記為Kn。

無向完全圖Kn邊數(shù)為=n(n-1)，有向完全圖Kn邊數(shù)為=n(n-1)。45/639/16/202345計算機(jī)科學(xué)與工程學(xué)院完全圖設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)無向簡單圖，假如G中任一個結(jié)點(diǎn)都與其余n-1個結(jié)點(diǎn)相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設(shè)G＝<V,E>為一個含有n個結(jié)點(diǎn)有向簡單圖，若對于任意u,v

V(u

v)，現(xiàn)有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解情況下，也記為Kn。

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

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

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

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

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

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

48/639/16/202348計算機(jī)科學(xué)與工程學(xué)院例10.349/639/16/202349計算機(jī)科學(xué)與工程學(xué)院二部圖設(shè)圖G=<V,E>，假如它結(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。50/639/16/202350計算機(jī)科學(xué)與工程學(xué)院二部圖

設(shè)圖G=<V,E>，假如它結(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。51/639/16/202351計算機(jī)科學(xué)與工程學(xué)院圖同構(gòu)abcdabcdabcdabcd52/639/16/202352計算機(jī)科學(xué)與工程學(xué)院定義10-1.6設(shè)兩個圖G=<V,E>和G′=<V′,E′>，假如存在雙射函數(shù)g：V→V′，使得對于任意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)是指兩個圖邊1-1對應(yīng)）圖同構(gòu)關(guān)系是圖集上等價關(guān)系。53/639/16/202353計算機(jī)科學(xué)與工程學(xué)院定義10-1.6設(shè)兩個圖G=<V,E>和G′=<V′,E′>，假如存在雙射函數(shù)g：V→V′，使得對于任意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)是指兩個圖邊