圖論

　　數學的一個分支。它以圖為研究物件。圖論中的圖是若幹給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。因此這種圖中點的位置、線的長短曲直是無關緊要的。

　　圖論起源於著名的柯尼斯堡七橋問題。在柯尼斯堡(今蘇聯加裡寧格勒)的普萊格爾河上有七座橋，將河中的兩個島和河岸連結，如圖1所示，要尋找一條路線，經過每座橋隻一次而能回到出發點。17336年，L.歐拉用點表示陸地，用連結兩個點的線來表示橋，以圖2代替圖1，提出瞭第一個圖論問題：對給定的圖，是否存在一條路線，使得通過每條線正好一次而能回到起點。他證明瞭：當且僅當，圖是連通的以及每個點都與偶數條線相關聯時，才存在上述的路線(所謂的歐拉圈)。圖2雖然是連通的，但是每個點都與奇數條線相關聯，所以並不存在歐拉圈。

　　1847年，G.R.基爾霍夫在建立電網絡理論時，以圖G（圖4）代替電網絡N（圖3）

提出瞭“連通圖”、“樹”、“支撐樹”等基本概念。

　　1857年，A.凱萊在研究飽和碳氫化合物(C_nH_2n+2)同分異構體的數目時，獨立地提出瞭“樹”的概念。他把這一類化合物的計數問題，抽象為計算某類樹的個數問題。在這類樹中，要求關聯到每點的線的條數是1或4，樹上的點對應於一個氫原子或一個碳原子（圖5）。這一問題是圖的計數理論的起源。

　　1859年，W.R.哈密頓提出瞭一種叫做“旅行世界”的遊戲，把一個正十二面體的20個頂點看作20個城市(圖6)。要尋找一條沿著多面體的邊走的旅行路線，經過每個頂點正好一次，最後回到出發點，例如，1→2→3→…→20→1就是一種走法。將這個問題推廣到一般圖上，即對給定的圖是否存在一條路線，使得通過每個點正好一次，最後回到起點（所謂的哈密頓圈）。這就是哈密頓問題。由於運籌學、計算機科學以及編碼理論中的很多問題，都可化為哈密頓問題，從而引起瞭廣泛的註意，但是至今隻得到一些關於哈密頓圈存在的充分條件。例如，若關聯到每個點的線的條數不少於圖的點數的一半，則必存在哈密頓圈。

　　1936年，D.柯尼希寫出瞭第一本圖論的書。近三十年來，圖論的廣泛應用，促進瞭圖論自身的發展。例如，W.T.塔特等發展瞭由H.惠特尼首先提出的擬陣理論，C.伯奇等發展瞭超圖理論，P.愛爾特希等發展瞭極圖理論。此外，代數圖論、拓撲圖論等方面也有瞭很大的進展。

　　圖的定義　在圖論中，所謂圖G，是指由兩個集合V（G）和E（G）所組成的集合，並記作G=（V，E），其中

稱為點集，它的元素υ稱為 G的點； 稱為邊集，它的元素 e稱為 G的邊，是 V( G)的某些點對。若 e=(υ _i，υ _j)是一條邊，則點υ _i和υ _j稱為互相鄰接，或稱為 e的兩個端點。同時把邊 e和點υ _j(或υ _j)稱為互相關聯的。若兩條邊 e _h和 e _k都關聯於某一點υ，則邊 e _h和 e _k稱為互相鄰接。一個具有 n個點的圖，如其每一對點都是互相鄰接的，則此圖稱為完全圖，記作 K _n，如圖 7 中的 K ₅。若圖的點集 V能夠劃分成兩個子集 V ₁和 V ₂，使得圖中每條邊都關聯於 V ₁和 V ₂中的各一個點，則稱這種圖是一個二部圖。若從一個二部圖的 V ₁和 V ₂中各取一點所成的任何點對，都是圖的邊，則稱這個二部圖為完全二部圖。假設此時 V ₁中的點數為 r， V ₂中的點數為s，則記此完全二部圖為 K _{r ， s}如圖7中的 K _3，3。

　　關聯於某一點υ的邊的數目稱為該點的度，記作d(υ)。通常把各點的度中最小者記作δ，最大者記作Δ。

　　若兩個圖G＝(V，E)和G′=(V′，E′)中的V和V′之間存在保持鄰接性質的一一對應關系，則稱G和G′是同構的，記作G≌G′。例如，圖8

中的 G′和圖7中的 K _3，3是同構的。若兩個圖 G＝( V， E)和 G′=( V′， E′)有 ，則稱 G′是 G的一個子圖。從 G中減去點υ以及所有關聯於υ的邊後所得的子圖，記為 G-υ。從 G中減去邊 e（保留其端點）後所得的子圖，記為 G- e。

　　連通度　若一點序列

中相繼的兩點所構成的點對(υ _i，υ _{i +1})都是圖中的邊，則稱 p為一條聯結υ ₁和υ _k的鏈。而 υ ₁和υ _k稱為鏈 p的兩個端點。一條兩個端點相重合的鏈，稱為圈。一個圖，若任何兩點之間，至少存在一條聯系它們的鏈，則稱之為連通圖。否則，稱為不連通圖。一個無圈的連通圖稱為樹。設圖 G的子圖 G′含有 G的所有的點，如果 G′是樹，那麼稱 G′為 G的一個支撐樹。設 G不是完全圖，使 G變成不連通圖所需要減去的最少點數，稱為 G的點連通度，記作k( G)。對完全圖 K _p，取κ( K _p)= p-1。設 G至少含有兩個點，使 G變成不連通圖所需要減去的最少邊數，稱為 G的邊連通度，記作 λ( G)。對 G中任意兩條聯結點 u和υ的不同鏈，若除瞭 u和υ之外再沒有其他的公共點，則稱它為聯結 u和υ的兩條點不相交的鏈。若兩條聯結 u和υ的鏈沒有公共邊，則稱其為聯結 u和υ的兩條邊不相交的鏈。K.門傑於1927年獲得一個有關圖的點連通度的著名定理：圖 G中每對點之間至少有κ( G)條點不相交的鏈。對邊連通度也有相似的結果：圖 G中每對點之間至少有 λ( G)條邊不相交的鏈。這是1956年由L.R.福特和D.R.富爾克森發現的。

　　無關數與覆蓋數　若x是點（或邊）的一個子集合，其中的點(或邊)兩兩互不鄰接，則稱x為圖的一個點（或邊）無關集。在各點(或邊)無關集中，其所含的點（或邊）數達到最大者，稱為最大點（或邊）無關集，而它所含的點（或邊）數，稱為圖的點（或邊）無關數，記作β₀（或β₁）。點（或邊）的一個子集合S，若使得圖中任意一個邊（或點），至少與S中一個點（或邊）相關聯，則稱S為圖的一個點(或邊)覆蓋集。在各點(或邊)覆蓋集中，所含的點（或邊）數達到最小的覆蓋集，稱為最小點（或邊）覆蓋集，其所含的點（或邊）數稱為圖的點（或邊）覆蓋數，記作α₀(或α₁)。當G是二部圖時，設V₁中的點代表工人，V₂中的點代表工作，邊(u_i，υ_j)代表工人u_i熟悉工作υ_j，則G的邊無關數β₁表示能同時將工人安排到熟悉的工作上的最大數目。柯尼希於1931年獲得瞭一個關於圖的邊無關數的著名定理：若G是二部圖，則G的邊無關數等於點覆蓋數(即β₁=α₀)。對任意的連通圖G，T.加萊於1959年發現如下的簡明關系式：α₀+β₀=n;當δ＞0時，α₁+β₁=n，式中n是圖的點數。因此，當G是二部圖時，點無關數等於邊覆蓋數（即β₀=α₁）。對二部圖求參數α₀、α₁、β₀、β₁的問題，都可化為線性規劃問題。點（或邊）覆蓋集和點（或邊）無關集分別都對應於相應線性規劃問題的基本可行解。其中求α₀(或α₁)的線性規劃問題和求β₁(或β₀)的線性規劃問題，恰巧互為對偶規劃。因此，柯尼希定理是一個組合形式的對偶定理(見線性規劃)。門傑定理也可以通過線性規劃對偶定理來證明。假如一個邊無關集又是邊覆蓋集，則稱它是圖的一個1-因子。D.W.霍爾於1935年，首先對二部圖給出瞭存在1-因子的充分必要條件。1947年，塔特給出瞭任意圖存在1-因子的充分必要條件。在此基礎上，他還發展瞭圖的因子理論。

　　色數　圖的每一個點（或邊）染一種顏色，使得染同一種顏色的點（或邊）都互不鄰接所需要的最少顏色種數，稱為圖的點（或邊）色數。記作λ（或λ′）。顯然，邊色數不能小於圖的最大度，即λ′≥Δ。V.G.維津於1964年證明瞭λ′≤Δ+1。關於點色數，R.L.佈魯克斯在1941年已獲得如下的結果：若G是連通圖，它既不是一個奇數點的圈，也不是一個完全圖，則λ≤Δ。當G是二部圖時，λ′=Δ，λ≤2。假設V₁中的點代表工人，V₂中的點代表設備，而邊(u_i，υ_j)代表工人u_i要求使用設備υ_j一天。如果在同一天內，每個工人隻能使用一種設備，而每種設備隻能被一個人使用，那麼G的邊色數λ′表示最少要λ′天後才能滿足各工人對各種設備的要求。

　　平面圖　若用幾何的點和線來表示一個圖G的點和邊，在平面上畫出G時每兩條線，除端點外，內部互不相交，則稱G是一個平面圖。例如，印刷電路板上的線路圖就是一種平面圖。完全圖K₅和完全二部圖K_3，3是兩個分別使點數和邊數最少的非平面圖。平面圖的邊把平面劃分為若幹個連通的區域。每個連通的區域稱為平面圖的一個面。歐拉公式f₀-f₁+f₂=2反映瞭平面圖的點數f₀、邊數f₁及面數f₂的關系。設(u，υ)是G的一條邊，若在這條邊上增加一個新的點ω，用兩個邊(u，ω)和(ω，υ)來代替(u，υ)時，稱邊(u，υ)被ω細分。兩個圖，若能從同一個圖通過一系列的邊的細分而得到，則稱這兩個圖同胚。例如，任何兩個圈都同胚。圖9

中是兩個分別同胚於 K ₅和 K _3，3的圖。1930年，K.庫拉托夫斯基首先給出瞭平面圖的特征：一個圖 G是平面圖，當且僅當， G中不含有同胚於 K ₅或 K _3，3的子圖。這是圖論中著名的定理之一。平面圖的研究與四色問題以及拓撲圖論的發展密切相關。

　　重構問題　1929年，S.M.烏拉姆提出瞭一個猜想：設圖G＝(V，E)，H＝(V′，E′)，其中

， ，且 n≥3，對於 i=1，2，…， n，若子圖 G _i= G-υ _i與 H _i= H-υ _i ^′同構，則圖 G與 H同構，這是圖論中著名的重構猜想，尚未得到證明。

　　鄰接矩陣　對一個給定的n個點的圖，構造一個n×n矩陣A=(α_ij)，其中所有α_ii=0；對於i≠j，且點υ_i與υ_j互相鄰接，則取α_ij＝1；否則α_ii=0。該矩陣A=(α_ij)稱為圖的鄰接矩陣。代數圖論中很多結果是通過研究鄰接矩陣獲得的。基爾霍夫於1847年證明瞭如下的著名定理：矩陣M所有代數餘因子都相等，且其值等於G的支撐樹的數目，此處M=(m_ij)也是一個n×n矩陣，所有的m_ii＝d(υ_i)；當i≠j時，取m_ij＝-α_ij。

　　有向圖　若將圖G=(V，E)中E的元素都變成有序的點對（即給邊規定瞭方向），則稱此圖為定向圖。人們常見的物資流向圖、電流圖、計算程序框圖等都是屬於定向圖。定瞭向的邊e=(υ_i，υ_j)稱為弧。而 υ_i稱為弧的起點，υ_j稱為弧的終點。以 υ為起點的弧的數目，稱為υ的出度;以υ為終點的弧的數目，稱為υ的入度。若一點序列

中相繼兩點所構成的有序點對(υ _i，υ _{j +1})都是定向圖中的弧，則稱 p為一條以υ ₁為起點、υ _k為終點的定向鏈。一條起點和終點重合的定向鏈稱為定向圈。若一個支撐樹上的邊的定向滿足如下條件：有一個點的入度為零(稱之為根)，其餘各點的入度都是1，則此樹稱為定向樹(或樹形圖)。如圖 10 所示，圖中箭頭表示邊的定向。假如在任意兩個點υ _i與υ _j之間，允許存在弧(υ _i，υ _j)和(υ _j，υ _i)，則稱其為有向圖。

　　定向圖常常被用來描述元素間的某種偏序關系。例如表示人與人之間的上下級關系；比賽過程中的輸贏關系;生產過程中工序的先後順序；集合間的包含關系;狀態間的轉移關系；命題間的邏輯關系，等等。對有些物理和化學現象可以利用有向圖來表示變量之間的函數關系。在圖上，按一定的計算規則，就可直接求得問題的解答。在網絡分析中，圖論早已成為一種有力的工具。圖論和線性規劃相結合，產生瞭網絡流理論和組合最優化，而成為運籌學中應用較廣的兩個分支。

　　

參考書目

　F.Harary，Graph Theory，Addison-Wesley，ReadingMass.，1969.

　C.Berge，Graphs and Hypergraphs，North-Holland，Amsterdam，1973.

　J.A.Bondу and U.S.R.Murty，Graph Theory with Applications，Macmillan，London，1976.