立方圖
此條目可參照英語維基百科相應條目來擴充。 (2019年4月23日) |
在圖論中,若一個圖的每個頂點度數均為三,則稱其為立方圖(Cubic graph)、3-正則圖或三次圖。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/220px-Petersen1_tiny.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Biclique_K_3_3.svg/180px-Biclique_K_3_3.svg.png)
對稱性
編輯1932年,Ronald M. Foster首先尋找立方對稱圖的例子,並收集為Foster census。[1]許多著名的圖都是立方對稱圖,如湯瑪森圖、彼得森圖等。威廉·湯瑪斯·圖特用滿足下列性質的最大整數s來對立方對稱圖進行分類:圖的自同構群在其所有長度為s的路徑(其中不能有重複的邊)組成的集合上作用是傳遞的。他證明了s最大只能取5,也即s的可能值是1到5。[2]
圖着色與獨立集
編輯根據布魯克定理,除了K4以外的任何連通立方圖都可以用至多三種顏色染色。也即,這樣的連通立方圖至少存在一個包含n/3個頂點的獨立集,其中n是該圖的頂點數。
根據Vizing定理,任一立方圖的邊色數只能為三或四。3-邊着色又稱Tait-着色,Tait-着色方式將邊集分割為三個完美匹配。根據Kőnig's_theorem每個二分立方圖都有一個Tait-着色。
哈密頓迴路
編輯關於立方圖是否具有哈密頓迴路有許多研究。1880年,P.G. Tait猜想任一立方多面體圖都有哈密頓迴路。1946年,威廉·湯瑪斯·圖特提出了Tait猜想的反例,有46個點的圖特圖。1971年,圖特猜想所有的二分立方圖都有哈密頓迴路。然而Joseph Horton提出了圖特猜想的反例,有96個點的Horton圖。[3]在這之後,Mark Ellingham又提出了兩個反例:Ellingham–Horton圖。[4][5]Barnette猜想(目前仍是猜想)將Tait猜想與圖特猜想結合起來,稱任一二分立方多面體圖都有哈密頓迴路。當一個立方圖有哈密頓迴路時,可以使用LCF表示法簡潔地表示。
如果從所有 階立方圖中隨機選取一個,那麼它有相當大概率有哈密頓迴路:當 趨近於無窮時,這個概率趨近於1。[6]
David Eppstein猜想任一 階立方圖最多有 (約等於 )條不同的哈密頓迴路,且給出了極限情況下的例子。[7]目前為止,得到證明的最佳估計為 。[8]
另見
編輯參考文獻
編輯- ^ Foster, R. M., Geometrical Circuits of Electrical Networks, Transactions of the American Institute of Electrical Engineers, 1932, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068.
- ^ Tutte, W. T., On the symmetry of cubic graphs, Can. J. Math., 1959, 11: 621–624 [2019-05-10], doi:10.4153/CJM-1959-057-2, (原始內容存檔於2011-07-16).
- ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
- ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
- ^ Ellingham, M. N.; Horton, J. D., Non-Hamiltonian 3-connected cubic bipartite graphs, Journal of Combinatorial Theory, Series B, 1983, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1 .
- ^ Robinson, R.W.; Wormald, N.C., Almost all regular graphs are Hamiltonian, Random Structures and Algorithms, 1994, 5 (2): 363–374, doi:10.1002/rsa.3240050209.
- ^ Eppstein, David, The traveling salesman problem for cubic graphs (PDF), Journal of Graph Algorithms and Applications, 2007, 11 (1): 61–81 [2020-12-27], arXiv:cs.DS/0302030 , doi:10.7155/jgaa.00137, (原始內容 (PDF)存檔於2021-02-24).
- ^ Gebauer, H., On the number of Hamilton cycles in bounded degree graphs, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), 2008.
外部連結
編輯- Royle, Gordon. Cubic symmetric graphs (The Foster Census). (原始內容存檔於2011-10-23).
- 埃里克·韋斯坦因. Bicubic Graph. MathWorld.
- 埃里克·韋斯坦因. Cubic Graph. MathWorld.