圖 (數學)

由点和边组成的数学结构

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

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

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

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

定義

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

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

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

一條邊 上的兩個節點xy稱作這條邊的頂點端點;也說這條邊連接了節點xy,或這條邊與xy關聯(英語:incident)。一個節點可以不屬於任何邊,即它不與任何節點相連。由於 是無序對,  表示的是同一個元素。

更一般地,多重圖的定義中允許同一對節點之間存在多條不同的邊。在特定語境中,多重圖也可以直接稱作圖。[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)。具體地說,對於兩個節點xy,如果 是一條邊,則稱它們是鄰接的。一張圖因此可以用其鄰接矩陣A來表示,即一個 的矩陣,其中每個元素Aij表示節點ij之間的邊的數量。對於一個簡單圖,總有 ,分別表示「不相連」和「相連」,而 (即一條邊的兩個頂點不能相同)。允許自環的圖上 的取值可以是非負整數,而多重圖則允許任何 的取值都是非負整數。無向圖的鄰接矩陣是對稱陣( )。

有向圖

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

邊為有方向的圖稱作有向圖(英語:directed graphdigraph)。

有向圖的一種比較嚴格的定義[8]是這樣的:一個二元組 ,其中

  •  節點的集合;
  •  (也稱為有向邊,英語:directed edgedirected link;或,英語:arcs)的集合,其中的元素是節點的有序對。

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

在從  的邊  上,節點  稱作這條邊的頂點,其中 起點(英語:tail), 終點[9]也說這條邊連接了節點  、這條邊與節點  關聯。一張有向圖中的節點可以不屬於任何一條邊。邊 稱為邊 反向邊

節點的出度(英語:out-degree)是指起點為該節點的邊的數量;節點的入度(英語:in-degree)是指終點為該節點的邊的數量。

更一般地,如果一張有向圖允許多條頭尾都分別相同的邊,則稱這樣的圖為有向多重圖,這樣的邊稱為多重邊。一種允許多重邊的有向圖定義方法如下[8]:一個有向圖是這樣的三元組 

  •  是節點的集合;
  •  是邊的集合;
  •  是一個關聯函數,將每條邊映射到一個由頂點組成的有序對上(即一條邊被按順序關聯到兩個頂點)。

自環是指一條起點和終點相同的邊。前面的兩個定義都不允許自環,因為若節點 上有一個自環,則邊 存在;但這樣的邊不在 中。因此,如果要允許自環,則上面的定義要做修改:對於有向簡單圖, 的定義應該修改為 ;對於有向多重圖, 的定義應該修改為 。為了避免定義不清,這樣的圖分別稱作允許自環的有向簡單圖允許自環的有向多重圖(英語:quiver英語Quiver (mathematics))。

在允許自環的有向簡單圖 中,邊是 上的一個齊次關係英語Binary relation#Homogeneous relation ,稱作 上的鄰接關係。 對於頂點是  的邊 ,我們說  是彼此鄰接的,記作 

混合圖

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

賦權圖

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

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

基本術語

  • 子圖subgraph):對於圖 和圖 ,若  ,則稱  的子圖。
  • 生成子圖spanning subgraph):指滿足條件  的子圖 
  • (chain或walk)、軌跡(trail)、路徑(path):鏈是頂點 和邊 交替出現的序列 稱作一個長度為k的鏈,其中  為其端點,其餘頂點為內部點。所有邊都不相同的鏈稱為軌跡(簡稱跡)。所有頂點都不相同的軌跡稱為路徑(簡稱路)。在有向圖中,若鏈(跡、路)的方向和其中每條邊的方向一致,則稱其為有向鏈(跡、路)。[13]
  • 兩端點相同的鏈和跡分別稱為閉鏈(或環,cycle)、閉跡(或迴路,circuit)。
  • 距離(Distance): 從頂點 出發到頂點 的最短路徑若存在,則此路徑的長度稱作從  的距離。

特殊的圖

正則圖

正則圖是指每個節點的鄰居(英語:neighbor)數量都相同的圖,即每個節點的度都相同的圖。節點的度為k的正則圖也稱作k-正則圖。

完全圖

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

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

有限圖

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

連通圖

在無向圖中,如果存在xy之間的路徑,則稱此兩節點的無序對 連通的;否則,則稱此兩點是非聯通的。

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

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

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

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

二分圖

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

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

平面圖

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

循環圖

階為n≥3循環圖(英語:cycle graph)或環形圖(英語:circular graph)是指其節點可以列為v1, v2, …, vn,使得圖中的邊為 ,其中i=1, 2, …, n − 1,以及 。循環圖的另一種定義是所有點的度都為2的連通圖。如果循環圖是另一個圖的子圖,則它是那個圖中的一個

樹和森林

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

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

其它特殊的圖

一些進階的特殊圖包括:

例子

 
一張6個節點和7條邊的圖
  • 右邊的圖示是一個點集為 、邊集為 的圖。
  • 計算機科學中,有向圖可以用於表示概念圖有限狀態自動機,以及其它許多數據結構。
  • 任意集合X上的二元關係R都可定義一個有向圖。X中的元素xy有一條邊,若且唯若xRy
  • 有向圖可以用於表示信息網絡。例如,在推特上,用戶之間的關注關係可以用有向圖表示。[14][15]

圖運算

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

圖的推廣

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

無向圖可以看作是由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:
  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. ^ 8.0 8.1 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.

文獻

外部連結