離散數(shù)學(xué)圖論課件

圖的術(shù)語度數(shù)完全圖補(bǔ)圖圖的同構(gòu)7-1圖的基本概念1定義一個(gè)圖是一個(gè)三元組<V(G),E(G),φG>,簡(jiǎn)記為G＝<V,E>，其中：V＝{v1,v2,v3,…,vn}是一個(gè)非空集合,vi(i＝1,2,3,…,n)稱為結(jié)點(diǎn),簡(jiǎ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)對(duì)（有序偶或無序偶）與之對(duì)應(yīng)。一、圖的術(shù)語2離散數(shù)學(xué)圖的術(shù)語若邊e與結(jié)點(diǎn)無序偶(u，v)相對(duì)應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)；若邊e與結(jié)點(diǎn)有序偶<u，v>相對(duì)應(yīng)，則稱邊e為有向邊(或弧)，記為e＝<u，v>，這時(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)，否則稱為不鄰接的；關(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)的零圖稱為平凡圖；3離散數(shù)學(xué)(a)例：(b)(c)(d)例：5離散數(shù)學(xué)(e)(f)(g)(h)例：例：6離散數(shù)學(xué)(i)(j)(k)(l)例：例：7離散數(shù)學(xué)定義在無向圖G＝<V，E>中，與結(jié)點(diǎn)v(vV)關(guān)聯(lián)的邊的條數(shù)，稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)；定義在有向圖G＝<V，E>中，以結(jié)點(diǎn)v(vV)為始點(diǎn)引出的邊的條數(shù)，稱為該結(jié)點(diǎn)的引出度數(shù),簡(jiǎn)稱出度,記為deg+(v)；以結(jié)點(diǎn)v(vV)為終點(diǎn)引入的邊的條數(shù)，稱為該結(jié)點(diǎn)的引入度數(shù)，簡(jiǎn)稱入度,記為deg-(v)；而結(jié)點(diǎn)的出度和入度之和稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)，即deg(v)＝deg+(v)+deg-(v)；δ(G)最小度，Δ(G)最大度定義在圖G＝<V，E>中，對(duì)任意結(jié)點(diǎn)vV，若度數(shù)deg(v)為奇數(shù)，則稱此結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn)，若度數(shù)deg(v)為偶數(shù)，則稱此結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。二、度數(shù)9離散數(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；例：10離散數(shù)學(xué)定理1.在無向圖G＝<V，E>中，所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：在有向圖G＝<V，E>中，所有結(jié)點(diǎn)的出度之和等于所有結(jié)點(diǎn)的入度之和，所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：11離散數(shù)學(xué)三、完全圖定義在圖G＝<V，E>中，若所有結(jié)點(diǎn)的度數(shù)均有相

同度數(shù)d，則稱此圖為d次正則圖。定義一個(gè)(n，m)(n2)的簡(jiǎn)單無向圖，若它

為n-1次正則圖，則稱該(n，m)圖為無向簡(jiǎn)單

完全圖，簡(jiǎn)稱完全圖,記為Kn。有向完全圖定理設(shè)無向完全圖G有n個(gè)頂點(diǎn)，則G有n(n-1)/2條邊。13離散數(shù)學(xué)例：例：如圖(a)、(b)、(c)、(d)所示，它們分別是無向的簡(jiǎn)單完全圖K3，K4，K5和有向的簡(jiǎn)單完全圖K3。14離散數(shù)學(xué)定義設(shè)有圖G＝<V，E>和圖G1＝<V1，E1>，若G和G1滿足：若V1V，E1E，則稱G1是G的子圖，記為G1G；若G1G，且G1G(即V1V或E1E)，則稱G1是G的真子圖，記為G1G；定義若V1＝V，E1E，則稱G1是G的生成子圖；定義若V2V，V2Φ，以V2為結(jié)點(diǎn)集，以兩個(gè)端點(diǎn)均在V2中的邊的全體為邊集的G的子圖稱為V2導(dǎo)出的子圖，簡(jiǎn)稱G的導(dǎo)出子圖。四、子圖15離散數(shù)學(xué)定義設(shè)G＝<V，E>為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,從完全圖Kn中刪去G中的所有的邊而得到的圖稱為G的補(bǔ)圖(或G的補(bǔ))，記為。定義Ｇ＝<Ｖ，Ｅ>是圖，Ｇ’＝<Ｖ’，Ε’>是Ｇ的子圖，Ｅ”＝Ｅ－Ｅ’，Ｖ”是Ｅ”中邊所關(guān)聯(lián)的所有頂點(diǎn)集合，則Ｇ”＝<Ｖ”，Ｅ”>稱為Ｇ’關(guān)于Ｇ的相對(duì)補(bǔ)圖。 關(guān)于完全圖的子圖的補(bǔ)圖稱為此子圖的絕對(duì)補(bǔ)圖。五、補(bǔ)圖17離散數(shù)學(xué)例：例：在下圖(a)、(b)、(c)、(d)中，(a)與(b)是互為補(bǔ)圖；(c)和(d)是互為補(bǔ)圖。18離散數(shù)學(xué)六、圖的同構(gòu)例:如下圖所示，圖(a)、圖(b)、圖(c)和圖(d)所表示的圖形實(shí)際上都是一樣的。19離散數(shù)學(xué)例：例：如圖(a)、(b)所示的兩個(gè)圖G＝<V,E>和G1＝<V1,E1>，證明G≌G1。解：定義函數(shù)g:V→V1，滿足g(vi)＝vi’(i＝1，2，3