【正文】 離散數(shù)學(xué) 1 一、圖 定義 一個 圖 是一個三元組 V(G),E(G),φ G,簡記為G＝ V,E。 71 圖的基本概念 其中： 1) V＝ {v1,v2,v3,… ,vn}是一個非空集合 ,vi(i＝1,2,3,… ,n)稱為 結(jié)點 ,簡稱 點 ,V為 結(jié)點集 ； 2) E＝ {e1,e2,e3,… ,em}是一個有限的集合， ei(i＝1,2,3,… ,m)稱為 邊 ,E為 邊集 ， E中的每個元素都有 V中的結(jié)點對（有序偶或無序偶）與之對應(yīng)。 例 離散數(shù)學(xué) 2 圖的術(shù)語 圖的術(shù)語 ? 若邊 e與結(jié)點無序偶 (u， v)相對應(yīng)，則稱邊 e為 無向邊 ,記為 e＝ (u， v)，這時稱 u， v是邊 e的兩個 端點 ； 2) 若邊 e與 結(jié)點 有偶 u， v相對應(yīng) ， 則稱邊 e為 有向邊 (或 弧 )，記為 e＝ u， v， 這時稱 u是邊 e的 始點 (或 弧尾 ).v是邊 e的 終點 (或 弧頭 )， 統(tǒng)稱為 e的 端點 ； 3) 在一個圖中 ， 關(guān)聯(lián)結(jié)點 vi和 vj的邊 e， 無論是有向的還是無向的 ， 均稱邊 e與結(jié)點 vI和 vj相關(guān)聯(lián) ， 而 vi和 vj稱為 鄰接點 ，否則稱為 不鄰接的 ； 離散數(shù)學(xué) 3 續(xù)： 續(xù)： 4) 關(guān)聯(lián)于同一個結(jié)點的兩條邊稱為 鄰接邊 ； 5) 圖中關(guān)聯(lián)同一個結(jié)點的邊稱為 自回路 (或 環(huán) )； 6) 圖中不與任何結(jié)點相鄰接的結(jié)點稱為 孤立結(jié)點 ； 7) 僅由孤立結(jié)點組成的圖稱為 零圖 ； 8) 僅含一個結(jié)點的零圖稱為 平凡圖 ； 9) 含有 n個結(jié)點 、 m條邊的圖稱為 (n， m)圖 ； 離散數(shù)學(xué) 4 續(xù)： 續(xù)： ? 每條邊都是無向邊的圖稱為 無向圖 ； ? 每條邊都是有向邊的圖稱為 有向圖 ； ? 有些邊是無向邊 ， 而另一些是有向邊的圖稱為 混合圖 。 ? 在有向圖中 ， 兩個結(jié)點間 (包括結(jié)點自身間 )若有同始點和同終點的幾條邊 ， 則這幾條邊稱為 平行邊 ， 在無向圖中 ，兩個結(jié)點間 (包括結(jié)點自身間 )若有幾條邊 ， 則這幾條邊稱為 平行邊 ， 兩結(jié)點 vi， vj間相互平行的邊的條數(shù)稱為邊(vi， vj)或 vi， vj的 重數(shù) ； ? 含有平行邊的圖稱為 多重圖 。 非多重圖稱為 線圖 ；無自回路的線圖稱為 簡單圖 。 離散數(shù)學(xué) 5 (a) 例： (b) (c) (d) 例： 離散數(shù)學(xué) 6 (e) (f) 例： 例： (g) 離散數(shù)學(xué) 7 二、度數(shù) 定義 在無向圖 G＝ V， E中，與結(jié)點 v(v?V)關(guān)聯(lián)的邊的條數(shù)，稱為該結(jié)點的 度數(shù) ，記為 deg(v)； 二、度數(shù) 定義 在有向圖 G＝ V， E中 ， 以結(jié)點 v(v?V)為始點引出的邊的條數(shù) ， 稱為該結(jié)點的 引出度數(shù) ,簡稱 出度 ,記為 deg+(v)；以結(jié)點 v(v?V)為終點引入的邊的條數(shù) ， 稱為該結(jié)點的 引入度數(shù) ， 簡稱 入度 ,記為 deg(v)；而結(jié)點的出度和入度之和稱為該結(jié)點的 度數(shù) ， 記為 deg(v) ， 即 deg(v) ＝deg+(v)+deg(v)； δ (G)最小度 ， Δ (G)最大度 定義 在圖 G＝ V， E中 ， 對任意結(jié)點 v?V， 若度數(shù) deg(v)為奇數(shù) ， 則稱此結(jié)點為 奇度數(shù)結(jié)點 ， 若度數(shù) deg(v)為偶數(shù) ， 則稱此結(jié)點為 偶度數(shù)結(jié)點 。 離散數(shù)學(xué) 8 例： 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； 例： 離散數(shù)學(xué) 9 定理 定理 G＝ V， E中 ， 則所有結(jié)點的度數(shù)的總和等于邊數(shù)的兩倍 ， 即： ；m2)vd e g (Vv???，m)v(d e g)v(d e gVvVv?? ??????2. 在有向圖 G＝ V， E中，則所有結(jié)點的出度之和等于所有結(jié)點的入度之和，即： 在所有圖中， 度數(shù)為奇數(shù)的結(jié)點個數(shù)為偶數(shù) . 離散數(shù)學(xué) 10 定理 。 證明 V1＝ {v|v?V且 deg(v)＝奇數(shù) }， V2＝ {v|v?V且deg(v)＝偶數(shù) }。顯然， V1∩V 2＝ Φ，且 V1∪V 2＝ V，于是有： 。m2)vd e g ()vd e g ()vd e g (21 VvVvVv??? ??????由于上式中的 2m和偶度數(shù)結(jié)點度數(shù)之和均為偶數(shù)，因而也為偶數(shù)。于是 |V1|為偶數(shù) (因為 V1中的結(jié)點 v之 deg(v)都為奇數(shù) )，即奇度數(shù)的結(jié)點個數(shù)為偶數(shù)?！? 離散數(shù)學(xué) 11 三、完全圖 三、完全圖 定義 在圖 G＝ V， E中，若所有結(jié)點的度數(shù)均有相 同度數(shù) d，則稱此圖為 d次正則圖。 定義 一個 (n， m)(n?2)的簡單無向圖，若它 為 n1次正則圖，則稱該 (n， m)圖為 無向簡單 完全圖 ， 簡稱 完全圖 ,記為 Kn。 有向完全圖 定理 設(shè)無向完全圖 G有 n個頂點，則 G有 條邊。 離散數(shù)學(xué) 12 四、子圖和補圖 定義 設(shè)有圖 G＝ V， E和圖 G1＝ V1， E1，若 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＝ V， E和圖 G2＝ V2， E2，若 V2?V， V2?Φ ，以 V2為結(jié)點集，以兩個端點均在 V2中的邊的全體為邊集的 G的子圖稱為 V2導(dǎo)出的子圖 ，簡稱 G的導(dǎo)出子圖 。 四、子圖和補圖 離散數(shù)學(xué) 13 例： 例： 它的真子圖 G’和生成子圖 G’’。 離散數(shù)學(xué) 14 四 、 子圖和補圖 定義 設(shè) G＝ V， E為具有 n個結(jié)點的簡單圖 ,從完全圖 Kn中刪去 G中的所有的邊而得到的圖稱為 G的 補圖 (或 G的 補 )， 記為 。 關(guān)于完全圖的子圖的補圖稱為此子圖的 絕對補圖 。 定義 Ｇ＝ Ｖ ， Ｅ 是圖 ， Ｇ ’ ＝ Ｖ ’ ， Ε ’是Ｇ的子圖 ，Ｅ ” ＝Ｅ－Ｅ ’ ， Ｖ ” 是Ｅ ” 中邊所關(guān)聯(lián)的所有頂點集合 ，則Ｇ ” ＝ Ｖ ” ， Ｅ ” 稱為Ｇ ’ 關(guān)于Ｇ的 相對補圖 。 四、子圖和補圖 G離散數(shù)學(xué) 15 例： 例： 求下圖的補圖。 離散數(shù)學(xué) 16 五、圖的同構(gòu) 五、圖的同構(gòu) 例 : 如下圖 (