圖論(數(shù)據(jù)庫)

時間：2022-11-24 06:30:01 | 來源：信息時代

時間：2022-11-24 06:30:01 來源：信息時代

    圖論 : 數(shù)學中以圖為研究對象的一個分支。圖論中的圖是由若干個點及一些連接兩點的線構(gòu)成的圖形,其中點表示事物,連接兩點的線表示對應的兩個事物之間的某種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題: 18世紀中葉,普魯士的哥尼斯堡有一條普雷哥爾河,河中有兩個島嶼。在河的兩岸與兩個島嶼之間有七座橋,如圖1所示。

圖1 哥尼斯堡七橋

圖2 七橋問題圖表示

當時人們熱衷于一個難題: 一個人怎樣不重復地走完七橋,最后回到出發(fā)地點? 1736年,瑞士數(shù)學家Leonhard Euler發(fā)表論文,證明哥尼斯堡七橋問題無解,即一個人不可能不重復地走完七橋回到出發(fā)點。Euler研究的方法是,用4個點A、B、C、D分別表示兩岸和兩個島嶼,用兩點之間的連線表示對應兩塊陸地之間的橋,如圖2所示。由于這一開創(chuàng)性的工作,后人把Euler尊為圖論的鼻祖,稱1736年為圖論的元年。19世紀中葉,在電網(wǎng)絡和飽和碳氫化合物的研究中引入連通圖、樹等概念。1859年,William Rowan Hamilton給出 “周游世界”的游戲,把一個正12面體的20個頂點看作20座城市,要尋找一條沿著多面體的邊走的旅行路線,恰好經(jīng)過每一個頂點一次,最后回到出發(fā)點,見圖3。這就是所謂的哈密頓回路。到了20世紀中期以后,由于科學技術(shù)的發(fā)展,特別是計算機科學技術(shù)的迅猛發(fā)展,圖論在許多領(lǐng)域中得到廣泛的應用,自身也得到空前地發(fā)展,成為一個十分活躍的研究領(lǐng)域。

圖3 周游世界問題

1. 圖的基本概念
圖是由若干個點和一些連接兩點的線構(gòu)成的圖形,在這里點的位置、線的長短及曲直都是無關(guān)緊要的,點稱作頂點,線稱作邊。圖有有向圖與無向圖之分。無向圖不考慮邊的方向,稱作無向邊,簡稱邊;有向圖的邊要考慮方向,稱作有向邊,見圖4和圖5。

圖4 無向圖

圖5 有向圖

有關(guān)的形式定義:
(1)無向圖:設V={v₁,v₂,…,v_n},E={e₁,e₂,…,e_m},n≥1,m≥0,其中每一個v_j表示一個頂點,e_k＝(v_i,v_j)表示連接v_i和v_j的一條邊,v_i和v_j稱作e_k的端點。在這里,(v_i,v_j)＝(v_j,v_i),稱作無序?qū)?即e_k是沒有方向的。我們稱G=<V,E>為無向圖,簡稱圖,其中V是G的頂點集,E是邊集。注意:e_k的兩個端點可以是相同的,此時稱作環(huán),如圖4中的e₁＝(a,a)。允許兩條和兩條以上的邊有兩個相同的端點,此時稱這些邊為平行邊,并稱平行邊的條數(shù)為重數(shù)。如圖4中e₂、e₃,是兩條平行邊。既無平行邊也無環(huán)的圖稱為簡單圖。有n個頂點的圖稱為n階圖。若n=1且E=∅, 即只有一個頂點沒有邊的圖稱為平凡圖。若有一條邊e_k＝(v_i,v_j),則稱頂點v_i與v_j相鄰,邊e_k與頂點v_i和v_j相關(guān)聯(lián)。無邊關(guān)聯(lián)的頂點稱為孤立點。稱有共同端點的兩條邊(v_i,v_j)與(v_j,v_k)相鄰。
(2)有向圖:與無向圖類似,只是每條邊都是有方向的,用兩個端點的有序?qū)Ρ硎緀_k＝<v_i,v_j>,其中v_i是e_k的始點,v_j是e_k的終點。在有向圖中,只有當兩條有向邊有相同的始點和終點時才稱為平行邊,如圖5中的e₃和e₄是平行邊,而e₆和e₇不是平行邊。
(3)頂點的度數(shù):在無向圖中,頂點v作為邊的端點的總次數(shù)稱作v的度數(shù),記作d(v)。類似地,在有向圖中,頂點v作為邊的端點的總次數(shù)稱作為v的度數(shù),記作d(v)。又稱v作為邊的始點的總次數(shù)為v的出度,記作d⁺(v),v作為邊的終點的總次數(shù)為v的入度,記作d^-(v)。d⁺(v)+d^-(v)=d(v)。注意:一個頂點作為環(huán)的端點要計算2次; 同樣地,作為平行邊的端點也要重復計算。無向圖G中頂點度數(shù)的最大值和最小值分別稱為G的最大度數(shù)和最小度數(shù),分別記作Δ(G)和δ(G)。類似地,有向圖D中頂點度數(shù)的最大值和最小值分別稱為D的最大度數(shù)和最小度數(shù),分別記作Δ(D)和δ(D); D中頂點出度的最大值和最小值分別稱為D的最大出度和最小出度,分別記作Δ⁺(D)和δ⁺(D); D中頂點入度的最大值和最小值分別稱為D的最大入度和最小入度,分別記作Δ^-(D)和δ^-(D)。在無向簡單圖G中,Δ(G)≤n-1(n為G的階數(shù))。例如,在圖4所示的無向圖G中,d(a)=5,d(c)=2,d(d)=0,Δ(G)=5,δ(G)=0。在圖5所示的有向圖D中,d(a)=5,d⁺(a)=3,d^-(a)=2,Δ(D)=5,Δ⁺(D)=3,Δ^-(D)=2,δ⁺(D)=1,δ^-(D)=1。
2. 握手定理
在任何無向圖和有向圖中,所有頂點的度數(shù)之和等于邊數(shù)的2倍,且奇度數(shù)頂點的個數(shù)為偶數(shù)。在有向圖中,所有頂點的出度之和等于所有頂點的入度之和,且都等于邊數(shù)。
3. 圖的同構(gòu)
設G₁＝<V₁,E₁>和G₂＝<V₂,E₂>為兩個無向圖,若存在雙射函數(shù)f:V₁→V₂(見函數(shù))使得∀v_i, v_j∈V₁,(v_i,v_j)∈E₁當且僅當(f(v_i),f(v_j))∈E₂,且當是平行邊時(v_i,v_j)與(f(v_i),f(v_j))的重數(shù)相同,則稱G₁與G₂同構(gòu),記做G₁＝G₂。類似可定義有向圖之間的同構(gòu)。例如,圖6所示的兩個圖同構(gòu)。

圖6 兩個同構(gòu)的圖

4.完全圖
任意兩個頂點之間都有一條邊的無向簡單圖。n階完全圖記為K_n。K₃,K₄與K₅如圖7所示。設D為n階有向簡單圖,若D中任何兩個不同的頂點之間均有兩條方向相反的邊,則稱D為有向完全圖。

圖7 無向完全圖

5.正則圖
每個頂點度數(shù)都為k的無向簡單圖稱為k正則圖。
6.子圖
設G=<V, E>, G′=<V′,E′>, 若V′V, E′E,則稱G′為G的子圖, 記為G′G。又當G′G, 且V′⊂V或E′⊂E時, 稱G′為G的真子圖。 又若V′=V時,稱G′為G的生成子圖。
7.補圖
設G=〈V,E〉為無向簡單圖, 令＝{(u, v)|u,v∈V,u≠v且(u,v)∉E},稱＝〈V,〉為G的補圖。例如,圖8中的兩個圖互為補圖。

圖8 補圖

8.通路與回路
在無向圖中,設Γ=v₀e₁v₁e₂…e_tv_t是頂點與邊的交替序列且v_i-1與v_i是e_i的端點(1≤i≤t),稱Г為v₀到v_t的通路。Г中的邊數(shù)稱為Г的長度。若v₀＝v_t則稱Г為回路。除首尾兩點外,所有邊都不相同的通路稱為簡單通路,所有邊都不相同的回路稱為簡單回路。所有頂點和所有邊都不相同的通路稱為初級通路或路徑。所有頂點和所有邊都不相同的回路稱為初級回路或圈。有邊重復出現(xiàn)的通路稱為復雜通路,有邊重復出現(xiàn)的回路稱為復雜回路。
9. 圖的連通性
若無向圖G中任何兩個頂點之間均有通路,則稱G是連通圖,否則稱G是非連通圖。設G′是G的連通子圖,如果在G′中再任意添加G中另外一個頂點或另外一條邊,所得到的圖就成為非連通的,則稱G′是G的極大連通子圖。G的極大連通子圖稱為G的連通分支。連通圖只有一個連通分支,非連通圖的連通分支數(shù)大于等于2。
在有向圖D中,去掉所有有向邊的箭頭(即,把有向邊改成無向邊)所得到的無向圖稱作有向圖的基圖。若D的基圖是連通的,則稱D是弱連通的;若D中任意兩個頂點之間至少有一個頂點到另一個頂點有通路,則稱D是單向連通的; 若D中任何兩個頂點相互之間都有通路,則稱D是強連通的。
10.二部圖
設G=〈V,E〉為無向圖,若能將V分成V₁和V₂,使得V=V₁∪V₂,V₁∩V₂＝∅, 而且G的每條邊的一個端點屬于V₁,另一個端點屬于V₂,則稱G為二部圖。又若,簡單二部圖G中V₁中每個頂點均與V₂中所有頂點相鄰,則稱G為完全二部圖,記為K_r,s,其中r和s分別為V₁和V₂中的頂點數(shù)。例如,圖9是K_2,3和K_3,3。

圖9 完全二部圖

11. 歐拉圖
圖(無向圖或有向圖)中經(jīng)過每條邊一次且僅一次的回路稱作歐拉回路。有歐拉回路的圖稱為歐拉圖。無向圖為歐拉圖當且僅當它是連通的且沒有奇度數(shù)頂點。有向圖為歐拉圖當且僅當它是強連通的且每個頂點的入度等于出度。例如,圖10所示的圖為一個歐拉圖,cbahgfedbhfdc為一條歐拉回路。
不難看出,在哥尼斯堡七橋問題中“不重復地走完七橋回到出發(fā)點的路線”應該是圖2中的一條歐拉回路,而這個圖的4個頂點的度數(shù)都是奇數(shù),因此不存在歐拉回路,所以哥尼斯堡七橋問題無解。

圖10 歐拉圖

圖11 平面圖

12. 哈密頓圖
圖G(無向圖或有向圖)中恰好經(jīng)過每個頂點一次的回路稱作哈密頓回路。有哈密頓回路的圖稱為哈密頓圖。到目前為止,還沒有找到判別一個圖是否是哈密頓圖的好方法,哈密頓圖的判別問題是NP完全的(見計算復雜性理論)。哈密頓的周游世界問題就是要在圖3中找一條哈密頓回路。這個圖是哈密頓圖,其中ABCDEFGHIJKLMNO PQRSTA為一條哈密頓回路。
13. 平面圖
能夠畫在平面上使得除在頂點處外沒有邊相交的無向圖稱為平面圖。例如,圖11所示的圖為一個平面圖。
14. 圖的矩陣表示
圖的一種表示方法。
15.無向圖的關(guān)聯(lián)矩陣
設無向圖G=<V,E>,其中V={v₁,v₂,…,v_n},E={e₁,e₂,…,e_n}。令

則稱[m_ij]_n×m為G的關(guān)聯(lián)矩陣。例如,圖12所示無向圖G的關(guān)聯(lián)矩陣為

圖12 無向圖G

16.有向圖的關(guān)聯(lián)矩陣
設無環(huán)有向圖D=〈V,E〉,V={v₁,v₂,…,v_n},E={e₁,e₂,…,e_n}。令

則稱[m_ij]_n×m為D的關(guān)聯(lián)矩陣。例如,圖13所示有向圖D的關(guān)聯(lián)矩陣為

圖13 無環(huán)有向圖D

17.無向圖的相鄰矩陣
設無向簡單圖G=<V,E>,其中V={v₁,v₂,…,v_n},令a_ii＝0,

則稱[a_ij]_n×m為G的相鄰矩陣。例如,圖14所示的無向圖的相鄰矩陣為

圖14 無向簡單圖G

無向圖相鄰矩陣的性質(zhì):
(1)A(G)是對稱的。
(2)第i行元素之和為頂點v_i的度數(shù)。
(3)A(G)中所有元素之和等于邊數(shù)的2倍。
18.有向圖的鄰接矩陣
設有向圖D=〈V,E〉,V={v₁,v₂,…,v_n},令a_ij為從頂點v_i到v_j的有向邊的條數(shù)(i,j=1,2,…,n),則稱[a_ij]_n×n為D的鄰接矩陣。例如,圖15所示有向圖D的鄰接矩陣為

圖15 有向圖D

有向圖鄰接矩陣的性質(zhì):
(1)第i行元素之和為頂點v_i的出度,第j列元素之和為頂點v_j的入度。
(2)A(D)中所有元素之和為圖中的邊數(shù),亦即圖中長度為1的通路數(shù),其中對角線元素之和為圖中長度為1的回路數(shù)(即環(huán)數(shù))。
(3)A(D)的k次冪A^k(D)中的元素a_ij^k(i≠j)為v_i到v_j長度為k的通路數(shù),而a_ij^k為v_i到自身長度為k的回路數(shù),A^k(D)中的所有元素之和為D中長度為k的通路總數(shù),其中A^k(D)的對角線元素之和為D中長度為k的回路數(shù)。
19.有向圖的可達矩陣
設有向圖D=〈V,E〉,V={v₁,v₂,…,v_n},令p_ij＝1,當i≠j時,

則稱P(D)=[p_ij]_n×n為D的可達矩陣。圖15所示有向圖的可達矩陣為