平面三次图哈米尔顿性的一个充要条件  

Sufficient and Necessary Condition on Hamiltonian 3-Regular Plane Graph

作　　者：许寿椿[1] 

机构地区：[1]中央民族大学理学院,北京100081

出　　处：《中央民族大学学报（自然科学版）》2008年第3期11-16,共6页Journal of Minzu University of China(Natural Sciences Edition)

摘　　要：本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色.即Dg的对偶极大平面图g有四着色C,该四着色的某组对偶二色子图Gk的两个分支都是树.据此得到求出图Dg全部哈米尔顿圈的算法,该方法已经成功处理了批量例图.In this paper, we proved Theorem 1 and its Corollary. Theorem 1 let g be a maximal planar graph, D（g） be a 3-regular plane graph and D（g） be dual of g, then the D（g） is Hamiltonian ,if and only if, graph g has a t-t type of Gk, in other words, the graph g has 4-coloring C and the 4-coloring C has a dual biehromatie subgraph Gk = Gαβ ∪ Gγδ, each of Gαβ, Gγδ is a tree. Corollary let Ng be the number of t-t type Gk of all 4-colorings of maximal planar graph g, Nd be the number of Hamihonian cycles of 3-reguale plane graph D（g） and D（g） be the dual of g, then Ng = Nd. An algorithm to generate all Hamiltonian cycles of 3-reguale plane graph is described.

关 键 词：四色问题 极大平面图 平面三正则图 哈米尔顿圈 

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