共查询到20条相似文献,搜索用时 937 毫秒
1.
图G的对偶带宽是指图G中相邻两点最小标号差的最大值。确定了一些特殊树的对偶带宽,主要结果如下:(1)如果树T有n个顶点,并且其最大度△(T)不小于[n/2],那么树T的对偶带宽等于n一△(T)的充要条件为T是双层星且其内星的中心为最大度顶点;(2)完全二叉树T2,k的对偶带宽等于2^k-1;(3)等高单毛虫树Pm,n的对偶带宽为[mn/2]。 相似文献
2.
讨论了点数和最大度均固定的一类树的谱半径, 分别给出了这类树的谱半径的上界和下界, 并分别 刻画了达到上下界的极图. 相似文献
3.
吕长青 《华东师范大学学报(自然科学版)》2015,2015(1):131-135
通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度. 相似文献
4.
陈娅红 《西南民族学院学报(自然科学版)》2009,35(2):241-243
令(n,△)是具有n个顶点,最大度为△的树的全体.1.△(n)是具有n个顶点且每个顶点的度是1或△的树的全体.对于任意λ≠0,本文分别在(n,△)和。1.△(n)中确定了具有最大的五一修改的Wjener指数的极值图. 相似文献
5.
申玉红 《云南民族大学学报(自然科学版)》2013,22(2):144-145
最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1. 相似文献
6.
求解最大度约束下最小生成树的新算法 总被引:1,自引:0,他引:1
马来焕 《江南大学学报(自然科学版)》2009,8(5):551-554
针对网络优化中度约束最小生成树问题的特征,融合破圈法的基本思想,提出了一种求解网络G关于指定节点的最大度约束下最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过去掉圈中权最大的边,最终构造出网络G关于指定节点的最大度约束下的最小生成树。算法证明和算例都表明了该算法的有效性。 相似文献
7.
文章主要讨论一类超图,使它具有边着色性质,即边色数等于最大度数△。通过对线性超树与其对偶超图、线图性质的分析,找出线性超树的边色数即,线性超树的边色数为q(H)=△。 相似文献
8.
具有k个最大次点树的叶子数目估计 总被引:2,自引:1,他引:1
黄承兴 《云南大学学报(自然科学版)》2001,23(2):91-94
对于任意一棵具有k个最大次点树,采用细分、同胚的方法,得到如下结论:任意一颗具有k个最大次点树都含有至少max│k△-2),0│+2个叶子;如果一棵树具有k个最大次点(其中△≥3)并且其叶子数目为k(△-2)+2,则这棵树在同胚意义下的次序列是(△,△,…,△,1,1,…,1k(△-2) 2,即具有k个最大次点且叶子数目为k(△-2)+2的树在同胚意义下的次序列是唯一的。 相似文献
9.
设△(T)和λ1(T)分别表示树T的最大度和谱半径,Tn表示有n个点的树且Tn^(△)=(T∈Tn|△(T)=△},文章根据树的谱半径给Tn^n-6(n≥18)中的树进行了排序并将结果扩大到第78棵树。 相似文献
10.
一个图称为是1-平面的,当且仅当它可以画在一个平面上,使其任何一条边最多交叉另外一条边.本文证明了最大度△≥15且不含三角形的1-平面图G是△-边可选择的和(△+1)-全可选择的. 相似文献
11.
度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。 相似文献
12.
郑永前 《同济大学学报(自然科学版)》1999,27(5):567-570
介绍一种建立实体模型的方法,用由组合立体的各子立体的控制点所构造的几何树来描述实体,并把子立体间的几何约束问题转化为结点之间的关系,为建立和修改实体模型提供了方便。 相似文献
13.
王维凡 《辽宁大学学报(自然科学版)》1992,19(1):16-21
本文证明了对每一个△(G)≥3的外平面图G,有X~c(G)≤△(G)+3,其中X~c(G)为G的完备色数,△(G)为G的顶点最大度。 相似文献
14.
不含3-圈平面图的线性染色 总被引:1,自引:0,他引:1
王侃 《浙江师范大学学报(自然科学版)》2011,34(2)
运用Discharging方法,研究了平面图的线性染色问题,证明了一个没有3-圈的平面图G的线性色数lc(G)≤[3△(G)/2]+2,其中△(G)表示G的最大度. 相似文献
15.
对于任意整数k≥2,证明了最大度至少为5k-1且最大平均度小于3-3/△(G)-k+2的图G的k-森林染色数为[△(G)/k]+1. 相似文献
16.
最大度不小于7的图的星边色数的一个上界 总被引:4,自引:0,他引:4
定义了星边染色和星边色数X's(C),证明了若图G的最大度△≥7,则X's(G)≤[16(△-1)3/2].此结果包含了若图G是最大度△≥12的线图,则Xs(G)≤[16(△-1)3/2]. 相似文献
17.
18.
19.
柳柏濂 《华南师范大学学报(自然科学版)》1988,(1):1
若简单连通图G=(V,E)满足G=T_1UT_2,E(T_1)∩E(T_2)=φ,其中T_1和T_2是G的生成树,则G称为简单2—补树图.本文研究了简单2—补树图的若干性质(10个定理),其中包括:2—补树图G顶点度的性质,κ(G),λ(G),δ(G),△(G),2—补树图的构造性质和判定条件. 相似文献
20.
吴建良 《山东大学学报(理学版)》2005,40(3):11-14
设G是一个连通图且满足|E|≤|V| [3△/2]-4,则它的线性荫度la(G)=[△/2],同时得到了一个与树相关的结果。 相似文献