共查询到20条相似文献,搜索用时 171 毫秒
1.
周永生 《兰州理工大学学报》1985,(4)
在可靠通讯网络的构造方面,F.Harary于1962年证明了“图Hm,n是m—连通的”的定理。此定理告诉我们,Hm,n是具有几个顶点,边数最少的m—连通图。 本文首先给出了连通正则图是m—连通的的充要条件,然后利用这一结果及循环图的性质,推广了“图Hm,n是m—连通的”这一定理,并构造出包含Hm,n在内的具有n个顶点、边数最少的一类m—连通图。最后利用同构的循环图构造出一类可靠通讯网络。 相似文献
2.
设α(n)是自同构群与n阶循环群C(n)同构的图的最小顶点数,该文构造出群为C(3r)的具有α(3r)个顶点的边数最少的图,并证明了这样的图是唯一的. 相似文献
3.
Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右. 相似文献
4.
图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G 中的一个两两不相邻的边子集称为图G 的一个匹配。图G 的一个最大匹配的边数称为图G 的匹配数。图G 中的一个与G 的每个团都有交的顶点子集称为G 的一个团横贯集,图G 中元素个数最少的团横贯集的顶点数称为G 的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。
相似文献
相似文献
5.
何建锋 《云南民族大学学报(自然科学版)》2007,16(3):216-218
给图G的每条边e都赋一个权w(e),所得的赋权图记为G(w).在G(w)中,顶点v的标号f(v)等于与顶点v相邻各边的权之和,当各顶点标号相异时,称G(w)是非正则的.G(w)的非正则和是在所有以图G为基础图的非正则图中,各顶点标号的和为最小时的值,记为∑(G).若非正则和∑(G)=nδ 2n,则称图G连续.利用图的权矩阵,讨论了图nK4m、nK5m、nK6m和nK7m的连续性. 相似文献
6.
设G是含有n个顶点和ε条边的图,G的Zeta函数可以表示为ZG(u)=(1-u2)n-ε/f(u),其中f(u)=det(I-uA (G)+u2(D (G)-I)),A(G)与D (G)分别表示G的邻接矩阵与度对角矩阵。分别利用正则图的TU子图的权重ω和二部图的顶点n和边数ε来表示相应的f′(-1)的值。 相似文献
7.
图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G中的一个两两不相邻的边子集称为图G的一个匹配。图G的一个最大匹配的边数称为图G的匹配数。图G中的一个与G的每个团都有交的顶点子集称为G的一个团横贯集,图G中元素个数最少的团横贯集的顶点数称为G的团横贯数。本文针对n阶连通无三角形的3一正则图G-(V(G),E(G)),首先给出了其割边数的一个上界(n—l0)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。 相似文献
8.
连通图的Balaban指标(也叫J指标)的定义是m1J(G)=m-n+2uv∑∈E(G)σG(u)σG(v)其中m,n分别是图G的边数和点数,σG(u)表示在G中从顶点u到其它各个顶点的距离之和.Balaban指标被广泛应用于各种QSAR和QSPR的研究.首先给出连通3-正则图的Balaban指标的一个上界.然后对KNOR M等人介绍的两类3-正则图,分别给出它们的Balaban指标计算公式和上界,改进了KNOR M等人的结果. 相似文献
9.
10.
《河南师范大学学报(自然科学版)》2016,(6):29-35
双圈图是指顶点数等于边数减1的连通图,Harary指数是指图中所有顶点对的距离倒数之和.基于此,主要研究了具有k个悬挂点且两个圈只有一个交点的n阶双圈图有极大Harary指数的图类. 相似文献
11.
陈文彬 《广州大学学报(自然科学版)》2014,(1)
证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约. 相似文献
12.
从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图. 相似文献
13.
有各种各样的方法去衡量不同网络的可靠性和容错性.一个连通图G的g-额外连通度Kg(g-额外边连通度λg)是顶点数最小的顶点集S(边数最少的边集S),使得G-S不连通,并且剩下的每个连通分支含有的顶点数至少是g+1.探究n-维折叠交叉超立方体FCQn的2-额外连通度和2-额外边连通度,证明得到如下结论:当n≥8时,κ2(... 相似文献
14.
15.
研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。 相似文献
16.
为纠错码问题提供理论基础,在运用同余、奇偶性方法的基础上,给出了用点边二种观点分析边标号的方法。使用这种方法,得到了一般序列图、正则序列图、Euler序列图、圈的粘接序列图和圈的并序列图的必要条件,证明了边数为2k,k是奇数的Euler图是非序列图类,讨论了m个n圈的粘接图中的非序列图类:分析偶圈的特征,构造了偶圈的具有同顶点集的序列母图并给出其序列标号表达式。这些结果在通讯、军事等领域有重要应用价值。 相似文献
17.
周后卿 《邵阳学院学报(自然科学版)》2008,5(3):7-9
设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为(2r-2),边为1/2nr(r-1)的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G.J.Davis,G.S.Domke等人的结论. 相似文献
18.
唐保祥 《西北师范大学学报(自然科学版)》2000,36(4):22-26
根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 . 相似文献
19.
《内蒙古师范大学学报(自然科学版)》2017,(3)
研究具有最大能量的直径为6的毛毛虫树的能量问题.给出毛毛虫树的定义,并介绍了直径为6的毛毛虫树;通过比较不同变换下毛毛虫树的能量大小,得到各悬挂边数目之间的关系;给出n取不同值时,有最大能量的直径为6的毛毛虫树的一些结论,解决了给定顶点数和边数的连通图中具有最大能量的图的问题. 相似文献
20.
张霞 《山东大学学报(理学版)》2005,40(3):5-10
给出图G和一个正整数r,令f‘r(G)为图G边染色的最大色数,使得每个顶点最多关联r种颜色,并且每个顶点关联的颜色中任两种颜色所染的边数相差最多为1.对所有的正整数n和r,给出了f‘r(Kn,n)的下界和上界;在r|n和r=2,3,n-1的情形,得到f‘r(Kn,n)的值。 相似文献