跳转到内容

立方图

维基百科，自由的百科全书

这是本页的一个历史版本，由Candidadida（留言 | 贡献）在2020年12月27日 (日) 08:32 （→图着色：​ 修正笔误）编辑。这可能和当前版本存在着巨大的差异。

彼得森图是立方图
完全二分图 是立方二分图

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

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

对称性

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

图着色

主条目：图着色问题

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

根据Vizing定理，任一立方图的边色数（英语：Edge chromatic number）只能为三或四。

参考文献

  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, doi:10.4153/CJM-1959-057-2 .

外部連結

检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=立方图&oldid=63448950”