共查询到20条相似文献，搜索用时 15 毫秒
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)
设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。 相似文献
11.
12.
许振宇 《山东科技大学学报(自然科学版)》2004,23(3):95-97
设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。 相似文献
13.
王维凡 《辽宁大学学报(自然科学版)》1992,19(1):16-21
本文证明了对每一个△(G)≥3的外平面图G,有X~c(G)≤△(G)+3,其中X~c(G)为G的完备色数,△(G)为G的顶点最大度。 相似文献
14.
15.
战新刚 《山东大学学报(理学版)》2004,39(1):5-8
图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图G的k-有界染色数χk(G)是指对图G进行k-有界染色所用的最少颜色数．讨论一类外平面图的k-有界染色，给出能在多项式时间内确定其k-有界染色数的一些充分条件． 相似文献
16.
17.
研究了射影平面上2 连通图的圈基结构,并给出了在嵌入的边宽度ew(G)≥5时外可平面图的最小圈基结构,证明了最小圈基与最短不可收缩圈之间的一一对应性. 相似文献
18.
设Ｇ是无割点平面图，ｘｅｆｌ（Ｇ）为Ｇ的边面Ｌｉｓｔ选择数。本文证明了若Ｇ为最大度Δ（Ｇ）≥６的无割点外平面图，则ｘｅｆｌ（Ｇ）＝Δ（Ｇ）。 相似文献
19.
一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a＇（G）是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a＇（G）≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a＇（G）=4的充分条件,拓展了该领域的相关结果. 相似文献
20.