图论术语

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

## 基本術語

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

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

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

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

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

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

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

兩個圖 $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 2rad(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. 這是歐拉示性數。

### 嵌入

### 強連通分量

### 橋

### 路徑

路徑（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$ 的一條路。

### 樹

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

樹 _T_ 的連通子圖稱為 _T_ 的**子樹**。

樹也是一個團的森林。

### 森林

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

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

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

### 縮圖

### 隨機圖

### 團

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

### Utility graph

### 完全圖

**完全圖**是所有頂點兩兩相鄰的圖。_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 算法、等。

## 定理術語

* 彼得森定理
* 布魯克斯定理
* 柯尼格引理
* 柯尼格定理 (圖論)
* 庫拉托夫斯基定理
* 拉姆齊定理（而且看拉姆齊理論）
* 門格爾定理（Menger's Theorem）
* 圖特定理
* Vizing 定理
* 最大流最小割定理

## 圖的方向

### 有向無環圖

## 代數圖論

代數圖論

## 不變量

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

看以上的平面圖。

## 譜圖論

## 參考來源

## 參見

* 圖
* 圖論
* 圖論話題列表
* 數學
* 離散數學
* 組合數學
* 算法
* 計算機科學
* 最優化
* 人工智慧（神經網格）
* 連接組（承現峻，connectome）
* 網格科學
* 費曼圖（Feynman diagram、物理、量子力學、統計力學）