共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
在ew(G)≥5的条件下。研究在平面和射影平面上2-连通的外可平面图的圈基结构,给出在这两种平面上嵌入的最小圈基,结果表明,平面上的最小圈基仅与面圈有关,射影平面上的最小圈基不仅与面圈有关,还与其不可收缩圈有着一一对应性。 相似文献
3.
周杰 《东北师大学报(自然科学版)》2002,34(2):16-21
给出了临界极大外平面图以及最大度临界极大外平面图的定义,并讨论了它们的性质,为研究极大外平面图的四染色提供了一种新方法。 相似文献
4.
图的同构的判定是图论研究中的重要课题之一,非同构的极大外平面图的计数问题尚未解决.提出一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵,证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图被不重不漏地构造出来,同时得到其总个数,解决了有关极大外平面图同构与计数问题. 相似文献
5.
给出并证明了外平面图的两个结构性质:(1)△≥5时,存在一个最小面,至多关联于一个△度点;(2)△=4且每个最小面均关联两个4度点时.存在闭内部面。作为性质的应用,更简捷的证明了非奇圈的外平面图为第一类图。 相似文献
6.
研究环面上2-连通外可平面图G在嵌入∏的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)>m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为∏的除Hamilton圈外的面迹数,l1,…,lf为∏的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应. 相似文献
7.
8.
研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a’(G)≤Δ(G)+3. 相似文献
9.
给定一个无向连通图G,圈包装问题就是求G的边不相交圈的最大数目.此问题在一般图下是APX困难问题,在平面图下是NP困难问题.主要证明了在几类特殊的平面图下多项式时间可得到最优解.主要考虑外平面图,系列平行图和平面欧拉图这三类特殊的平面图. 相似文献
10.
吴建良 《山东科技大学学报(自然科学版)》1996,(2)
设V(G)、E(G)和F(G)分别为平面图G的点集、边集和面集。G的完备色数Xc(G)是使得V(G)∪E(G)∪F(G)中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了:对无割点的外平面图G,有Xc(G)≤max{7,△(G)+1},其中△(G)为G的最大度数。 相似文献
11.
单伟 《济南大学学报(自然科学版)》2009,23(3):302-305
阐述了几乎外平面图的概念与特点,证明两类特殊的几乎外平面图的双约束边色数恒满足max{Δ(G),FM(G)}≤χe/vf(G)≤max{Δ(G)+1,FM(G)+1},其中Δ(G)、FM(G)分别为图G的最大度和最大面度. 相似文献
12.
许振宇 《山东科技大学学报(自然科学版)》2004,23(3):95-97
设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立,且它们的色数均不超过最大度加1。 相似文献
13.
14.
田双亮 《西北民族学院学报》2005,26(2):1-3
通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图. 相似文献
15.
16.
几种特殊图形的分数色数研究 总被引:1,自引:0,他引:1
图的着色问题是图论中的一个重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文研究了一些特殊图形的分数色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明. 相似文献
17.
18.
19.
连广昌 《南京邮电大学学报(自然科学版)》1995,(2)
证明了图的逻辑积的色数公式x(G1∧G2∧…∧Gn)≤min{x(G1),x(G2),…,x(Gn)},边色数有并作如下猜想:x(G1∧G2∧…∧Gn)=min{x(G1),x(G2),…,x(Gn)}. 相似文献
20.
几类冠图的邻强边色数 总被引:7,自引:0,他引:7
图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想:对任意连通图GG,{y}≥3且G≠C5有△≤X’ax(G)≤△+2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了:△≤X’as(G)≤△+1,且X’as(G)≤△+1当且仅当G[V△]≠Ф。 相似文献