共查询到17条相似文献,搜索用时 46 毫秒
1.
平面图的4—着色的简单布尔方程表示 总被引:1,自引:0,他引:1
乌力吉 《内蒙古大学学报(自然科学版)》2001,32(1):1-5
如果一个无环平面图G至多有一个非三角形的面,则称G为准极大平面图(near-trian-gulation)本给出了极大平面图和准极大平面图4-着色的一类布尔方程表示式,该布尔方程所含变元较少,结构简单,具有良好的递归性质,为利用计算机寻找给定平面图的4-着色提供了很好的算法。 相似文献
2.
3.
许宝刚 《山东大学学报(理学版)》1994,(1)
对平面图G,使得V(G)∪(G)∪F(G)中相邻或相关元素均着不同色的最少颜色数,称为G的完备色数xe(G).本文证明了若G是极大平面图或其同胚图,xe(G)≤Δ(G)+4. 相似文献
4.
图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长. 相似文献
5.
平面图正常4—着色数的一个计算公式 总被引:2,自引:0,他引:2
乌力吉 《内蒙古大学学报(自然科学版)》2001,32(2):119-124
四色定理等价于任何准极大平面图(near-triangulation)至少有一个正常4-着色。给出了对任意给定的准极大平面图都能准确求出其正常4-着色数的计算公式,该公式的复杂性揭示了四色定理本身所蕴涵的难度。为研究四色定理提供了一条与以往不同的途径。 相似文献
6.
7.
周杰 《东北师大学报(自然科学版)》2002,34(2):16-21
给出了临界极大外平面图以及最大度临界极大外平面图的定义,并讨论了它们的性质,为研究极大外平面图的四染色提供了一种新方法。 相似文献
8.
平面图着色的遗传算法 总被引:6,自引:0,他引:6
洪斌 《贵州大学学报(自然科学版)》1999,16(4):297-302
基于遗传算法的思想 ,建立了一个用四种不同颜色对平面图结点进行着色的快速算法。 相似文献
9.
10.
关于平面图3-可着色的一个定理 总被引:1,自引:0,他引:1
Borodin和Raspaud提出一个猜想:任何既没有5-圈也没有相邻三角形的平面图是3-可着色.这个猜想强化了Steinberg提出的猜想.在本文中,我们研究了没有5-,6-,9-圈并且没有相邻三角形的平面图的结构.利用这个结构,证明了这类图是3-可着色的.它加强了由Borodin及Sanders和Zhao的结果,并且又是对Borodin和Raspaud猜想的一个正面的支持. 相似文献
11.
1994年,ThomassenC证明了每一个平面图是5-可选色的,于1995年,ThomassenC又证明了每一围长至少为5的平面图是3-可选色的.现用递推归纳法证明每一围长为4的平面图是个可选色的.甚至当确定图中任一个4圈的着色时,该结论也是成立的. 相似文献
12.
阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。 相似文献
13.
本文完全刻画了群环ZnD4的零因子集合,得到diam(Γ(ZnD4))=2当且仅当n=2t,否则diam(Γ(ZnD4))=3;(-Γ)(ZnD4)为非平面图;gr(Γ(ZnD4))=3等一些结果,并且给出了(-Γ)(ZnD4)的中心. 相似文献
14.
研究平面图的动态着色数,通过定义一个算法得到强导出图.利用颜色对换的思想来研究平面图动态着色的上界问题,得到结论:若G是平面图,则χd(G)≤5. 相似文献
15.
平图的四着色与对偶图的H圈 总被引:7,自引:6,他引:1
阐明了平图中的H圈与对偶图顶点四着色的依存关系.提出了平图的顶点四着色和对偶图顶点四着色的具体步骤.介绍了多面体平图的H圈分解与对偶图顶点四着色,以及对偶图的H圈分解与平图的顶点四着色.讨论了平图及对偶图的H圈的个数,森林Fi的个数及顶点四着色方案数. 相似文献
16.
17.
《内蒙古师范大学学报(自然科学版)》2015,(5)
确定一个图的扩容图的自同构群是一个比较困难的问题.通过完全图的完全扩容图的自同构群与完全图的自同构群之间的特殊关系,推导出完全图的完全扩容图的自同构群是一个非本原群,在此基础上进一步确定了完全图的完全扩容图的自同构群. 相似文献