圖 (數學)
在離散數學中,圖(英語:graph)是用於表示物體與物體之間存在某種關係的結構。數學抽象後的「物體」稱作節點或頂點(vertex, node, point),節點間的相關關係則稱作邊。[1]在描繪一張圖的時候,通常用一組點或小圓圈表示節點,其間的邊則使用直線或曲線。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/220px-6n-graf.svg.png)
圖中的邊可以是有方向或沒有方向的。例如在一張圖中,如果節點表示聚會上的人,而邊表示兩人曾經握手,則該圖就是沒有方向的,因為甲和乙握過手也意味著乙一定和甲握過手。相反,如果一條從甲到乙的邊表示甲欠乙的錢,則該圖就是有方向的,因為「曾經欠錢」這個關係不一定是雙向的。前一種圖稱為無向圖,後一種稱為有向圖。
圖是圖論中的基本概念。1878年,詹姆斯·西爾維斯特首次使用「圖」這一名詞:他用圖來表示數學和化學分子結構之間的關係(他稱為「化學圖」,英語:chemico-graphical image)。[2][3]
定義
編輯在圖論中,圖的定義有很多。下面是一些比較基本的定義方式以及與它們相關的數學結構。
圖
編輯一張圖(為了和有向圖區分,也稱無向圖;為了和多重圖區分,也稱簡單圖)[4][5]是一個二元組G = (V, E),其中集合V中的元素稱為節點,集合E中的元素是兩個節點組成的無序對,稱為邊。集合V稱為點集,E稱為邊集。
一條邊 上的兩個節點x和y稱作這條邊的頂點或端點;也說這條邊連接了節點x和y,或這條邊與x和y關聯(英語:incident)。一個節點可以不屬於任何邊,即它不與任何節點相連。由於 是無序對, 和 表示的是同一個元素。
更一般地,多重圖的定義中允許同一對節點之間存在多條不同的邊。在特定語境中,多重圖也可以直接稱作圖。[6][7]此時,在上面的定義中,集合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,如果 是一條邊,則稱它們是鄰接的。一張圖因此可以用其鄰接矩陣A來表示,即一個 的矩陣,其中每個元素Aij表示節點i和j之間的邊的數量。對於一個簡單圖,總有 ,分別表示「不相連」和「相連」,而 (即一條邊的兩個頂點不能相同)。允許自環的圖上 的取值可以是非負整數,而多重圖則允許任何 的取值都是非負整數。無向圖的鄰接矩陣是對稱陣( )。
有向圖
編輯邊為有方向的圖稱作有向圖(英語:directed graph或digraph)。
有向圖的一種比較嚴格的定義[8]是這樣的:一個二元組 ,其中
- 是節點的集合;
- 是邊(也稱為有向邊,英語:directed edge或directed link;或弧,英語:arcs)的集合,其中的元素是節點的有序對。
為了和多重圖區分,這樣的有向圖也稱為有向簡單圖。
在從 到 的邊 上,節點 和 稱作這條邊的頂點,其中 是起點或尾(英語:tail), 是終點或頭。[9]也說這條邊連接了節點 和 、這條邊與節點 和 關聯。一張有向圖中的節點可以不屬於任何一條邊。邊 稱為邊 的反向邊。
節點的出度(英語:out-degree)是指起點為該節點的邊的數量;節點的入度(英語:in-degree)是指終點為該節點的邊的數量。
更一般地,如果一張有向圖允許多條頭尾都分別相同的邊,則稱這樣的圖為有向多重圖,這樣的邊稱為多重邊。一種允許多重邊的有向圖定義方法如下[8]:一個有向圖是這樣的三元組 :
- 是節點的集合;
- 是邊的集合;
- 是一個關聯函數,將每條邊映射到一個由頂點組成的有序對上(即一條邊被按順序關聯到兩個頂點)。
自環是指一條起點和終點相同的邊。前面的兩個定義都不允許自環,因為若節點 上有一個自環,則邊 存在;但這樣的邊不在 中。因此,如果要允許自環,則上面的定義要做修改:對於有向簡單圖, 的定義應該修改為 ;對於有向多重圖, 的定義應該修改為 。為了避免定義不清,這樣的圖分別稱作允許自環的有向簡單圖或允許自環的有向多重圖(英語:quiver)。
在允許自環的有向簡單圖 中,邊是 上的一個齊次關係 ,稱作 上的鄰接關係。 對於頂點是 和 的邊 ,我們說 和 是彼此鄰接的,記作 。
混合圖
編輯邊既可以有向、也可以無向的圖稱作混合圖。混合簡單圖是一個多元組G = (V, E, A),而混合多重圖則是多元組G = (V, E, A, ϕE, ϕA),其中V、E(無向邊集)、A(有向邊集)、ϕE、ϕA的定義可以參考前面的無向圖和有向圖定義。在此定義下,有向圖和無向圖是混合圖的特殊情況。
賦權圖
編輯賦權圖(英語:weighted graph,也稱加權圖、網絡(英語:network))[10][11]是指每條邊都對應有一個數字(即「權重」,weight)的圖。[12]根據具體問題,權重可以表示諸如費用、長度或容量等意義。這樣的圖會出現在最短路徑問題和旅行商問題等問題中。
基本術語
編輯- 子圖(subgraph):對於圖 和圖 ,若 且 ,則稱 是 的子圖。
- 生成子圖(spanning subgraph):指滿足條件 的 的子圖 。
- 鏈(chain或walk)、軌跡(trail)、路徑(path):鏈是頂點 和邊 交替出現的序列 稱作一個長度為k的鏈,其中 和 為其端點,其餘頂點為內部點。所有邊都不相同的鏈稱為軌跡(簡稱跡)。所有頂點都不相同的軌跡稱為路徑(簡稱路)。在有向圖中,若鏈(跡、路)的方向和其中每條邊的方向一致,則稱其為有向鏈(跡、路)。[13]
- 兩端點相同的鏈和跡分別稱為閉鏈(或環,cycle)、閉跡(或迴路,circuit)。
- 距離(Distance): 從頂點 出發到頂點 的最短路徑若存在,則此路徑的長度稱作從 到 的距離。
特殊的圖
編輯正則圖
編輯正則圖是指每個節點的鄰居(英語:neighbor)數量都相同的圖,即每個節點的度都相同的圖。節點的度為k的正則圖也稱作k-正則圖。
完全圖
編輯完全圖(英語:complete graph)是指每對節點之間都有一條邊相連的圖。一張完全圖包含簡單圖所有可能出現的邊。
有限圖
編輯有限圖(英語:finite graph)是指點集和邊集是有限集的圖。否則,則稱為無限圖。在不加說明的情況下,圖論中討論的圖大多是有限圖。
連通圖
編輯在無向圖中,如果存在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)是指其節點可以列為v1, v2, …, vn,使得圖中的邊為 ,其中i=1, 2, …, n − 1,以及 。循環圖的另一種定義是所有點的度都為2的連通圖。如果循環圖是另一個圖的子圖,則它是那個圖中的一個環。
樹和森林
編輯樹是指任意兩點之間都有且僅有一條路徑的無向圖。等價地,樹是一個連通無環無向圖。
森林是指任意兩點之間至多僅有一條路徑的無向圖。等價地,森林是一個無環無向圖,或一組樹的無交並。
其它特殊的圖
編輯一些進階的特殊圖包括:
例子
編輯圖運算
編輯圖上可以進行一些運算或變換,使一個圖變為另一個圖:
圖的推廣
編輯在超圖中,允許一條邊連接多於兩個節點。
無向圖可以看作是由1-單純形(邊)和0-單純形(節點)組成的單純復形。由此,復形成為圖的推廣,其中允許維度更高的單純形。
圖可以看作是一種擬陣。
參見
編輯參考資料
編輯腳註
編輯- ^ 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.
- ^ 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. . The term "graph" first appears in this paper on page 65.
- ^ 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).
- ^ Bender & Williamson 2010,第148頁.
- ^ 參見 Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
- ^ Bender & Williamson 2010,第149頁.
- ^ Graham et al., p. 5.
- ^ 8.0 8.1 Bender & Williamson 2010,第161頁.
- ^ 徐 2004,第1頁.
- ^ Strang, Gilbert, Linear Algebra and Its Applications 4th, Brooks Cole, 2005 [2021-08-14], ISBN 978-0-03-010567-8, (原始內容存檔於2020-09-20)
- ^ Lewis, John, Java Software Structures 4th, Pearson: 405, 2013, ISBN 978-0133250121
- ^ 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.
- ^ 徐 2004,第20-21頁.
- ^ 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).
- ^ 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).