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

本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=RUS,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图.     

平图的四着色与对偶图的H圈

阐明了平图中的H圈与对偶图顶点四着色的依存关系.提出了平图的顶点四着色和对偶图顶点四着色的具体步骤.介绍了多面体平图的H圈分解与对偶图顶点四着色,以及对偶图的H圈分解与平图的顶点四着色.讨论了平图及对偶图的H圈的个数,森林Fi的个数及顶点四着色方案数.     

两个只有路型二色子图的极大平面图

本文证明了极大平面图g9D和g12A,其每个四着色的每个二色子图都是路.并猜测在全部无分离三圈的极大平面图中这是仅有的两个图.     

基于平图的H圈分解的对偶图的四着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。     

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

阐明了平图的4着色及对偶树与对偶图中的H图的依存关系,以及对偶图的4着色及对偶树与平图中的H圈的依存关系。给出了平面H圈和对偶图顶点4着色的基本思路,得到了对偶图与三角剖分图之间的关系,并利用此关系提出了平图及对偶图的H圈及对偶树的分解方法和顶点4着色方法。这两种方法都是通过给出对偶图成平面的面中心的H圈得到对偶树,并对对偶树进行着色而得到的。介绍了46面体平图及对偶图中的H圈及对偶树的各种分解方案和顶点4着色方案。结果表明:任意平图中的H圈必定将对偶图分解为两棵对偶树,且两棵对偶树的2着色等价于对偶图的顶点4着色,从而使kempe四色猜想"证明"中的错误得以纠正。     

四正则平面图与其对偶图的哈密顿圈

Goodey证明每个三正则 3连通的面度全为 4或全为 6的平面图都是 Hamilton图 ,本文探讨四正则平面图与其对偶图的 Hamilton圈     

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

阐明了对偶图中的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圈的分解方法和计数方法,为解决任意平图中的生成树的构造和计数问题奠定了基础。     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图.两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系.面是平面图区别于非平面图的本质特征.同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的.任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过 D-过程画出.平面图与其对偶图互为对偶.显平面图与其隐对偶图合称为相伴对偶图.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

围长为4的平面图是4-可选色的

1994年，ThomassenC证明了每一个平面图是5-可选色的，于1995年，ThomassenC又证明了每一围长至少为5的平面图是3-可选色的．现用递推归纳法证明每一围长为4的平面图是个可选色的．甚至当确定图中任一个4圈的着色时，该结论也是成立的．     

极大平面图的导出四正则图的三着色

本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.     

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

阐明了平图中的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圈的个数。     

图的禁用子图和H—连通性

证明了如下结果：设Ｇ是３—连通图，如果Ｇ满足如下之一：（ｉ）｛Ｋ１，３，Ａ，Ｄ）－ｆｒｅｅ．（ｉｉ）｛Ｋ１，３，Ａ，Ｐ５｝－ｆｒｅｅ．（ｉｉｉ）｛Ｋ１，３，Ｉ｝－ｆｒｅｅ．（ｉｉｉｉ）｛Ｋ１，３，Ｚ３，Ｂ｝－ｆｒｅｅ．则Ｇ是Ｈ－连通的．     

关于（g,f）-3-覆盖图

设G是一个图,用V（G）和E（G）表示顶点集和边集,并设g和f是定义在V（G）上的两个非负整数值函数且g〈f。图G的一个（g,f）-因子是G的一个支撑子图F使对任意的x∈V（G）有g（x）≤dF（x）≤f（x）。如果过图G的任何三条边都有一个（g,f）-因子,则称图G是一个（g,f）-3-覆盖图,本文给出了一个图是（g,f）-3-覆盖图的一个充分条件。     

k-因子的哈密顿性质

借助Bauer定理给出了一个猜想的简短证明：如果图G含有k-因子且是2-连通的,并满足σ２（Ｇ）≥ｎ－ｋ,那么图G是哈密顿的.     

关于消去图的一个充分条件

设G是一个图,用V（G）和E（G）表示顶点集和边集,并设g和f是定义在V（G）上的两个非负整数值函数,且g     

（g，f，k）临界图的一个充分必要条件

设G是-个简单图,g和f是两个定义在V（G）上的整数值函数,且对所有的x∈V（G）都满足g（x）≤f（X）．如果删除G的任何k个顶点后,图G的其余部分含有-个（g,f）因子,那么称图G为一个（g,f,k）-临界图．本文给出了-个图是（g,f,k）-临界图的-个充要条件,并对这些奈件的应用作了讨论。进-步,本文研究了（g,f,k）-临界图的性质．