用戶:Tenpages/圖 (數學)

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

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

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

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

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

定義

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

圖

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

一張圖（為了和有向圖區分，也稱無向圖；為了和多重圖區分，也稱簡單圖）是一個二元組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$的矩陣，其中每個元素A_ij表示節點i和j之間的邊的數量。對於一個簡單圖，總有$A_{ij}\in \{0,1\}$，分別表示「不相連」和「相連」，而$A_{ii}=0$（即一條邊的兩個頂點不能相同）。允許自環的圖上$A_{ii}$的取值可以是非負整數，而多重圖則允許任何$A_{ij}$的取值都是非負整數。無向圖的鄰接矩陣是對稱陣（$A_{ij}=A_{ji}$）。

有向圖

主條目：有向圖

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

邊為有方向的圖稱作有向圖（英語：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}\;{\textrm {and}}\;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的定義可以參考前面的無向圖和有向圖定義。在此定義下，有向圖和無向圖是混合圖的特殊情況。

賦權圖

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

賦權圖（英語：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-正則圖。

完全圖

主條目：完全圖

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

完全圖（英語：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₁, v₂, …, v_n，使得圖中的邊為$\{v_{i},v_{i+1}\}$，其中i=1, 2, …, n − 1，以及$\{v_{n},v_{1}\}$。循環圖的另一種定義是所有點的度都為2的連通圖。如果循環圖是另一個圖的子圖，則它是那個圖中的一個環。

樹和森林

主條目：樹 (圖論)

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

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

其它特殊的圖

一些進階的特殊圖包括：

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

例子

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

• 右邊的圖示是一個點集為$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. 
• Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability. 2010. 
• 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. ISBN 978-3-540-26183-4. 
• 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.  含有內容需登入查看的頁面 (link)
• 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. 

外部連結

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