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

圖的術(shù)語度數(shù)完全圖補圖圖的同構(gòu)7-1圖的基本概念1定義一個圖是一個三元組<V(G),E(G),φG>,簡記為G＝<V,E>，其中：V＝{v1,v2,v3,…,vn}是一個非空集合,vi(i＝1,2,3,…,n)稱為結(jié)點,簡稱點,V為結(jié)點集；E＝{e1,e2,e3,…,em}是一個有限集，ei(i＝1,2,3,…,m)稱為邊,E為邊集，E中的每個元素都有V中的結(jié)點對（有序偶或無序偶）與之對應(yīng)。一、圖的術(shù)語2離散數(shù)學(xué)圖的術(shù)語若邊e與結(jié)點無序偶(u，v)相對應(yīng)，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e的兩個端點；若邊e與結(jié)點有序偶<u，v>相對應(yīng)，則稱邊e為有向邊(或弧)，記為e＝<u，v>，這時稱u是邊e的始點(或弧尾)，v是邊e的終點(或弧頭)，統(tǒng)稱為e的端點；在一個圖中，關(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é)點的零圖稱為平凡圖；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é)點v(vV)關(guān)聯(lián)的邊的條數(shù)，稱為該結(jié)點的度數(shù)，記為deg(v)；定義在有向圖G＝<V，E>中，以結(jié)點v(vV)為始點引出的邊的條數(shù)，稱為該結(jié)點的引出度數(shù),簡稱出度,記為deg+(v)；以結(jié)點v(vV)為終點引入的邊的條數(shù)，稱為該結(jié)點的引入度數(shù)，簡稱入度,記為deg-(v)；而結(jié)點的出度和入度之和稱為該結(jié)點的度數(shù)，記為deg(v)，即deg(v)＝deg+(v)+deg-(v)；δ(G)最小度，Δ(G)最大度定義在圖G＝<V，E>中，對任意結(jié)點vV，若度數(shù)deg(v)為奇數(shù)，則稱此結(jié)點為奇度數(shù)結(jié)點，若度數(shù)deg(v)為偶數(shù)，則稱此結(jié)點為偶度數(shù)結(jié)點。二、度數(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é)點的度數(shù)的總和等于邊數(shù)的兩倍，即：在有向圖G＝<V，E>中，所有結(jié)點的出度之和等于所有結(jié)點的入度之和，所有結(jié)點的度數(shù)的總和等于邊數(shù)的兩倍，即：11離散數(shù)學(xué)三、完全圖定義在圖G＝<V，E>中，若所有結(jié)點的度數(shù)均有相

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

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

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