共查询到16条相似文献,搜索用时 60 毫秒
1.
本文在论文[1]的基础上给出极大平面图的另外一种商图,即极大平面图对偶二色子图结构特性图.证明极大平面图对偶二色于图特性图是树,并给出它的若干性质. 相似文献
2.
两个只有路型二色子图的极大平面图 总被引:1,自引:1,他引:0
许寿椿 《中央民族大学学报(自然科学版)》2005,14(1):5-9
本文证明了极大平面图g9D和g12A,其每个四着色的每个二色子图都是路.并猜测在全部无分离三圈的极大平面图中这是仅有的两个图. 相似文献
3.
杨宁 《中央民族大学学报(自然科学版)》2005,14(4):305-310
本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系. 相似文献
4.
程斌 《中央民族大学学报(自然科学版)》2005,14(3):209-213,240
本文通过分析三次图中面的奇偶性及组合情况,引出了可边三色块的概念,接着用面扩树方式给出了三次图中大量的可边三色块,在这些可边三色块中导出了三次图的一些边三色解. 相似文献
5.
6.
许宝刚 《山东大学学报(理学版)》1994,(1)
对平面图G,使得V(G)∪(G)∪F(G)中相邻或相关元素均着不同色的最少颜色数,称为G的完备色数xe(G).本文证明了若G是极大平面图或其同胚图,xe(G)≤Δ(G)+4. 相似文献
7.
8.
平面三次图哈米尔顿性的一个充要条件 总被引:1,自引:1,他引:0
许寿椿 《中央民族大学学报(自然科学版)》2008,17(3):11-16
本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色.即Dg的对偶极大平面图g有四着色C,该四着色的某组对偶二色子图Gk的两个分支都是树.据此得到求出图Dg全部哈米尔顿圈的算法,该方法已经成功处理了批量例图. 相似文献
9.
关于非平面图染色的一个猜想 《山东科学》2017,30(3):94-97
本文提出以下猜想:若θ(G)=2,则χ(G)≤9;若θ(G)≥3,则χ(G)≤6θ(G)-1。证明了当 |S|∈{p,p-1,p-2,p-3,p-4,p-5}时,该猜想是正确的。 相似文献
10.
11.
12.
针对实际中的一类连接问题建立了网络模型,给出了便于计算机实现的算法,即:通过依次收缩各边简化网络G= ( V,E,W) ,最终得到最小生成树;然后恢复各边和顶点,从而得到了此类问题的最优解。 相似文献
13.
14.
完整地研究了寻找一个图的全部极大独立集所需要的理论、寻找范围、计算公式和枚举方法,采用有根树描述,以邻接矩阵中任意一行所对应的顶点为根,再以该行中各个非零元素所对应的那些顶点为根,按照文中所述方法生成有根树,这些有根树就描述出图的全部极大独立集,本方法已用计算机程序实现。 相似文献
15.
杨宁 《中央民族大学学报(自然科学版)》2005,14(2):141-145
本文给出一个通过直接寻找路路分解的方法求出图的自同构群,其算法的复杂性是多项式级的,对于一百多个点的图形也能顺利求解. 相似文献
16.
有向图具有哈密顿圈的一个充要条件 总被引:4,自引:0,他引:4
徐尚进 《广西大学学报(自然科学版)》1999,24(2):106-107,114
通过有向图的邻接矩阵的轨道来刻划图的哈顿圈的问题。 相似文献