对偶图中的H圈与平图的4着色  

Hamiltonian cycle in duality and 4-colouring of planar graph

作　　者：侴万禧[1] 李晓毅[2] 

机构地区：[1]安徽理工大学土木建筑学院,安徽淮南232001 [2]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2012年第3期322-326,共5页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10471096)

摘　　要：阐明了对偶图中的H圈与平图的2棵对偶树的相互依存关系,阐述了平图的4着色与2棵对偶树之间的相互依存关系。平图的顶点4着色以及2棵对偶树的分解决定了对偶图中的H圈,对偶图中的H圈也决定了平图的顶点4着色及2棵对偶树的分解。平图H圈决定了对偶图的2棵对偶树的分解及顶点4着色,对偶图的2棵对偶树的分解及对偶图的顶点4着色决定了平图的H圈的分解。2棵对偶树的2着色等价于平图的顶点4着色,内区与外区的分界线恰好是H圈。提出了多面体平图的H圈的构造步骤和多面体平图的顶点4着色步骤。介绍了12面体平图中30个H圈的构造,对偶图中对偶树的分解、以及对偶树的4着色。解决了任意平图中的H圈的分解方法和计数方法,为解决任意平图中的生成树的构造和计数问题奠定了基础。This paper clarifies not only the interdependent relation between Hamiltonian cycles in duality and paired of dual trees in planar graph,but also the relation between the 4-colouring of the dual and the paired of dual trees.The Hamiltonian cycle in the duality graph decides the paired of dual trees and 4-colouring of the vertex in planar graph.This condition in turn is also correct.The 2-colouring of the paired trees is equivalent to 4-colouring of the duality.The outside area within the boundary region occurs to be Hamiltonian cycle exactly.Its construction step of the Hamiltonian cycle in polyhedron planar graph and 4-colouring in polyhedron are given.A new method of constructing Hamiltonian cycle on the basis of decomposition with paired trees is proposed.Construction of 30 Hamiltonian cycles,decomposition with paired trees and 4-colouring of the dual are presented.Give the decomposition and counting method of arbitrary Hamiltonian cycle in planar graph,and lay the foundation for arbitrary Hamiltonian cycle with the construction of spanning trees.

关 键 词：H圈 平图 对偶图 4着色 对偶树 

分 类 号：O157[理学—数学]