氧化還原法

[拼音]：tulun

[英文]：graph theory

研究節點和邊組成的圖形的數學理論和方法，為運籌學的一個分支。圖論的基本元素是節點和邊（也稱線、弧、枝），用節點表示所研究的物件，用邊表示研究物件之間的某種特定關係。因此，圖論可用節點和邊組成的圖形及其有關的理論和方法來描述、分析和解決各種實際問題，諸如物理學、化學、生物學、管理科學、計算方法和工程技術等領域的有關問題。圖論與組合數學、線性規劃、群論、矩陣論、概率論、數值分析等數學分支有密切的關係。

發展簡史

1736年瑞士數學家L.尤拉發表圖論的第一篇論文,解決了著名的柯尼斯堡七橋問題,因此通常認為尤拉是圖論的創始人。流經東普魯士的柯尼斯堡的普萊格爾河上有七座橋，將河中的島和河岸連線起來（圖1）。長期以來人們在議論能否從A、B、C、D這四塊陸地中的任何一塊開始,經過所有的橋一次且僅一次，最後回到原來出發的這塊陸地。當時，尤拉將每塊陸地用一個點來代替，將每座橋用連線相應的兩個點的一條邊來代替,從而得到了一個“圖”（圖2）。尤拉對於一般的圖提出了一個普遍的判別法則：要從圖中一點出發，經過所有的邊一次且僅一次，能回到原來的出發點，則這個圖必須是連通的，且每個點都必須與偶數條邊相關聯。顯然,圖2中的各點都是連通的，但每個點都不是與偶數條邊相連線，因此七橋問題不可能有解。1845年，德國物理學家G.R.基爾霍夫為了解決一類線性聯立方程組而建立“樹”理論。他把電網路和其中的電阻、電容和電感等抽象化，用一個只有點和邊組成的組合結構來代替電網路，而不指明每條邊所代表的電器元件種類,這樣就可以方便地對方程組進行求解。圖3為一電網路(N)及其基本圖(G)和它的一個生成樹(T)。 1852年F.格思裡在對地圖著色時發現,無論多麼複雜的地圖,只要用四種顏色就能將相鄰區域區分開來。這就是所謂“四色猜想”。經過百餘年的努力，直到1976年才由K.阿佩爾和W.赫肯藉助電子計算機證明了四色定理。1856年，W.R.哈密頓在給 R.L.格雷夫斯的信中提出一個遊戲：用正十二面體上20個頂點表示20個城市，要求遊戲者沿著各邊行走，走遍每個城市一次且僅一次，最後回到原出發城市。這個遊戲促使人們研究如何判斷一個圖有無這一性質，如果有，則又如何確定這樣的路徑。這是一個至今尚未完全解決的問題（圖4）。 1962年中國數學家管梅谷提出一個所謂“中國郵路問題”：郵遞員帶著郵件從郵局出發，走遍他所管轄的每一條街道，最後回到郵局，如何選擇路線，使走的路程最短。1967年埃德蒙茲給出中國郵路問題一個好的解法。1936年出版D.克尼希第一本關於圖論的書。60年代以來圖論在各種學科領域中得到了廣泛應用。圖論在理論上也得到了新的發展，如W.圖特等發展了擬陣理論，C.貝爾熱等發展了超圖理論，P.埃爾德什等發展了極圖理論等。

圖

圖論中所研究的圖就是節點和邊的集合，記作G＝(V，E),其中V表示非空的節點集合，E表示邊的集合。圖5中,V＝{v1,v2,v3,v4,v5,v6},E＝{e1,e2,e3,e4,e5,e6,e7,e8},其中e1＝[v1,v1],e2＝[v1,v2],…。在圖的研究中常用到的概念有：

（1）節點數和邊數：集合V的元素個數稱為圖G的節點數;集合E的元素的個數稱為圖G的邊數。

（2）端點和關聯邊：若e＝[vi，vj]∈E,則稱點vi和vj是e的端點，而稱e是點vi和vj的關聯邊。

（3）相鄰點和相鄰邊:若vi和vj與同一條邊相關聯,則vi與vj是相鄰點；若ei與ej有一個共同端點,則若ei與ej為相鄰邊。

（4）環和多重邊:若邊的兩個端點同屬一個節點,則稱該邊為環；若兩個端點之間多於一條邊，則稱多重邊。

（5）多重圖和簡單圖：含有多重邊的圖稱為多重圖；無環無多重邊的圖稱為簡單圖。

（6）次：以點 v為端點的邊數稱為這個點的次，記作d(v)。如圖5中d(v2)=4。

（7）懸掛點和懸掛邊：次為1的點稱為懸掛點;與懸掛點連線的邊為懸掛邊。

（8）奇點和偶點:次為奇數的點為奇點,否則為偶點。

（9）空圖：若圖G中E＝∅（空集）,則G為空圖。

（10）孤立點：空圖的點或次為零的點，均稱為孤立點。

連通圖

如果圖G 的任意兩點至少有一條通路連線起來，則圖G稱為連通圖，否則稱為不連通圖（圖6）。連通圖也有一些常用的概念：

（1）鏈：若圖G的節點的序列P＝{v1,…,vk}中,相繼兩節點在圖中都是相鄰的,則稱P是一條連線v1和vk的鏈。

（2）有向連通圖和無向連通圖：給每條邊規定一個方向，即各節點間用帶有箭頭的邊連線時，稱為有向連通圖；否則為無向連通圖（圖7）。

（3）強連通圖：在有向連通圖中所有頂點間都有互通的邊存在時，則這種有向連通圖稱為強連通圖（圖8）。

子圖

在研究和描述圖的性質和圖的區域性結構中，子圖的概念佔有重要地位。對於圖G1＝(V1,E1)，G2＝(V2,E2)，若V1吇V2，E1吇E2，則稱G1為G2的子圖。若V1嶅V2,E1嶅E2,即 G1不包含G2中所有節點和邊，則稱G1為G2的真子圖,如圖9中右圖是左圖的真子圖。若V1=V2,E1嶅E2，則稱 G1為G2的支撐子圖。若V1吇V2，E1＝{[u，v]∈E2|u∈V1,v∈V1}，則稱G1是G2由V1匯出的子圖，記作G(V1)。