立方图：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2023年10月10日 (二) 01:55的最新版本

在图论中，若一个图的每个顶点度数均为三，则称其为立方图（Cubic graph）、3-正则图或三次图。

彼得森图、汤玛森图等都是立方图。

对称性

1932年，Ronald M. Foster（英语：R. M. Foster）首先寻找立方对称图（英语：Symmetric graph）的例子，并收集为Foster census（英语：Foster census）。^[1]许多著名的图都是立方对称图，如汤玛森图、彼得森图等。威廉·湯瑪斯·圖特用满足下列性质的最大整数s来对立方对称图进行分类：图的自同构群在其所有长度为s的路径（其中不能有重复的边）组成的集合上作用是传递的。他证明了s最大只能取5，也即s的可能值是1到5。^[2]

图着色与独立集

根据布鲁克定理，除了K₄以外的任何连通立方图都可以用至多三种颜色染色。也即，这样的连通立方图至少存在一个包含n/3个顶点的独立集，其中n是该图的顶点数。

根据Vizing定理，任一立方图的边色数（英语：Edge chromatic number）只能为三或四。3-边着色又称Tait-着色，Tait-着色方式将边集分割为三个完美匹配。根据Kőnig's_theorem（英语：Kőnig%27s_theorem_(graph_theory)）每个二分立方图都有一个Tait-着色。

哈密顿回路

关于立方图是否具有哈密顿回路（英语：Hamiltonian path）有许多研究。1880年，P.G. Tait（英语：Peter Tait (physicist)）猜想任一立方多面体图都有哈密顿回路。1946年，威廉·湯瑪斯·圖特提出了Tait猜想（英语：Tait's conjecture）的反例，有46个点的图特图（英语：Tutte graph）。1971年，图特猜想所有的二分立方图都有哈密顿回路。然而Joseph Horton提出了图特猜想的反例，有96个点的Horton图（英语：Horton graph）。^[3]在这之后，Mark Ellingham（英语：Mark Ellingham）又提出了两个反例：Ellingham–Horton图（英语：Ellingham–Horton graph）。^[4]^[5]Barnette猜想（英语：Barnette's conjecture）（目前仍是猜想）将Tait猜想与图特猜想结合起来，称任一二分立方多面体图都有哈密顿回路。当一个立方图有哈密顿回路时，可以使用LCF表示法（英语：LCF notation）简洁地表示。

如果从所有 $n$ 阶立方图中随机选取一个，那么它有相当大概率有哈密顿回路：当 $n$ 趋近于无穷时，这个概率趋近于1。^[6]

David Eppstein（英语：David Eppstein）猜想任一 $n$ 阶立方图最多有 $2^{n/3}$ （约等于 $1.260^{n}$ ）条不同的哈密顿回路，且给出了极限情况下的例子。^[7]目前为止，得到证明的最佳估计为 $O({1.276}^{n})$ 。^[8]

另见

一些简单的立方图（英语：Table of simple cubic graphs）

参考文献

^ 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.

[Ref_Foster-1] 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 .

[2] 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） .

[3] Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.

[4] Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.

[5] 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  .

[6] 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 .

[7] 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） .

[8] Gebauer, H., On the number of Hamilton cycles in bounded degree graphs, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), 2008 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ 第1行： / 第1行： @@
 {{expand language|1=en|page=Cubic graph|time=2019-04-23T07:48:12+00:00}}
-{{unreferenced|time=2019-04-23T07:48:12+00:00}}
-[[File:Petersen1_tiny.svg|右|缩略图|[[佩特森圖|彼得森图]]是立方的。]]
+[[File:Petersen1_tiny.svg|右|缩略图|[[佩特森圖|彼得森图]]是立方图]]
-[[File:Biclique_K_3_3.svg|右|缩略图|180x180像素|[[完全二分图]] <math>K_{3,3}</math>是所谓“bicubic”的（立方的二分图）。]]
+[[File:Biclique_K_3_3.svg|右|缩略图|180x180像素|[[完全二分图]] <math>K_{3,3}</math>是立方二分图]]
-在[[图论]]中，如果图的所有顶点都有三度，那么这个图就是'''立方图，'''也被称为3-'''[[正則圖|正则图]]'''或'''三次图'''。
+在[[图论]]中，若一个[[图 (数学)|图]]的每个[[顶点 (图论)|顶点]][[度 (图论)|度数]]均为三，则称其为'''立方图'''（Cubic graph）、3-'''[[正則圖|正则图]]'''或'''三次图'''。
+[[佩特森圖|彼得森图]]、[[三間小屋問題|汤玛森图]]等都是立方图。
+== 对称性 ==
+年，{{link-en|Ronald M. Foster|R. M. Foster}}首先寻找立方{{link-en|对称图|Symmetric graph}}的例子，并收集为{{link-en|Foster census|Foster census}}。<ref name="Ref_Foster">{{Citation|first1=R. M.|last1=Foster|title=Geometrical Circuits of Electrical Networks|journal=[[Transactions of the American Institute of Electrical Engineers]]|volume=51|pages=309–317|year=1932|doi=10.1109/T-AIEE.1932.5056068|issue=2}}.</ref>许多著名的图都是立方对称图，如[[汤玛森图]]、[[彼得森图]]等。[[威廉·湯瑪斯·圖特]]用满足下列性质的最大整数''s''来对立方对称图进行分类：图的[[自同构群]]在其所有长度为''s''的路径（其中不能有重复的边）组成的集合上作用是传递的。他证明了''s''最大只能取5，也即''s''的可能值是1到5。<ref>{{Citation
+ | doi = 10.4153/CJM-1959-057-2
+ | last = Tutte
+ | first = W. T.
+ | journal = Can. J. Math.
+ | pages = 621–624
+ | title = On the symmetry of cubic graphs
+ | url = http://cms.math.ca/cjm/v11/p621
+ | volume = 11
+ | year = 1959
+ | accessdate = 2019-05-10
+ | archive-date = 2011-07-16
+ | archive-url = https://web.archive.org/web/20110716145555/http://cms.math.ca/cjm/v11/p621
+ }}.</ref>
+==图着色与独立集==
+根据[[布鲁克定理]]，除了''K''<sub>4</sub>以外的任何连通立方图都可以用至多三种颜色染色。也即，这样的连通立方图至少存在一个包含n/3个顶点的[[独立集]]，其中n是该图的顶点数。
+根据[[Vizing定理]]，任一立方图的{{link-en|边色数|Edge chromatic number}}只能为三或四。3-边着色又称Tait-着色，Tait-着色方式将边集分割为三个[[匹配_(图论)|完美匹配]]。根据{{tsl|en|Kőnig%27s_theorem_(graph_theory)|Kőnig's_theorem}}每个二分立方图都有一个Tait-着色。
+==哈密顿回路==
+关于立方图是否具有{{link-en|哈密顿回路|Hamiltonian path}}有许多研究。1880年，{{link-en|P.G. Tait|Peter Tait (physicist)}}猜想任一立方多面体图都有哈密顿回路。1946年，[[威廉·湯瑪斯·圖特]]提出了{{link-en|Tait猜想|Tait's conjecture}}的反例，有46个点的{{link-en|图特图|Tutte graph}}。1971年，图特猜想所有的二分立方图都有哈密顿回路。然而Joseph Horton提出了图特猜想的反例，有96个点的{{link-en|Horton图|Horton graph}}。<ref>Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.</ref>在这之后，{{link-en|Mark Ellingham|Mark Ellingham}}又提出了两个反例：{{link-en|Ellingham–Horton图|Ellingham–Horton graph}}。<ref>Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.</ref><ref>{{Citation|last1=Ellingham|first1=M. N.|last2=Horton|first2=J. D.|title= Non-Hamiltonian 3-connected cubic bipartite graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B| volume=34| pages=350–353| year=1983| doi=10.1016/0095-8956(83)90046-1|issue=3|doi-access=free}}.</ref>{{link-en|Barnette猜想|Barnette's conjecture}}（目前仍是猜想）将Tait猜想与图特猜想结合起来，称任一二分立方多面体图都有哈密顿回路。当一个立方图有哈密顿回路时，可以使用{{link-en|LCF表示法|LCF notation}}简洁地表示。
+如果从所有<math>n</math>阶立方图中随机选取一个，那么它有相当大概率有哈密顿回路：当<math>n</math>趋近于无穷时，这个概率趋近于1。<ref>{{citation
+ | last1 = Robinson | first1 = R.W.
+ | last2 = Wormald | first2 = N.C.
+ | doi = 10.1002/rsa.3240050209
+ | issue = 2
+ | journal = Random Structures and Algorithms
+ | pages = 363–374
+ | title = Almost all regular graphs are Hamiltonian
+ | volume = 5
+ | year = 1994}}.</ref>
+{{link-en|David Eppstein|David Eppstein}}猜想任一<math>n</math>阶立方图最多有<math>2^{n/3}</math>（约等于<math>1.260^n</math>）条不同的哈密顿回路，且给出了极限情况下的例子。<ref>{{citation
+ | last = Eppstein
+ | first = David
+ | authorlink = David Eppstein
+ | arxiv = cs.DS/0302030
+ | issue = 1
+ | journal = [[Journal of Graph Algorithms and Applications]]
+ | pages = 61–81
+ | title = The traveling salesman problem for cubic graphs
+ | url = http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf
+ | volume = 11
+ | year = 2007
+ | doi = 10.7155/jgaa.00137
+ | accessdate = 2020-12-27
+ | archive-date = 2021-02-24
+ | archive-url = https://web.archive.org/web/20210224121929/http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf
+ }}.</ref>目前为止，得到证明的最佳估计为<math> O({1.276}^n)</math>。<ref>{{citation
+ | last = Gebauer
+ | first = H.
+ | contribution = On the number of Hamilton cycles in bounded degree graphs
+ | title = Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08)
+ | url = https://epubs.siam.org/doi/pdf/10.1137/1.9781611972986.8
+ | year = 2008
+ }}.</ref>
+==另见==
+* {{link-en|一些简单的立方图|Table of simple cubic graphs}}
+== 参考文献 ==
+{{reflist}}
 == 外部連結 ==