第五章圖的基本概念圖論起源于1736年歐拉(Enler)的第一篇圖論論文,解決了“哥尼斯堡的七橋問題”。在哥尼斯堡的匹格河上有七座橋,如圖所示。第五章圖的基本概念圖論起源于1736年歐拉(Enler)的1當時人們熱衷于這樣的游戲：設想從任一個地方出發通過每座橋一次且僅一次后回到原地,這是否可能?但多次實踐都發現不行1727年歐拉的朋友向歐拉提出了這個問題是否有解？1736年歐拉用圖論的方法解決了這個問題,寫了第一篇圖論的論文,成為圖論的創始人。后來稱此問題為哥尼斯堡七橋問題。在圖a中,用邊表示橋,頂點表示島嶼和河的兩岸,便得到一個圖,如圖b所示。很顯然,通過哥尼斯堡七座橋中每一座一次且僅一次的問題等價于在圖5.13(b)中找一條閉鏈,使得它的每一邊出現一次且僅一次,也就是如何一筆畫的問題。當時人們熱衷于這樣的游戲：設想從任一個地方出發通過每座橋一次2但在此之后100年間，沒有大的進展。直到Kirchhoff(克希霍夫)用樹的理論解決了電網絡問題，1857年Cayler(凱萊)用統計不同構樹的方法來計算CnH2n+1同分異構體數目,這些結果引起了人們的重視,圖論的研究進入了一個發展時期,在此期間,出現了兩個著名的問題:四色問題和Hamilton回路問題,成為不少數學家的研究目標。但在19世紀后期和二十世紀初，圖論的研究再次處于停頓狀態。直到1920年,科尼格(Konig)攥寫了許多圖論方面的論文,在1936年科尼格(Konig)發表了第一本圖論書籍《有限圖與無限圖理論》，總結了200年來圖論研究的主要成果。但在此之后100年間，沒有大的進展。3此后的50年，圖論經歷了一場爆炸性的發展，成為數學科學中一門獨立的學科。主要分支有圖論、超圖理論、極值圖論、算法圖論、網絡圖論和隨機圖論等。幾十年來圖論在理論上和應用上都得到很大的發展,特別是在近30多年來由于計算機的廣泛應用而又得到飛躍的發展。在計算機科學、運籌學、化學、物理和社會科學等方面都取得了不少成果，對計算機學科中的操作系統研究、編譯技術、人工智能和計算機網絡等方面都有廣泛的應用。這里主要討論圖的基本概念和算法，為今后的學習和研究打下基礎。此后的50年，圖論經歷了一場爆炸性的發展，成為數學科學中一門45.1引言一、圖的定義：在集合論中離散對象之間的關系可以用關系圖來描述,這種圖就是圖論中所述的有向圖。定義5.1：設V是一個非空集,E是V上的二元關系,稱有序對(V,E)為有向圖,記為G=(V,E)或G(V,E)。V中的元素稱為頂點(或點),V稱頂點集。E是V×V的子集,E中的元素是有序對,稱為弧,E稱為弧集。5.1引言一、圖的定義：5例如有向圖G=(V,E),V={a,b,c,d,e,f,g},E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e),(f,f)},弧(a,b)表示從頂點a到頂點b的一條帶箭頭的線。對于弧(a,b)來講,在關系中a稱為有序對中的第一個元素,b稱為第二個元素。在圖論中，稱a為起點，b為終點。稱a與弧(a,b)關聯，b與弧(a,b)關聯。弧(c,c),(f,f)這種起點與終點相同的弧就稱為自環。在圖中，g與E中任何元素(弧)都不關聯，稱為孤立點。例如有向圖G=(V,E),V={a,b,c,d,e,f,g}6定義5.2：頂點a和b稱為弧(a,b)的端點,a為起點,b為終點。稱a和b與弧(a,b)關聯。若頂點a和b相同,則對應的弧(a,b)稱為自環。若V中某頂點與E中任何弧都不關聯,則該頂點稱為孤立點。與一條弧相關聯的兩個頂點稱為鄰接的或相鄰的。一頂點關聯于幾條弧,稱這些弧是弧鄰接或弧相鄰。例如上圖中a與b相鄰;c與d相鄰;(a,b)與(b,c)弧相鄰。定義5.2：頂點a和b稱為弧(a,b)的端點,a為起點,b為7在研究有向圖時,只考察它的頂點與弧的連接關系以及整個圖形所具有的性質。至于各頂點之間的相對位置及弧的長短曲直都是無關緊要的。對于有向圖，弧集中的元素都是有序對，若改成無序對，則就是下面介紹的無向圖。定義5.3：設V是一個非空集,E是以V中兩個元素組成的多重集為元素的集合,稱有序對(V,E)為無向圖,也記為G=(V,E)或G(V,E)。V中的元素稱為頂點或點,V稱為頂點集,E中的元素稱為邊,E稱為邊集。E中元素現在也是集合，由于可能出現{a,a}這種情況，所以說E中元素是V中兩個元素組成的多重集。該圖的V={v1,v2,v3,v4,v5,v6}，E={{v1,v2},{v1,v5,}，{v2,v2},{v2,v3},{v2,v4},{v2,v5},{v2,v5},{v3,v4},{v4,v5}}，邊{v1,v2}關聯于頂點a,b，而{v2,v2}這種關聯的兩個頂點是相同的稱為自環。而v6不關聯任何邊，也稱為孤立點。頂點v4同時關聯邊{v2,v4},{v3,v4},{v4,v5}，稱這些邊為邊鄰接另外在上圖中，邊{v2,v5}出現了兩次，象這種兩個頂點之間出現不止一條的邊稱為多重邊。在研究有向圖時,只考察它的頂點與弧的連接關系以及整個圖形所具8定義5.7：若圖G=(V,E)中,連結兩個頂點之間的邊可以不止一條這些邊稱為多重邊,則圖G稱為多重圖。無自環的非多重圖稱為簡單圖。邊集為空集的圖稱為零圖。只有一個頂點的圖稱為平凡圖。若G中每兩個頂點之間恰有一條邊,則稱G為完全圖。n個頂點的完全圖記為Kn。在定義5.7中,零圖是指沒有邊的圖,其每個頂點為孤立點,但頂點集V不能是空集。同樣在有向圖中，也可定義多重弧，多重有向圖和簡單有向圖。定義5.7：若圖G=(V,E)中,連結兩個頂點之間的邊可以9為了敘述方便起見,簡稱無向圖為圖,如果在圖(有向圖)中頂點標以名稱,如上圖中頂點標a,b,c,d,e,f,g,這樣的圖(有向圖)稱為標定圖(有向圖),否則稱為非標定圖(有向圖)。下面主要考慮標定圖。如果一個圖的頂點集和邊集是有限的,則稱該圖為有限圖,類似地定義有限有向圖。我們這里討論的圖和有向圖是指有限圖和有限有向圖。圖(有向圖)的最本質的內容就是頂點與邊(弧)的關聯關系。為了描述這一關系,現在引進一個重要的概念,即頂點的度數。為了敘述方便起見,簡稱無向圖為圖,如果在圖(有向圖)中頂點標10二、頂點度數定義5.4：設G=(V,E)是一個圖,頂點v所關聯的邊數(有自環情況要計算兩次),稱為頂點v的度數,記為d(v)。度數為1的頂點稱為懸掛點。度數為奇(偶)數的頂點稱為奇(偶)頂點。圖G中頂點的最小度數記為

(G),

(G)=minv

V{d(v)},簡記為

。在這里要注意：對于邊{a,b},在計算頂點a的度數和b的度數時分別都被用了一次，因此對于自環，此時b=a,{a,a},同樣要統計兩次。二、頂點度數11圖的基本概念ppt課件12證明：對每條邊來講，有兩個端點，在計算頂點度數時，每條邊被計算了兩次(極端情況，自環，同一端點同樣算了兩次)，所以圖中所有頂點度數之和為邊數的兩倍。證明：對每條邊來講，有兩個端點，13定理5.2:奇頂點有偶數個。定義5.5：設G是一個有向圖,以頂點v為起點的弧數稱為v的出度,記為d+(v);以頂點v為終點的弧數稱為v的入度,記為d-(v)。對于有向圖G中任一頂點v,d+(v)+d-(v)稱為頂點v的度數,也記為d(v)。定理5.2:奇頂點有偶數個。14作為弧，有進必有出，有出必有進，兩者平衡作為弧，有進必有出，有出必有進，兩者平衡15定理5.3:在有向圖中,所有頂點的入度之和等于所有頂點的出度之和。證明略。三、同構一個有向圖的弧以及弧所關聯的頂點位置變動后,可以畫出許多不同的圖形和形狀。例如圖的(a)和(b)這兩個有向圖,粗看起來是不同的,但仔細觀察以后,發現頂點之間一一對應,即a

D,b

B,c

A,d

E;弧之間也一一對應,即(a,b)

(D,B),(a,c)

(D,A),…，即這兩個有向圖除頂點所標名稱不同外,其結構相同,頂點數相同,弧數相同,并且頂點與弧的關聯關系保持不變,通常說這兩個有向圖是同構的。定理5.3:在有向圖中,所有頂點的入度之和等于所有頂點的出度16定義5.6：設G=(V,E)和G'=(V',E')是兩個有向圖,若存在雙射

:V→V'以及雙射

:E→E',使得對任何u,v

V,(u,v)

E,有

((u,v))=(

(u),

(v)),稱G和G'是同構的,記為G

G'。類似可以定義兩個無向圖的同構概念。定義5.6：設G=(V,E)和G'=(V',E')是兩個有向17圖5.4中兩個圖同構,即著名的彼得森(Petersen)圖。該圖的每個頂點度數均為3,稱為3-正則圖。一般,若圖的每個頂點度數均為r,則稱為r-正則圖。圖5.4中兩個圖同構,即著名的彼得森(Petersen)圖18研究同構的好處是，對于幾個同構的圖只要研究其中一個圖的性質，其他幾個圖的性質也就知道了。事實上同構關系是一個等價關系。定義5.8：設V是頂點集,E是邊集,f是V到實數的函數,g是E到實數集的函數,稱有序三元組G=(V,E,f)或G=(V,E,g)，以及有序四元組G=(V,E,f,g)為帶權圖。例如下圖就是邊上帶權為g的帶權圖G=(V,E,g),以后主要討論邊上帶權的帶權圖在有向圖中類似可以定義帶權有向圖。研究同構的好處是，對于幾個同構的圖只要研究其中一個圖的性質，19四、子圖在討論圖的性質時研究圖的局部結構是相當重要的,現介紹子圖的概念。定義5.9：設有圖G=(V,E),若在圖G'=(V',E')中,V'

V,E'

E且E'中邊所關聯的頂點在V'中,則稱G'為G的子圖。若V'=V,E'

E,則子圖G'=(V',E')稱為圖G的一個生成子圖。四、子圖20定義5.10：設有圖G=(V,E),設E'

E,以E'為邊集,E'中邊的端點全體為頂點集,構成的子圖稱為由E'導出的G的子圖,記為G(E'),又稱為G的邊導出子圖。設V'

V,以V'為頂點集,端點均在V'中所有邊的全體為邊集,構成的子圖稱為由V'導出的G的子圖,記為G(V'),又稱為G的導出子圖例如圖(d)是由G的邊{v1,v2},{v2,v4},{v4,v5}導出的子圖J,(e)是由G的頂點v1,v2,v4,v5導出的子圖H。定義5.10：設有圖G=(V,E),設E'E,以E'為邊21圖的基本概念ppt課件22簡單圖G=(V,E)的補圖是一個以V為頂點集的簡單圖,中兩個頂點相鄰當且僅當這兩個頂點在G中不相鄰。從圖G中刪去一個頂點v及其關聯的邊得到的子圖,記為G-v,或G-{v}。從圖G中刪去一邊e得到的子圖記為G-e,如圖所示。簡單圖G=(V,E)的補圖是一個以V為頂點集的簡單圖,中兩235.2路與回路一、路徑,鏈,路定義5.12：圖G的一個有限點邊交替序列(v0,e1,v1,e2,…,em,vm)，使得對1≤i≤m,ei的端點是vi-1和vi,稱該序列為一條路徑。邊e1,e2,…,em互不相同的路徑稱為鏈。m稱為該鏈的長度。頂點都不相同的鏈稱為路,m稱為該路的長度。v0=vm的路徑(或鏈)稱為閉路徑(或閉鏈)。除首尾兩點外其余頂點都不相同的閉鏈稱為回路。長度為偶(奇)數的路或回路稱為偶(奇)路或偶(奇)回路。5.2路與回路一、路徑,鏈,路24例如圖中(v2,e6,v5,e7,v2,e8,v4,e4,v5,e7,v2,e1,v1)是一條v2到v1的路徑;(v2,e6,v5,e7,v2,e1,v1)是一條v2到v1的路徑，由于邊不重復，所以是鏈;(v2,e8,v4,e4,v5,e5,v1)是一條v2到v1的路徑，邊不重復，所以是鏈，又因為點也不重復，所以是一條路。有時點邊交替序列可用邊序列或點序列代替。在圖中(v2,e6,v5,e7,v2,e8,v4,e4,v5,e7,v2)是一條閉路徑;(v1,e1,v2,e6,v5,e7,v2,e8,v4,e4,v5,e5,v1)是一條閉路徑，由于邊不重復，是一條閉鏈;(v1,e1,v2,e8,v4,e4,v5,e5,v1)是一條閉路徑，由于邊不重復，是一條閉鏈，除首尾兩點外，點不重復，是回路。(v2,e6,v5,e7,v2)也是回路。例如圖中(v2,e6,v5,e7,v2,e8,v4,e4,25一條路也是一條鏈,一條回路也是一條閉鏈,并且自環和兩條多重邊都自成一條回路一條回路上每個頂點的度數為2,一條路除起點和終點外,每個頂點的度數也為2。定理5.4：若圖G中每個頂點度數至少為2,則G包含一條回路。證明：若圖G包含自環或多重邊,則定