研究節點和邊組成的圖形的數學理論和方法，為運籌學的一個分支。圖論的基本元素是節點和邊（也稱線、弧、枝），用節點表示所研究的物件，用邊表示研究物件之間的某種特定關係。因此，圖論可用節點和邊組成的圖形及其有關的理論和方法來描述、分析和解決各種實際問題，諸如物理學、化學、生物學、管理科學、計算方法和工程技術等領域的有關問題。圖論與組合數學、線性規劃、群論、矩陣論、概率論、數值分析等數學分支有密切的關係。
發展簡史
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＝{
v
1,
v
2,
v
3,
v
4,
v
5,
v
6},
E＝{
e
1,
e
2,
e
3,
e
4,
e
5,
e
6,
e
7,
e
8},其中
e
1＝[
v
1,
v
1],
e
2＝[
v
1,
v
2],…。在圖的研究中常用到的概念有:①節點數和邊數：集合
V的元素個數稱為圖
G的節點數；集合
E的元素的個數稱為圖
G的邊數。②端點和關聯邊：若
e＝[
vi，vj]∈
E,則稱點
vi和
vj是
e的端點，而稱
e是點
vi和
vj的關聯邊。③相鄰點和相鄰邊:若
vi和
vj與同一條邊相關聯,則
vi與
vj是相鄰點；若
ei與
ej有一個共同端點,則若
ei與
ej為相鄰邊。④環和多重邊:若邊的兩個端點同屬一個節點,則稱該邊為環；若兩個端點之間多於一條邊，則稱多重邊。⑤多重圖和簡單圖：含有多重邊的圖稱為多重圖；無環無多重邊的圖稱為簡單圖。⑥次：以點
v為端點的邊數稱為這個點的次，記作
d(
v)。如圖5中
d(
v
2)=4。⑦懸掛點和懸掛邊：次為1的點稱為懸掛點；與懸掛點連接的邊為懸掛邊。⑧奇點和偶點:次為奇數的點為奇點,否則為偶點。⑨空圖：若圖
G中
E＝φ（空集）,則
G為空圖。⑩孤立點：空圖的點或次為零的點，均稱為孤立點。
連通圖 如果圖G 的任意兩點至少有一條通路連接起來，則圖G稱為連通圖，否則稱為不連通圖（圖6）。連通圖也有一些常用的概念：①鏈：若圖G的節點的序列P＝{v1,v2,…,vk}中,相繼兩節點在圖中都是相鄰的,則稱P是一條連接v1和vk的鏈。②有向連通圖和無向連通圖：給每條邊規定一個方向，即各節點間用帶有箭頭的邊連接時，稱為有向連通圖；否則為無向連通圖（圖7）。③強連通圖：在有向連通圖中所有頂點間都有互通的邊存在時，則這種有向連通圖稱為強連通圖（圖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)。
樹 樹是圖論中的一個重要概念。一個圖中如果沒有由節點和邊組成的圈就稱為無圈圖。樹就是一個連通的無圈圖。圖10給出有6個節點的不同的樹。如果連通圖G＝(V，E)的支撐子圖T＝(V，ET)是樹,則稱T為G 的支撐樹（圖11）。若T＝(V，ET)是支撐樹，則稱T＝(V，E\ET)為G 的餘樹（圖12）。
圖的矩陣表示法 一個圖由它的鄰接性和關聯性完全決定，這種信息可用矩陣表示。常用的有鄰接矩陣和關聯矩陣等。①鄰接矩陣 A：用來表示圖中各節點之間連通狀態的矩陣。A的元素aij可定義為
圖13中圖G 的鄰接矩陣A為
②關聯矩陣 S：用來描述節點和邊之間的關聯關系的矩陣。S的元素sij可以定義為
圖13中圖G 的關聯矩陣S為
其他還有能用來描述基爾霍夫電流定理和電壓定理的割集矩陣和圈矩陣等。
參考書目
李修睦:《圖論導引》,華中工學院出版社,武漢,1982。
F.Harary著,李慰萱譯：《圖論》,上海科學技術出版社，上海，1981。
J.A.Bondy，U.S.R.Murty，Graph Theory with Applications,MacMillan Press, London, 1976.