圖 (數學)

此條目介紹的是圖論中的基本研究對象。關於數學函數的圖，請見「函數圖形」。關於抽象數據類型，請見「圖 (數據結構)」。關於其他主題，請見「圖」。

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

一個有6個頂點，7條邊的圖

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

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

定義

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

圖

一張有3個節點和3條邊的圖

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

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

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

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

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

一個點集為空集的圖稱為空圖（因此邊集也是空集）。圖的階（英語：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，如果${\displaystyle \{x,y\}}$是一條邊，則稱它們是鄰接的。一張圖因此可以用其鄰接矩陣A來表示，即一個${\displaystyle n\times n}$的矩陣，其中每個元素A_ij表示節點i和j之間的邊的數量。對於一個簡單圖，總有${\displaystyle A_{ij}\in \{0,1\}}$，分別表示「不相連」和「相連」，而${\displaystyle A_{ii}=0}$（即一條邊的兩個頂點不能相同）。允許自環的圖上${\displaystyle A_{ii}}$的取值可以是非負整數，而多重圖則允許任何${\displaystyle A_{ij}}$的取值都是非負整數。無向圖的鄰接矩陣是對稱陣（${\displaystyle A_{ij}=A_{ji}}$）。

有向圖

主條目：有向圖

一張3個節點和4條邊組成的有向圖（雙向箭頭表示兩個方向上各有一條邊）

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

有向圖的一種比較嚴格的定義^[8]是這樣的：一個二元組${\displaystyle G=(V,E)}$，其中

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

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

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

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

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

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

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

在允許自環的有向簡單圖${\displaystyle G}$中，邊是${\displaystyle V}$上的一個齊次關係（英語：Binary relation#Homogeneous relation）${\displaystyle \sim }$，稱作${\displaystyle G}$上的鄰接關係。 對於頂點是${\displaystyle x}$和${\displaystyle y}$的邊${\displaystyle (x,y)}$，我們說${\displaystyle x}$和${\displaystyle y}$是彼此鄰接的，記作${\displaystyle x\sim y}$。

混合圖

主條目：混合圖

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

賦權圖

一張有10個節點和12條邊的賦權圖

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

基本術語

主條目：圖論術語

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

特殊的圖

正則圖

主條目：正則圖

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

完全圖

主條目：完全圖

一張有5個節點和10條邊的完全圖，其中每個節點都和所有其它節點相連。

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

有限圖

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

連通圖

主條目：連通圖和連通度（英語：Connectivity (graph theory)）

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

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

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

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

對於一張圖，若不存在大小為k − 1的點集或邊集，使得從圖中移除該集合後，圖就變為非連通圖，則稱該圖是k-點連通圖（英語：k-vertex-connected graph）或k-邊連通圖（英語：k-edge-connected graph）。k-點連通圖通常也簡稱k-連通圖。

二分圖

主條目：二分圖

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

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

平面圖

主條目：平面圖 (圖論)

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

循環圖

主條目：循環圖

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

樹和森林

主條目：樹 (圖論)

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

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

其它特殊的圖

一些進階的特殊圖包括：

• 佩特森圖；
• 完美圖（英語：perfect graph）；
• 弦圖；
• 強正則圖（英語：strongly regular graph）。

例子

一張6個節點和7條邊的圖

• 右邊的圖示是一個點集為${\displaystyle V=\{1,2,3,4,5,6\}}$、邊集為${\displaystyle E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}}$的圖。
• 在計算機科學中，有向圖可以用於表示概念圖、有限狀態自動機，以及其它許多數據結構。
• 任意集合X上的二元關係R都可定義一個有向圖。X中的元素x到y有一條邊，若且唯若xRy。
• 有向圖可以用於表示信息網絡。例如，在推特上，用戶之間的關注關係可以用有向圖表示。^[14][15]

圖運算

主條目：圖運算

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

• 一元運算，將一個圖變換為另一個圖，例如：
  • 邊收縮，
  • 線圖，
  • 對偶圖，
  • 補圖；
• 二元運算，結合兩個圖為一個新圖，例如：
  • 圖的無交並（英語：disjoint union of graphs），
  • 圖乘積，包括圖的笛卡爾乘積（英語：cartesian product of graphs）、圖的張量積（英語：tensor product of graphs）、圖的強乘積（英語：strong product of graphs）、圖的字典積等，
  • 圖的串並聯（英語：series–parallel graph）等。

圖的推廣

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

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

圖可以看作是一種擬陣。

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

在計算生物學中，冪圖（英語：power graph analysis）推廣了無向圖的定義。

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

參見

• 概念圖
• 圖 (數據結構)
• 圖論
• 圖數據庫
• 網絡理論

參考資料

腳註

1. Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 19 [8 August 2012]. ISBN 978-0-486-67870-2. （原始內容存檔於2019-05-05）. A graph is an object consisting of two sets called its vertex set and its edge set.
2. See:

   • J. J. Sylvester (February 7, 1878) "Chemistry and algebra," （頁面存檔備份，存於互聯網檔案館） Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
   • J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," （頁面存檔備份，存於互聯網檔案館） American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436.
     JSTOR 2369436
     . The term "graph" first appears in this paper on page 65.
3. Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 35 [2021-08-14]. ISBN 978-1-58488-090-5. （原始內容存檔於2021-08-14）.
4. Bender & Williamson 2010，第148頁.
5. 參見 Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
6. Bender & Williamson 2010，第149頁.
7. Graham et al., p. 5.
8. Bender & Williamson 2010，第161頁.
9. 徐 2004，第1頁.
10. Strang, Gilbert, Linear Algebra and Its Applications 4th, Brooks Cole, 2005 [2021-08-14], ISBN 978-0-03-010567-8, （原始內容存檔於2020-09-20）
11. Lewis, John, Java Software Structures 4th, Pearson: 405, 2013, ISBN 978-0133250121
12. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne. Foundations of Discrete Mathematics International student. Boston: PWS-KENT Pub. Co. 1991: 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
13. 徐 2004，第20-21頁.
14. Grandjean, Martin. A social network analysis of Twitter: Mapping the digital humanities community. Cogent Arts & Humanities. 2016, 3 (1): 1171458 [2021-08-14]. doi:10.1080/23311983.2016.1171458 . （原始內容存檔於2021-03-02）.
15. Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter （頁面存檔備份，存於互聯網檔案館）, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

文獻

• 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]. ISBN 978-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]. ISBN 978-0-486-67870-2. （原始內容存檔於2019-05-05）.

外部連結

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

• 數學主題