平面图与对偶原理

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

利用对偶图求平面图的生成树数目

图的生成树数目是图的一个重要参数，求连通图生成树数目的方法有很多．本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目，求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单，该方法对于平面图可以进一步推广.     

中国建筑师问题与对偶问题的4着色

提出了中国建筑师问题,阐明了求解中国建筑师问题的基本思路。介绍了25个顶点、69个边、45个面的对偶图的顶点4着色的全过程。将对偶图分解成含2棵可以2着色的对偶树的森林,在以r、b两色为对偶树得到的顶点实施2着色,以y、g两色为对偶树得到的顶点实施2着色,从而实施对偶图顶点的4着色。阐述了对偶图的4着色关键是将对偶图分解出森林,提出了3个森林的分解方法,讨论了H路径的个数、森林的个数、对偶图的A区和B区划分方案、对偶图的顶点4着色方案数。解决了对偶图顶点的4着色问题,利用对偶图顶点4着色方法使Kempe四色猜想"证明"中的漏洞得到了弥补。将此种方法用于12面体、20面体、22面体、32面体的对偶图的4色问题,并取得了成功。     

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

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

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

多面体平图的4着色方法

讨论了多面体平图的4着色问题,将平图的面着色问题简化为平图面中心的顶点着色问题。提出了多面体4着色的基本思路,当顶点数p值很大并且有许多面交汇时,实现对偶图的顶点4着色问题借助于对偶图G(p,q,f)的两棵对偶树的分解,而对偶图G(p,q,f)两棵对偶树的分解又依靠对偶图G′(f,s,t)的Hamilton路径p的分解。概括了对偶图G(p,q,f)4着色的基本方法,同时在此基础上给出了8面体,12面体,20面体,32面体4着色的具体步骤,并以图形的形式给出了以上多面体4着色的具体方案。     

仙人掌链图的Hosoya多项式

1988年,对于连通图G,日本化学家Hosoya提出了一个基于距离的多项式,即H(G)≡H(G,x):=∑k≥0d(G,k)xk。仙人掌链图是一个具有如下性质的连通可平面图:其所有的内部面都是六边形;任意两个六边形要么无公共顶点,要么恰有一个公共顶点(邻接);任意三个六边形都没有公共顶点;任意一个六边形最多同时与两个六边形邻接。文章给出了仙人掌链图的Hosoya多项式。     

32面体展开图的对偶图G（p，q，f）的4着色

提出了基于对偶图G（p,g,f）的2棵对偶树T^A及T^B分解的对偶图的顶点4着色方法及对偶树的算法。介绍了32面体展开图的对偶图G（p,q,f）的4着色的全过程。     

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

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

连通、P3局部连通［5,3］-图的圈可扩性

如果图G的任意s个顶点的导出子图中至少含有t条边,则称G为［s,t］-图。设H是一个图,如果图G中任意一个同构于H的子图F,有G［N(F)-V(F)］连通,则称G是H-局部连通的。本文证明：阶数≥8的连通、P₃-局部连通的［5,3］-图是1-2可扩的(这里P₃表示3阶路)。     

不含三圈的双圈图的谱半径

Nikiforov等人最近将图谱研究与极值图论相结合,提出了谱Turán型问题:给定一个图F,设G是一个不含子图与F同构的n阶图,那么图G的谱半径至多是多少?双圈图是边数等于顶点数加1的简单连通图。近期,部分学者对双圈图的谱半径进行了研究,确定了双圈图谱半径的第1~10大值和相应的极图。受此启发,研究了不含三圈的双圈图,确定不含三圈的双圈图的谱半径的上界,并刻画了相应的极图。     

关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界．同时证明了：对没有４圈或任何两个３面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立．     

一类六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了一类六点八边图中尚未解决的3个图Gi(i=1,2,3)的图设计存在性问题,并证明了(v,G,1)-GD(i=1,2,3)存在的必要条件v=0,1(mod 16)且≥16也是充分的.从而给出了这类六点八边图图设计存在的完全解.     

无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断；要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...     

qp~2阶连通4度半传递图

称图X是半传递图,如果X的自同构群Aut(X)作用在其顶点集和边集上都传递,但作用在其弧集上非传递。本文证明了qp2(其中q相似文献   

具有最小Wiener指数的双圈图

一个图G的Wiener指数W(G)定义为G中所有点对的距离和,双圈图是一个具有n个点和n+1条边的连通图,我们根据两个圈的相对位置关系把双圈图分成三类,分别在这三类中给出了最小的Wiener指数,然后通过比较三类极值的大小得到了双圈图中具有最小Wiener指数的图。     

一个特殊六点七边图的图设计

六点七边图(不带孤立点的简单图)共有17个图，其中5个图已经解决．本文讨论了其余12个图中一个特殊图的图设计存在性问题，从而可以用类似的方法解决其余六点七边图(当顶点数为奇数且(7，G，1)-GD存在时)的图设计存在性问题．     

基于无向图转有向图的同构判别

无向同构图指的是在两个图中寻找顶点之间的映射关系,通过映射使原本形式各异的两图中的各条边保持对应的关系.为了有效提高寻找无向同构图的时间效率、简化操作,首先研究了无向图同构的矩阵存储方式,并针对性地提出了把无向图转换为有向图的同构算法.与矩阵存储算法相比,该判定算法的时间更为简短.最后给出了实现该算法的相关程序以及用该算法对无向图进行判定的过程和结果.