平面三次图中的二元哈米顿圈  

Bihamilton Cycles in 3-Regular Plane Graph

作　　者：许寿椿[1] 

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

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

摘　　要：本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=R∪S,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图.In this paper,we definite Bihamiltonian cycles of 3-reguale plane and prove basic 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 Bihamiltonian,if and only if, graph g has a t-C-t type of Gk, in other words, the graph g has 4-coloring C and the 4-coloring C has a dual bichromatic subgraph Gk = Gαβ ∪ Gγβ, one of Gαβ and Gγβ is a connected and contains a cycle, other has two tree subgraphs. Corollary Let Ng be the number of t-C-t type Gk of all 4-colorings of maximal planar graph g, Nd be the number of BiHamiltonian cycles of 3-reguale plane graph D（g） and D（g） be the dual of g, then Ng = Nd/2. An algorithm to generate all Bihamihonian cycles of 3-reguale plane graph is described.

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

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