有向图

在離散數學中，**圖**（Graph）是用於表示物體與物體之間存在某種關係的結構。數學抽象後的「物體」稱作**節點**或**頂點**（英語：Vertex，node 或 point），節點間的相關關係則稱作**邊**。在描繪一張圖的時候，通常用一組點或小圓圈表示節點，其間的邊則使用直線或曲線。

圖中的邊可以是有方向或沒有方向的。例如在一張圖中，如果節點表示聚會上的人，而邊表示兩人曾經握手，則該圖就是沒有方向的，因為甲和乙握過手也意味著乙一定和甲握過手。相反，如果一條從甲到乙的邊表示甲欠乙的錢，則該圖就是有方向的，因為「曾經欠錢」這個關係不一定是雙向的。前一種圖稱為**無向圖**，後一種稱為**有向圖**。

圖是圖論中的基本概念。1878 年，詹姆斯・西爾維斯特首次使用「圖」這一名詞：他用圖來表示數學和化學分子結構之間的關係（他稱為「化學圖」，英語：chemico-graphical image）。

## 定義

在圖論中，圖的定義有很多。下面是一些比較基本的定義方式以及與它們相關的數學結構。

###  圖

一張圖（為了和**有向圖**區分，也稱**無向圖**；為了和多重圖區分，也稱**簡單圖**）是一個二元組 _G_ = (_V_, _E_)，其中集合 V 中的元素稱為**節點**，集合 E 中的元素是兩個節點組成的無序對，稱為**邊**。集合 V 稱為**點集**，E 稱為**邊集**。

一條邊 $\{x,y\}$ 上的兩個節點 _x_ 和 _y_ 稱作這條邊的**頂點**或**端點**；也說這條邊**連接**了節點 _x_ 和 _y_，或這條邊與 _x_ 和 _y_**關聯**（英語：incident）。一個節點可以不屬於任何邊，即它不與任何節點相連。由於 $\{x,y\}$ 是無序對， $\{x,y\}$ 和 $\{y,x\}$ 表示的是同一個元素。

更一般地，多重圖的定義中允許同一對節點之間存在多條不同的邊。在特定語境中，多重圖也可以直接稱作圖。此時，在上面的定義中，集合 _E_ 應該為多重集。

有時，圖的定義中允許**自環**（簡稱**環**，英語：loop），即一條連接一個節點和其自身的邊。允許自環的圖也稱為**自環圖**。

點集 _V_ 一般是有限集；這意味著邊集 _E_ 也是有限集（不考慮多重圖）。相對地，無限圖中的點集可以是無限的。然而，由於有限圖中的結論大多不能延伸到無窮圖，無窮圖通常更被視為一種特殊的二元關係。

一個點集為空集的圖稱為空圖（因此邊集也是空集）。圖的**階**（英語：order）是指其中節點的數量，即 |_V_|。圖的**邊數**是指其邊的數量，即 |_E_|。圖的**大小**（size）一般也指圖的邊數。但在一些語境中，例如描述算法複雜度的時候，圖的大小是指 |_V_|+|_E_|（否則非空圖的大小也有可能是 0）。節點的**度**（英語：degree 或 valency）是指連接到該節點的邊的數量；對於允許自環的圖，環要算做兩條邊（因為兩端都連接到這個節點）。

如果一個圖的階是 _n_，則其節點的度最大可能取 _n_-1（對於允許自環的圖則是 _n_），而邊最多可能有 _n_(_n_ − 1)/2 條 (對於允許自環的圖則是 _n_(_n_ + 1)/2）。

在圖的定義中，邊的概念定義了節點上的一個對稱關係，即「鄰接」關係（英語：adjacency relation）。具體地說，對於兩個節點 _x_ 和 _y_，如果 $\{x,y\}$ 是一條邊，則稱它們是鄰接的。一張圖因此可以用其鄰接矩陣 _A_ 來表示，即一個 $n\times n$ 的矩陣，其中每個元素 _Aij_ 表示節點 _i_ 和 _j_ 之間的邊的數量。對於一個簡單圖，總有 $A_{ij}\in \{0,1\}$ ，分別表示「不相連」和「相連」，而 $A_{ii}=0$ （即一條邊的兩個頂點不能相同）。允許自環的圖上 $A_{ii}$ 的取值可以是非負整數，而多重圖則允許任何 $A_{ij}$ 的取值都是非負整數。無向圖的鄰接矩陣是對稱陣（ $A_{ij}=A_{ji}$ ）。

### 有向圖

邊為有方向的圖稱作**有向圖**（英語：**directed graph** 或 **digraph**）。

有向圖的一種比較嚴格的定義是這樣的：一個二元組 $G=(V,E)$ ，其中

 * $V$ 是**節點**的集合；
* $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\wedge x\neq y\}$ 是**邊**（也稱為_有向邊_，英語：**directed edge** 或 **directed link**；或**弧**，英語：**arcs**）的集合，其中的元素是節點的有序對。

為了和多重圖區分，這樣的有向圖也稱為**有向簡單圖**。

在從 $x$ 到 $y$ 的邊 $(x,y)$ 上，節點 $x$ 和 $y$ 稱作這條邊的**頂點**，其中 $x$ 是**起點**或**尾**（英語：tail）， $y$ 是**終點**或**頭**。也說這條邊**連接**了節點 $x$ 和 $y$ 、這條邊與節點 $x$ 和 $y$ **關聯**。一張有向圖中的節點可以不屬於任何一條邊。邊 $(y,x)$ 稱為邊 $(x,y)$ 的**反向邊**。

節點的**出度**（英語：out-degree）是指起點為該節點的邊的數量；節點的**入度**（英語：in-degree）是指終點為該節點的邊的數量。

更一般地，如果一張有向圖允許多條頭尾都分別相同的邊，則稱這樣的圖為**有向多重圖**，這樣的邊稱為**多重邊**。一種允許多重邊的的有向圖定義方法如下：一個**有向圖**是這樣的三元組 $G=(V,E,\phi )$ ：

 * $V$ 是節點的集合；
* $E$ 是邊的集合；
* $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\wedge x\neq y\}$ 是一個**關聯函數**，將每條邊映射到一個由頂點組成的有序對上（即一條邊被按順序關聯到兩個頂點）。

自環是指一條起點和終點相同的邊。前面的兩個定義都不允許自環，因為若節點 $x$ 上有一個自環，則邊 $(x,x)$ 存在；但這樣的邊不在 $\{(x,y)\mid (x,y)\in V^{2}\wedge x\neq y\}$ 中。因此，如果要允許自環，則上面的定義要做修改：對於有向簡單圖， $E$ 的定義應該修改為 $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}$ ；對於有向多重圖， $\phi $ 的定義應該修改為 $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}$ 。為了避免定義不清，這樣的圖分別稱作**允許自環的有向簡單圖**或**允許自環的有向多重圖**（英語：quiver）。

在允許自環的有向簡單圖 $G$ 中，邊是 $V$ 上的一個齊次關係 $\sim $ ，稱作 $G$ 上的**鄰接關係**。 
對於頂點是 $x$ 和 $y$ 的邊 $(x,y)$ ，我們說 $x$ 和 $y$ 是彼此**鄰接**的，記作 $x\sim y$ 。

### 混合圖

邊既可以有向、也可以無向的圖稱作**混合圖**。**混合簡單圖**是一個多元組 _G_ = (_V_, _E_, _A_)，而**混合多重圖**則是多元組 _G_ = (_V_, _E_, _A_, _ϕ_E, _ϕ_A)，其中 _V_、_E_（無向邊集）、_A_（有向邊集）、_ϕ_E、_ϕ_A 的定義可以參考前面的無向圖和有向圖定義。在此定義下，有向圖和無向圖是混合圖的特殊情況。

### 賦權圖

**賦權圖**（英語：weighted graph，也稱**加權圖**、**網絡**（英語：network））是指每條邊都對應有一個數字（即「權重」，weight）的圖。根據具體問題，權重可以表示諸如費用、長度或容量等意義。這樣的圖會出現在最短路徑問題和旅行商問題等問題中。

## 基本術語

* **子圖**（subgraph）：對於圖 $G$ 和圖 $G'$ ，若 $V(G')\subseteq V(G)$ 且 $E(G')\subseteq E(G)$ ，則稱 $G'$ 是 $G$ 的子圖。
* **生成子圖**（spanning subgraph）：指滿足條件 $V(G')=V(G)$ 的 $G$ 的子圖 $G'$ 。
* **鏈**(chain 或 walk)、**軌跡**(trail)、**路徑**(path)：鏈是頂點 $v_{i}$ 和邊 $e_{i}$ 交替出現的序列 $W=v_{i_{0}}e_{i_{0}}v_{i_{1}}...e_{i_{k}}v_{i_{k}}$ 稱作一個長度為 _k_ 的鏈，其中 $v_{i_{0}}$ 和 $v_{i_{k}}$ 為其端點，其餘頂點為內部點。所有邊都不相同的鏈稱為軌跡（簡稱跡）。所有頂點都不相同的軌跡稱為路徑（簡稱路）。在有向圖中，若鏈（跡、路）的方向和其中每條邊的方向一致，則稱其為有向鏈（跡、路）。
* 兩端點相同的鏈和跡分別稱為閉鏈（或環，cycle）、閉跡（或迴路，circuit）。
* **距離**（Distance）： 從頂點 $u$ 出發到頂點 $v$ 的最短路徑若存在，則此路徑的長度稱作從 $u$ 到 $v$ 的距離。

## 特殊的圖

### 正則圖

**正則圖**是指每個節點的**鄰居**（英語：neighbor）數量都相同的圖，即每個節點的度都相同的圖。節點的度為 _k_ 的正則圖也稱作 _k_- 正則圖。

### 完全圖

**完全圖**（英語：complete graph）是指每對節點之間都有一條邊相連的圖。一張完全圖包含簡單圖所有可能出現的邊。

### 有限圖

**有限圖**（英語：finite graph）是指點集和邊集是有限集的圖。否則，則稱為**無限圖**。在不加說明的情況下，圖論中討論的圖大多是有限圖。

### 連通圖

在無向圖中，如果存在 _x_ 和 _y_ 之間的路徑，則稱此兩節點的無序對 $\{x,y\}$ 是**連通**的；否則，則稱此兩點是**非聯通**的。

**連通圖**是指每對節點都連通的無向圖。否則，則稱圖是**非連通圖**。

在有向圖中，如果存在 _x_ 和 _y_ 之間的有向路徑，則稱此兩節點的有序對 $\{x,y\}$ 是**強連通**的。此外，若將圖中的所有邊都換為無向邊，得到的無向圖中存在 _x_ 和 _y_ 之間的路徑，則稱此兩節點是**弱連通**的。否則，則稱此兩點是**非聯通**的。

**強連通圖**是指每對節點都強連通的有向圖。此外，**弱連通圖**是指每對節點都弱聯通的有向圖。否則，則稱圖是**非連通圖**。

對於一張圖，若不存在大小為 _k_ − 1 的點集或邊集，使得從圖中移除該集合後，圖就變為非連通圖，則稱該圖是**_k_- 點連通圖**或**_k_- 邊連通圖**。_k_- 點連通圖通常也簡稱 _k_- 連通圖。

### 二分圖

**二分圖**（英語：bipartite graph）是指這樣的簡單圖：其點集可以被劃分稱兩個集合 _W_ 和 _X_，其中 _W_ 中的任意兩個節點之間沒有邊相連，_X_ 中的任意兩個節點之間也沒有邊相連。二分圖是點著色色數為 2 的圖。

若一張圖的點集是兩個集合 _W_ 和 _X_ 的無交並，使得 _W_ 中的任意節點都和 _X_ 中的所有節點鄰接，且 _W_ 或 _X_ 之內沒有邊，則稱此圖是**完全二分圖**。

### 平面圖

**平面圖**是指可以將其節點和邊畫在平面上，而沒有兩邊相交的圖。

### 循環圖

階為 _n_≥3 的**循環圖**（英語：cycle graph）或**環形圖**（英語：circular graph）是指其節點可以列為 _v_1, _v_2, …, _v_n，使得圖中的邊為 $\{v_{i},v_{i+1}\}$ ，其中 _i_=1, 2, …, _n_ − 1，以及 $\{v_{n},v_{1}\}$ 。循環圖的另一種定義是所有點的度都為 2 的連通圖。如果循環圖是另一個圖的子圖，則它是那個圖中的一個環。

### 樹和森林

**樹**是指任意兩點之間都有且僅有一條路徑的無向圖。等價地，**樹**是一個連通無環無向圖。

**森林**是指任意兩點之間**至多**僅有一條路徑的無向圖。等價地，**森林**是一個無環無向圖，或一組樹的無交並。

### 其它特殊的圖

一些進階的特殊圖包括：

* 佩特森圖；
* 完美圖；
* 弦圖；
* 強正則圖。

## 例子

* 右邊的圖示是一個點集為 $V=\{1,2,3,4,5,6\}$ 、邊集為 $E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}$ 的圖。
* 在計算機科學中，有向圖可以用於表示概念圖、有限狀態自動機，以及其它許多資料結構。
* 任意集合 _X_ 上的二元關係 _R_ 都可定義一個有向圖。_X_ 中的元素 _x_ 到 _y_ 有一條邊，若且唯若 _xRy_。
* 有向圖可以用於表示信息網絡。例如，在推特上，用戶之間的關注關係可以用有向圖表示。

## 圖運算

圖上可以進行一些運算或變換，使一個圖變為另一個圖：

* **一元運算**，將一個圖變換為另一個圖，例如：
  * 邊收縮，
  * 線圖，
  * 對偶圖，
  * 補圖；
* **二元運算**，結合兩個圖為一個新圖，例如：
  * 圖的無交並，
  * 圖乘積，包括圖的笛卡爾乘積、圖的張量積、圖的強乘積、圖的字典積等，
  * 圖的串並聯等。

## 圖的推廣

在超圖中，允許一條邊連接多於兩個節點。

無向圖可以看作是由 1 - 單純形（邊）和 0 - 單純形（節點）組成的單純復形。由此，復形成為圖的推廣，其中允許維度更高的單純形。

圖可以看作是一種擬陣。

在模型論中，圖是一個結構。這樣一來，邊的數量可以是任意基數。參見圖極限。

在計算生物學中，冪圖推廣了無向圖的定義。

在地理信息系統中，為了進行道路網絡或電網的時空分析而提出的幾何網絡的定義參考了圖，並借用了許多圖論的概念。

## 參見

* 概念圖
* 圖 (資料結構)
* 圖論
* 圖資料庫
* 網絡理論

## 參考資料

### 腳註

### 文獻

* _Introduction To Graph Theory_, by Gary Chartrand and Ping Zhang, McGraw Hill
* 徐，俊明。图论及其应用 第二版。合肥：中國科學技術大學出版社. 2004. ISBN 7-312-00979-4.
* Balakrishnan, V. K. Graph Theory 1st. McGraw-Hill. 1997. ISBN 978-0-07-005489-9.
* Bang-Jensen, J.; Gutin, G. Digraphs: Theory, Algorithms and Applications. Springer. 2000 [2021-08-14]. （原始內容存檔於 2011-08-26）.
* Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability. 2010 [2021-08-14]. （原始內容存檔於 2021-08-17）.
* Berge, Claude. Théorie des graphes et ses applications. Paris: Dunod. 1958 （法語）.
* Biggs, Norman. Algebraic Graph Theory 2nd. Cambridge University Press. 1993. ISBN 978-0-521-45897-9.
* Bollobás, Béla. Modern Graph Theory 1st. Springer. 2002. ISBN 978-0-387-98488-9.
* Diestel, Reinhard. Graph Theory 3rd. Berlin, New York: Springer-Verlag. 2005 [2021-08-14]. ISBN978-3-540-26183-4. （原始內容存檔於 2019-12-16）.
* Graham, R.L.; Grötschel, M.; Lovász, L. Handbook of Combinatorics. MIT Press. 1995. ISBN 978-0-262-07169-7.
* Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press. 1998. ISBN 978-0-8493-3982-0.
* Gross, Jonathan L.; Yellen, Jay. Handbook of Graph Theory. CRC. 2003. ISBN 978-1-58488-090-5.
* Harary, Frank. Graph Theory. Addison Wesley Publishing Company. 1995. ISBN 978-0-201-41033-4.
* Iyanaga, Shôkichi; Kawada, Yukiyosi. Encyclopedic Dictionary of Mathematics. MIT Press. 1977. ISBN 978-0-262-09016-2.
* Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae 31st. Chapman & Hall/CRC. 2002. ISBN 978-1-58488-291-6.
* Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Publications. 1993 [8 August 2012]. ISBN978-0-486-67870-2. （原始內容存檔於 2019-05-05）.

## 外部連結

* Springer-Verlag, Heidelberg. Graph Theory. 2016 [2019-07-22]. （原始內容存檔於 2012-02-08）.
* 維基共享資源上的相關多媒體資源：圖
* 埃里克・韋斯坦因. Graph. MathWorld.