《離散數(shù)學(xué)》PPT課件

《《離散數(shù)學(xué)》PPT課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一、圖定義一個(gè)圖是一個(gè)三元組,簡記為G＝。7-1圖的基本概念其中：V＝{v1,v2,v3,…,vn}是一個(gè)非空集合,vi(i＝1,2,3,…,n)稱為結(jié)點(diǎn),簡稱點(diǎn),V為結(jié)點(diǎn)集；E＝{e1,e2,e3,…,em}是一個(gè)有限的集合，ei(i＝1,2,3,…,m)稱為邊,E為邊集，E中的每個(gè)元素都有V中的結(jié)點(diǎn)對（有序偶或無序偶）與之對應(yīng)。例1離散數(shù)學(xué)圖的術(shù)語圖的術(shù)語若邊e與結(jié)點(diǎn)無序偶(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)；若邊e與結(jié)點(diǎn)有偶相對應(yīng)，則稱

2、邊e為有向邊(或弧)，記為e＝，這時(shí)稱u是邊e的始點(diǎn)(或弧尾).v是邊e的終點(diǎn)(或弧頭)，統(tǒng)稱為e的端點(diǎn)；在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點(diǎn)，否則稱為不鄰接的；2離散數(shù)學(xué)續(xù)：續(xù)：關(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)圖；3離散數(shù)學(xué)續(xù)：續(xù)：每條邊都是無向邊的圖稱為無向圖；每條

3、邊都是有向邊的圖稱為有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。在有向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有同始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱為平行邊，在無向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有幾條邊，則這幾條邊稱為平行邊，兩結(jié)點(diǎn)vi，vj間相互平行的邊的條數(shù)稱為邊(vi，vj)或的重?cái)?shù)；含有平行邊的圖稱為多重圖。非多重圖稱為線圖；無自回路的線圖稱為簡單圖。4離散數(shù)學(xué)(a)例：(b)(c)(d)例：5離散數(shù)學(xué)(e)(f)例：例：(g)6離散數(shù)學(xué)二、度數(shù)定義在無向圖G＝中，與結(jié)點(diǎn)v(v?V)關(guān)聯(lián)的邊的條

4、數(shù)，稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)；二、度數(shù)定義在有向圖G＝中，以結(jié)點(diǎn)v(v?V)為始點(diǎn)引出的邊的條數(shù)，稱為該結(jié)點(diǎn)的引出度數(shù),簡稱出度,記為deg+(v)；以結(jié)點(diǎn)v(v?V)為終點(diǎn)引入的邊的條數(shù)，稱為該結(jié)點(diǎn)的引入度數(shù)，簡稱入度,記為deg-(v)；而結(jié)點(diǎn)的出度和入度之和稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)，即deg(v)＝deg+(v)+deg-(v)；δ(G)最小度，Δ(G)最大度定義在圖G＝中，對任意結(jié)點(diǎn)v?V，若度數(shù)deg(v)為奇數(shù)，則稱此結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn)，若度數(shù)deg(v)為偶數(shù)，則稱此結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。7離

5、散數(shù)學(xué)例：deg(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)＝deg+(v4)＝deg-(v4)＝0；deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；例：8離散數(shù)學(xué)定理定理1.在圖G＝中，則所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：在有向圖G＝中，則所有結(jié)點(diǎn)的出度之和等于所有結(jié)點(diǎn)的入度之和，即：3.定理在所有圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù).9離散數(shù)學(xué)定

6、理。證明設(shè)V1＝{v

7、v?V且deg(v)＝奇數(shù)}，V2＝{v

8、v?V且deg(v)＝偶數(shù)}。顯然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和偶度數(shù)結(jié)點(diǎn)度數(shù)之和均為偶數(shù)，因而也為偶數(shù)。于是

9、V1

10、為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)?！?0離散數(shù)學(xué)三、完全圖三、完全圖定義在圖G＝中，若所有結(jié)點(diǎn)的度數(shù)均有相同度數(shù)d，則稱此圖為d次正則圖。定義一個(gè)(n，m)(n?2)的簡單無向圖，若它為n-1次正則圖，則稱該(n，m)圖為無向簡單完全圖，簡稱完全圖,記為Kn。有向完

11、全圖定理設(shè)無向完全圖G有n個(gè)頂點(diǎn)，則G有條邊。11離散數(shù)學(xué)四、子圖和補(bǔ)圖定義設(shè)有圖G＝和圖G1＝，若G和G1滿足：若V1?V，E1?E，則稱G1是G的子圖，記為G1?G；若G1?G，且G1?G(即V1?V或E1?E)，則稱G1是G的真子圖，記為G1?G；定義若V1＝V，E1?E，則稱G1是G的生成子圖，記為G1?G；定義設(shè)有圖G＝和圖G2＝，若V2?V，V2?Φ，以V2為結(jié)點(diǎn)集，以兩個(gè)端點(diǎn)均在V2中的邊的全體為邊集的G的子圖稱為V2導(dǎo)出的子圖，簡稱G的導(dǎo)出子圖。四、子圖和補(bǔ)圖12離散數(shù)學(xué)例：例

12、：它的真子圖G’和生成子圖G’’。13離散數(shù)學(xué)四、子圖和補(bǔ)圖定義設(shè)G＝為具有n個(gè)結(jié)點(diǎn)的簡單圖,從完全圖Kn中刪去G中的所有的邊而得到的圖稱為G的補(bǔ)圖(或G的補(bǔ))，記為。