完全圖
任兩相異節點間洽有一條邊相連的無向圖 / 維基百科,自由的 encyclopedia
在圖論中,完全圖是一個簡單的無向圖,其中每一對不同的頂點都只有一條邊相連。完全有向圖是一個有向圖,其中每一對不同的頂點都只有一對邊相連(每個方向各一個)。
圖論起源於歐拉在1736年解決七橋問題上做的工作,但是通過將頂點放在正多邊形上來繪製完全圖的嘗試,早在13世紀拉蒙·柳利 的工作中就出現了[1]。這種畫法有時被稱作神秘玫瑰。
性質
在個頂點上的完全圖被記作
,有些文獻認為這個記號中的字母
代表德文 komplett,[2] 但是完全圖的德文vollständiger Graph,並沒有字母
,其他文獻認為這個記號是為了紀念卡齊米日·庫拉托夫斯基對圖論的貢獻。[3]
有
條邊,並且是
正則圖。所有的完全圖都是它們本身的極大團。它們是極大連通的,因為唯一的割點集(vertex cut)是所有頂點的集合。完全圖的補圖是空圖(empty graph)。
完全圖的每一條邊都被附上了定向之後形成的有向圖被稱作輪轉(tournament)。
可以被分解成
個樹
,且
有
個頂點。[4] Ringel猜想可以被表述為:完全圖
能否被分解成一些完全相同的
階樹。[5] 對於足夠大的
,這個結論是成立的。[6][7]
完全圖的匹配數按照它們的階數排列,由telephone numbers給出: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (OEIS數列A000085)。這些數字給出了在階圖上Hosoya指數(英語:Hosoya index)的最大可能值。[8] 在
上的完美匹配(perfect matching)的個數為
!!。
對於階數小於等於27階的完全圖來說,它們的交叉數是已知的,
的交叉數是7233或者7234。階數更大的交叉數由Rectilinear Crossing Number project在收集。[9]
的Rectilinear交叉數為:0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (OEIS數列A014540)。
幾何和拓撲
階完全圖可以代表
-單純形。幾何上,
構成了三角形,
構成了四面體,依次類推。Császár polyhedron, 一個非凸的和環面同胚的多邊形,可以由
作為它的骨架skeleton。
到
都是平面圖,然而當
時,在平面上繪製
時總是會有交叉,另外,非平面圖
在刻畫平面圖的性質時起着重要的作用:根據Kuratowski's theorem,當且僅當一個圖不包含
,以及完全二分圖
作為它的一部分時,這個圖是平面圖。根據Wagner's theorem,當且僅當一個圖不包含
,以及完全二分圖
作為它的圖子式時,這個圖是平面圖。
作為Petersen family的一部分,
起到了一個了類似的作用,為了保證一個圖的linkless embedding,它不能作為這個圖的圖子式出現。[10] 更精確地說,Conway和Gordon[11] 證明了每一個
在3維空間中的嵌入都是intrinsically linked 的,且至少有一對linked的三角形。Conway和Gordon還證明了 任意
在3維空間中的嵌入都包含了一個作為一個非平凡的扭結嵌入在空間裡的哈密頓環。
例子
另見
- Fully connected network:全連接網絡
- 完全二分圖,一種特殊的二分圖,其中每個節點都和另一個部分的所有節點相連。
參考文獻
- Knuth, Donald E., Two thousand years of combinatorics, Wilson, Robin; Watkins, John J. (編), Combinatorics: Ancient and Modern, Oxford University Press: 7–37, 2013 [2020-10-04], ISBN 978-0191630620, (原始內容存檔於2020-07-29).
- Gries, David; Schneider, Fred B., A Logical Approach to Discrete Math, Springer-Verlag: 436, 1993 [2020-10-04], ISBN 0387941150, (原始內容存檔於2014-01-02).
- Pirnot, Thomas L., Mathematics All Around, Addison Wesley: 154, 2000, ISBN 9780201308150.
- Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk. Optimal packings of bounded degree trees (PDF). Journal of the European Mathematical Society. 2019-08-05, 21 (12): 3573–3647 [2020-10-04]. ISSN 1435-9855. doi:10.4171/JEMS/909. (原始內容存檔 (PDF)於2020-03-09) (英語).
- Ringel, G. Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice. 1963.
- Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny. A proof of Ringel's Conjecture. 2020-01-08. arXiv:2001.02665
[math.CO].
- Hartnett, Kevin. Rainbow Proof Shows Graphs Have Uniform Parts. Quanta Magazine. [2020-02-20]. (原始內容存檔於2020-02-20) (英語).
- Tichy, Robert F.; Wagner, Stephan, Extremal problems for topological indices in combinatorial chemistry (PDF), Journal of Computational Biology, 2005, 12 (7): 1004–1013 [2020-10-04], PMID 16201918, doi:10.1089/cmb.2005.12.1004, (原始內容存檔 (PDF)於2017-09-21).
- Oswin Aichholzer. Rectilinear Crossing Number project. [2020-10-04]. (原始內容存檔於2007-04-30).
- Robertson, Neil; Seymour, P. D.; Thomas, Robin, Linkless embeddings of graphs in 3-space, Bulletin of the American Mathematical Society, 1993, 28 (1): 84–89, MR 1164063, arXiv:math/9301216
, doi:10.1090/S0273-0979-1993-00335-5.
- Conway, J. H.; Cameron Gordon. Knots and Links in Spatial Graphs. J. Graph Th. 1983, 7 (4): 445–453. doi:10.1002/jgt.3190070410.