对偶图的H圈分解和相应的平图4着色

Hamiltonian cycle decomposition of dual graph and 4-colouring of planar graph

阐明了平图中的H圈与对偶图中的森林Fi及顶点4着色的依存关系,提出了一种基于H圈分解的任意平图的顶点4着色方法。介绍了20面体平图中的24个H圈及对偶图中的24个森林Fi及24种顶点4着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的4着色方案数。得到任意平图及其对偶图均能分解出H圈和森林Fi,任意平图及其对偶图均为可4着色的。得到了当平图为三角剖分图时,对偶图为多边形组合,H圈个数必大于其对偶图中的H圈的个数。平图为多边形组合时,其对偶图为三角剖分图,H圈的个数必小于对偶图中的H圈的个数。平图中森林Fi的个数或4着色方案数等于对偶图中的H圈的个数;对偶图中的森林Fi′的个数或4着色方案数等于平图中的H圈的个数。

The interdependent relation among Hamiltonian cycle in the planar graph,the forests Fi in the dual graph and 4-colouring vertex is illustrated.A method of vertex 4-colouring of the arbitrary planar graph based on the decomposition of the Hamiltonian cycle is proposed.The 24 Hamiltonian cycles in the 20-sided flat map and the 24 forests-Fi in the dual graph and 24 kinds of vertex 4-cdouing program are introduced.The number of Hamiltonian cycles Ci,the number of forests Fi and the number of schemes of vertex 4-colouring in both planar and dual graph are also discussed.It is concluded that the arbitrary planar graph and the dual graph can be decomposed into Hamiltonian cycle and forests-Fi and are 4-colouring.It is also concluded that when the planar graph is triangular subdivision graph,the dual graph is polygon combination and the number of the Hamiltonian cycle is greater than that of Hamiltonian cycle in the dual graph.When the planar graph is polygon combination,the dual graph is triangular subdivision graph and the number of the Hamiltonian cycle will be less than that of Hamiltonian cycle in the dual graph.The number of the forest Fi in the planar graph or the number of schemes of 4-colour is equal to that of Hamiltonian cycle in the dual graph,and the number of the forest Fi in the dual graph or the number of schemes of 4-colour is equal to that of Hamiltonian cycle in the planar graph.