圖論

圖論是數學的一個分支，研究圖的數學性質。圖論中的圖由頂點（或節點）和連接它們的邊（或弧）組成。圖論的概念可追溯到1736年，歐拉用圖論解決了柯尼斯堡七橋問題。此後，圖論逐漸發展為一個成熟的數學領域，並在計算機科學、網絡科學、生物學等多個領域得到了廣泛應用。

概念

有向圖

無向圖

圖的定義：圖$G=(V,E)$是由頂點集$V$和邊集$E$組成的，其中$V$是非空有限集合，$E$是$V$中元素對（無向圖）或有序對（有向圖）所組成的集合。

1. 邊（Edge）：邊是圖中連接兩個頂點的線段。在無向圖中，邊是頂點對$(u,v)$，順序無關；在有向圖中，邊是頂點的有序對$(u,v)$，順序相關，表示從頂點$u$指向頂點$v$。
2. 端點（Endpoint）：邊連接的兩個頂點稱為端點。設邊$e=(u,v)$，則頂點$u$和$v$是邊$e$的端點。
3. 環（Loop）：如果一條邊的兩個端點重合，即$(u,u)$，則稱為環。
4. 空圖（Empty Graph）：一個沒有頂點和邊的圖稱為空圖。
5. 零圖（Null Graph）：一個有$n$個頂點但沒有邊的圖稱為$(n,0)$圖，也叫零圖。
6. 平凡圖（Trivial Graph）：只有一個頂點的圖稱為平凡圖，記為$(1,0)$圖。
7. 簡單圖（Simple Graph）：沒有環和平行邊（具有相同端點的多條邊）的圖稱為簡單圖。
8. 偶圖（Bipartite Graph）：如果圖$G$的頂點集$V(G)$能分解為兩個不相交子集$V_{1}$和$V_{2}$（即$V_{1}\cup V_{2}=V(G)$，$V_{1}\cap V_{2}=\varnothing$），且子集內的頂點互不相鄰，則稱圖$G$是偶圖，記為$G=(V_{1},V_{2},E)$。
9. 有向圖（Directed Graph）：圖$G=(V,E)$稱為有向圖，如果邊集$E$由頂點集$V$中元素的有序對組成。在有向圖中，頂點$u$是邊$e=(u,v)$的尾，邊$e$與頂點$u$出關聯；頂點$v$是邊$e=(u,v)$的頭，邊$e$與頂點$v$入關聯。
10. 無向圖（Undirected Graph）：圖$G=(V,E)$稱為無向圖，如果邊集$E$由頂點集$V$中元素的無序對組成。
11. 孤立點（Isolated Vertex）：沒有關聯邊的頂點稱為孤立點。
12. 懸點（Pendant Vertex）：恰有一條關聯邊的頂點稱為懸點。
13. 懸邊（Pendant Edge）：與懸點關聯的邊稱為懸邊。

歷史

圖論的歷史始於1736年，歐拉通過解決柯尼斯堡七橋問題，奠定了圖論的基礎。在19世紀和20世紀，隨着數學家們對圖論問題的研究，圖論逐漸發展為一個成熟的數學領域。20世紀下半葉，隨着計算機科學的發展，圖論在計算機科學中的應用越來越廣泛，成為計算機科學的一個重要分支。

圖論問題

1. 圖的計數：計算某類圖的數量。例如，計算具有$n$個頂點的無向圖的數量。
2. 子圖相關問題：在給定的圖$G$中尋找具有特定性質的子圖。例如：
   • 子圖同構問題：給定兩個圖$G$和$H$，判斷$G$中是否存在一個子圖與$H$同構。這是一個NP完全問題。
   • 哈密頓迴路問題：給定一個圖$G$，判斷是否存在一個子圖與具有$n$個頂點的圈同構。
3. 染色問題：將圖的頂點或邊染色，使得滿足特定條件。例如：
   • 四色問題：證明任何平面圖的頂點可以用不超過四種顏色染色，使得相鄰頂點具有不同顏色。
   • 邊色數問題：求一個圖的最少邊色數，使得相鄰邊具有不同顏色。
4. 路徑問題：在給定的圖中尋找滿足特定條件的路徑。例如:
   • 柯尼斯堡七橋問題：求解是否存在一條經過柯尼斯堡七橋且僅經過一次的路徑。
   • 哈密頓迴路問題：在給定圖中尋找一條包含所有頂點且僅訪問一次的迴路。
   • 最小生成樹問題：在給定的帶權無向圖中尋找權值最小的生成樹。
   • 中國郵路問題：求解經過所有邊至少一次的最短路徑。
   • 最短路問題：求解給定兩個頂點之間的最短路徑。
   • 斯坦納樹：求解包含給定頂點集合的最小生成樹。
   • 旅行商問題：求解經過所有頂點且僅訪問一次的最短路徑（NP困難問題）。
5. 網絡流與匹配問題：
   1. 最大流問題、最小割問題和最大流最小割定理：在給定的網絡中求解最大流和最小割。
   2. 最小費用最大流問題：在給定的網絡中求解具有最小費用的最大流。
   3. 二分圖及任意圖上的最大匹配：求解給定圖中的最大匹配。
   4. 帶權二分圖的最大權匹配：求解給定帶權二分圖中的最大權匹配。
6. 覆蓋問題：
   • 最大團：在給定圖中尋找最大的完全子圖。
   • 最大獨立集：在給定圖中尋找最大的無邊導出子圖，即獨立集。
   • 最小覆蓋集：求解包含所有頂點的最小邊集。
   • 最小支配集：求解能支配給定圖中所有頂點的最小頂點集。

重要算法

1. 迪克斯特拉算法（Dijkstra's Algorithm, D.A）：求解給定圖中兩個頂點之間的最短路徑。
2. 克魯斯卡爾算法（Kruskal's Algorithm, K.A）：求解給定帶權無向圖的最小生成樹。
3. 普里姆算法（Prim's Algorithm, P.A）：求解給定帶權無向圖的最小生成樹。
4. 拓撲排序算法（Topological Sorting Algorithm, TSA）：對有向無環圖（DAG）進行拓撲排序。
5. 關鍵路徑算法（Critical Path Algorithm, CPA）：求解給定圖中的關鍵路徑。
6. 廣度優先搜索算法（Breadth-First Search, BFS）：對圖進行廣度優先遍歷。
7. 深度優先搜索算法（Depth-First Search, DFS）：對圖進行深度優先遍歷。