圖論術語

圖論中有許多專有名詞，此處總結了一些名詞的一般意義和用法。

## 基本術語

一個圖（一般記作$G$）由兩類元素構成，分別稱為「頂點」（或節點、結點）和「邊」。每條邊有兩個頂點作為其端點，我們稱這條邊「連接」了它的兩個端點。因此，邊可定義為由兩個頂點構成的集合（在有向圖中為有序對，見下文「方向」一節）。

圖也可以用其他模型來表示，如定義在頂點集合上的二元布爾函數，或者方形(0,1)-矩陣。

頂點或邊上有標號的圖稱為有標號的，否則為無標號的。它們的區別在於，無標號的圖並沒有為頂點或邊指定一個特定的順序。

圖的標號一般指按某一規則為圖的頂點或邊指定一個標號。標號通常是自然數，且一般互不相同。

<image>

一個超邊是允許連接任意多個（可以多於兩個）頂點的「邊」。含有超邊的「圖」稱為超圖。邊可視為恰連接兩個頂點的超邊，因此圖可視為一種特殊的超圖。

空圖或禿圖是沒有邊的圖。

如果一個圖有無窮多的頂點和/或邊，則稱其為無窮的，否則為有窮的。如果一個圖是無窮的，但每個頂點的度（見下）是有限的，則稱為局部有窮的。一般假定「圖」指有窮圖。

兩個圖$G$和$H$，如果存在$V(G)$與$V(H)$之間的一一對應，使得圖$G$中兩個頂點相連若且唯若它們在圖$H$中的對應頂點相連，則稱圖$G$和$H$ 同構，記作$G\simeq H$。類似地，如果僅僅是$V(G)$到$V(H)$的映射而不一定是一一對應，則稱此映射是$G$到$H$的同態。

### 彼得森圖

圖論中最有名圖之一。

### 邊

一條邊一般表示為連接其兩個端點的曲線。以兩個頂點$u$、$v$為端點的邊一般記作$(u,v)$、$\{u,v\}$或$uv$。一條邊連接兩個頂點$u$、$v$時，稱$u$與$v$相鄰。圖$G$的邊集一般記作$E(G)$，當不發生混淆時可簡記為$E$。

### 補圖

圖$G$的補圖$\bar{G}$是一個圖，它的點集與$G$相同，而每條邊$(u,v)$存在於$\bar{G}$中若且唯若它不存在於$G$中。

### 頂點

一個頂點一般表示為一個點或小圓圈。一個圖$G$的頂點集（點集）一般記作$V(G)$，當不發生混淆時可簡記為$V$。圖$G$的階為其頂點數目，亦即|$V(G)$|。

### 度

若兩個點之間有一條邊，則這兩個點相鄰。關聯一個點$v$的邊的條數稱為是$v$度數（degree）或價（valency）。特別的，若$G$不是多重圖時，它等於這一點的鄰點個數。

一個頂點被稱作孤立頂點，當它的度數為$0$。

$G$的最小度記為$\delta(G) := min\left\{d(v)|v\in V\right\}$

$G$的最大度記為$\Delta(G) := max\left\{d(v)|v\in V\right\}$

$G$的平均度記為$d(G) := \frac{\sum_{v \in V} d(v)} {|V|}$

稱$G$為k-正則的，當$G$的所有頂點都有相同的頂點度k。特別的，3-正則圖被稱作立方圖。

### 獨立集

一個圖的獨立集是圖中一些兩兩不相鄰的頂點所形成的集合。

### 二分圖

圖G是二分圖若且唯若它的點集V能被劃分成兩塊X和Y，使得對於G中的任意一條邊，它有一個端點屬於X而另一個端點屬於Y。

### 環

看環（圖論）。

### 距離

距離是兩個頂點之間經過最短路徑的邊的數目，通常用$d_G ( u, v )$表示。

頂點$v$的偏心率（eccentricity），用來表示連接圖$G$中的頂點$v$到圖$G$中其它頂點之間的最大距離，用符號$\epsilon_G (v)$表示。

圖的直徑（diameter），表示取遍圖的所有頂點，得到的偏心率的最大值，記作$diam(G)$。相對於直徑的一個概念是圖的半徑（radius），表示圖的所有點的偏心率的最小值，記作$rad(G)$。這兩者間的關係是：$diam(G) \leqslant 2 rad(G)$

### 柯尼斯堡七橋問題

圖論中著名的問題。

### 連通圖／連通性

稱$G$是連通的，如果非空圖$G$的任意兩個頂點之間均有一條路相連。

稱$G$是k-連通的，如果非空圖$G$的任意兩個頂點之間都有$k$條獨立路相連。k-連通的的另外一個定義是：若$\mid G \mid>k\in \mathbb N$,且對任意滿足$|X|<k$的子集$X \subseteq V$均有$G-X$是連通的，則稱$G$是k-連通的。由門格爾定理，易知這兩個定義是等價的。通過k-連通的概念，定義使得$G$是k-連通的最大整數$k$稱作$G$的連通度。

類似的，還可以引入k-邊連通的概念：稱一個$\mid G \mid$的圖$G$是k-邊連通的，如果對任意一個滿足$\mid F \mid < k$的邊的集合$F$，$G - F$均是連通的。同樣，$G$的邊連通度是使得$G$是k-邊連通的最大整數。

### 旅行推銷員問題

電腦科學中最有名的問題之一。

### 歐拉路徑

一筆畫問題、也看哈密爾頓環。

### 平面圖

庫拉托夫斯基定理描述關於平面圖的等價判定定理。由歐拉公式可知：V-E+F=2，其中的2即為球面的歐拉示性數。

### 路徑

路徑（walk），又譯作途徑。一個長度為$k$的路徑是一個非空的頂點和邊的交錯序列$v_0 e_0 v_1 e_1 ... e_{k-1} v_k$，使得對於所有$i < k$均有$e_i={v_i v_{i+1}}$。特別的，當$v_0 = v_k$時，稱這個路徑是閉的（closed）；當路徑中的頂點互不相同，得到$G$的一條路。

### 樹

<image>

連通無圈圖稱為樹，一般記為T。其中，度數為1的頂點稱為葉子，否則稱為內點。有時我們會從樹中選出一個頂點作為特殊頂點，稱之為根以示區分，此時稱此樹為有根樹。有根樹常作為有向無環圖來處理。

樹T的連通子圖稱為T的子樹。

樹也是一個團的森林。

### 森林

無環（不一定連通）圖稱為森林，森林F的子圖稱為F的子森林。

如果圖G的一個生成子圖是樹，則稱該子圖為生成樹。

星是僅有一個頂點不是葉子的樹。星也可以表示為完全二分圖K1,n。

### 團

<image>

圖中的團是由圖中兩兩相鄰的頂點構成的集合。

### 完全圖

完全圖是所有頂點兩兩相鄰的圖。n階完全圖，記作Kn。如圖所示為K5。n階完全圖有n(n-1)/2條邊。

### 網路流

重要的電腦科學、最優化理論、與算法學的題目。也看最大流最小割定理。

### 圍長

圍長定義為圖所包含的最短環長，也被稱為"girth"。

### 相鄰

兩頂點相鄰，意思是之間有一條邊。

### 葉子

看以上的樹術語。

### 自環

一個自環是兩個端點為同一頂點的邊。如果有多於一條邊連接同一對頂點，則它們均被稱為重邊。一個圖的重數是重複次數最多的邊的重複次數。如果一個圖不含自環或重邊，則稱為簡單圖。多數情況下，如無特殊說明，可以假定「圖」總是指簡單圖。

### 著色

圖著色問題包含四色定理，數學中最有名的問題之一。現代的證明用電腦、文章很長。

### 子圖

兩個圖G和H，如果V(H)是V(G)的子集且E(H)是E(G)的子集（當然，E(H)中只能包含將V(H)中的頂點相連的邊）則稱H是G的子圖。如果圖G和H不相等，即V(H)是V(G)的真子集或E（H）是E（G）的真子集，則稱H是G的真子圖。如果H是G的子圖或者存在一個G的子圖與H同構，則稱G包含H。

如果圖G的子圖H滿足V(H)=V(G)，即圖H包含圖G的所有頂點，則稱H是G的支撐子圖或生成子圖。

如果圖G的子圖H滿足邊(u,v)在圖H中若且唯若邊(u,v)在圖G中，即圖H包含了圖G中所有兩個端點都在V(H)中的邊，則稱H是G的導出子圖。

對於圖的某個性質而言，如果圖G具有此性質而G的任一真子圖都不具有此性質，則稱G是具有該性質的極小圖。類似地，如果圖G具有此性質而任一以G為真子圖的圖都不具有此性質，則稱G是具有該性質的極大圖。

### 最短路問題

重要的電腦科學、與算法學的題目。也看Dijkstra演算法、Kruskal演算法、A*搜尋演演算法等。

## 定理術語

- 握手引理
- 友誼定理
- 彼得森定理
- 布魯克斯定理
- 柯尼格引理
- 柯尼格定理 (圖論)
- 庫拉托夫斯基定理
- 拉姆齊定理（而且看拉姆齊理論）
- 門格爾定理（Menger's Theorem）
- 圖特定理
- Vizing定理
- 最大流最小割定理
- 圖蘭定理
- 艾狄胥-斯通定理

## 代數圖論

代數圖論

## 不變量

### 虧格（幾何、拓撲）

看以上的平面圖。