共查询到20条相似文献,搜索用时 125 毫秒
1.
提出并证明了λ=1的平衡关联区组设计(DBB设计)对应的超图具有最佳连通性,使最佳连通超图的构造又具有了一大类成果。该结构的超图(多总线或通讯网)成本低,端口数少,且直径小,容错性高,在通讯网的拓扑设计中有较好的应用前景。 相似文献
2.
程绩 《西华师范大学学报(哲学社会科学版)》2007,28(3):242-245
随着有向超图理论在实际问题中的深入应用,其平面性研究也更加具有意义.本文回顾有向超图的一般理论,给出了有向超图结构图的概念,并在此基础上给出有向超图的可平面性算法.由于有向超图的结构图是简单有向图,故有向超图的可平面性算法建立在对一般图的可平面性判断上,该算法是多项式时间算法,是有效算法. 相似文献
3.
叶淼林 《安庆师范学院学报(自然科学版)》1999,5(3):3-6
本文给出了超图的点连通度、边连通度的概念。定义了Euler超图、i-型(i=1,2,3)Hamilton超图及超图的Euler问题和Hamilton问题。证明了超图的Euler问题,i-型(i=1,2,3)Hamilton问题均是NP-完备问题,类似于图的结果,分别给出了超图是Euler超图及Hamitlon超图的一个必要条件 相似文献
4.
混合超图是含有两种超边的超图,一种称为D-超边,一种称为C-超边,它们的区别主要体现在着色要求上.在任一着色中,要求每一D-超边至少有两个点着不同的颜色,每一C-超边至少有两个点着相同的颜色.只含D-超边的超图称为D-超图,只含C-超边的超图称为C-超图.主要讨论了C-超图的完美性问题,给出了完美C-超图的一个充分条件. 相似文献
5.
6.
无向超图的计数级数 总被引:1,自引:1,他引:0
黄汝激 《北京科技大学学报》1999,21(5):507-510
应用置换群理论,引入了超边群,超图群和超图同构的概念,导出了超边群及其循环指标的一般表达式,导出了无向无标号标图和标号超图的计数级数,解决了无向超图的同构和计数问题。 相似文献
7.
程绩 《达县师范高等专科学校学报》2007,17(5):13-15
随着超图理论在实际问题中的深入应用,其平面性研究也更加具有意义.回顾了超图的一般理论,给出了超图的二部图概念,并在此基础上给出了超图的可平面性算法.该算法是多项式时间算法,是有效算法. 相似文献
8.
杨春德 《重庆邮电学院学报(自然科学版)》1995,7(2):66-70
文献(1)讨论了伪超图开关类运算的基本性质。本文在此基础上,讨论τ(m)伪超图开关类的类容量极值问题和τ(m)伪超图开关类中k阶为超图容量极值问题,并给出相应的精确容量或极值界限。 相似文献
9.
讨论了k-一致超图的Laplacian谱的问题,分别得到了k-一致超图的Laplacian谱的上界和下界,并由此推得k-一致超图的Laplacian矩阵是正定矩阵。 相似文献
10.
一致超图与其补超图各种独立数间的关系 总被引:1,自引:0,他引:1
主要讨论了超图中的若干参数:独立数、强独立数、边独立数和全独立数,利用这些参数的定义和性质,研究了一致超图与其补超图中这些参数间的关系及其上界。 相似文献
11.
张新军 《莆田高等专科学校学报》2012,(2):7-10,52
将一般图的[r,s,t]-着色推广到超图上得到超图的[r,s,t]-着色的定义及超图[r,s,t]-着色的一些性质和定理,并讨论了超图的[r,s,t]-色数的上下界。 相似文献
12.
从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法. 相似文献
13.
王志雄 《华侨大学学报(自然科学版)》1996,17(2):123-126
研究混合超图的各种星染色方式及其性质,比较它们之间的关系以及它们与一般超图的染色,星染色的关系,并给出了若干类染色图。 相似文献
14.
基于一般图中图熵的定义,定义了超图基于拉普拉斯度的图熵.将简单图的图熵的一些结论推广到k-均匀超图.利用一种移边操作,分别确定了在k-均匀超树、单圈k-均匀超图、双圈k-均匀超图和k-均匀化学超树中基于拉普拉斯度的图熵最大值和最小值,并确定了相应的极值图. 相似文献
15.
16.
讨论了r一致导出匹配可扩张超图及其性质,并找到了1种寻找边数较少的导出匹配可扩张超图的方法。 相似文献
17.
19.
引入植树超图的概念,利用植树超图给出了一个超图是无圈超图的充分必要条件.建立了无圈超图与树的对应关系,表明信息科学家提出的无圈超图与数学家建立的无圈图有着密切的联系,所得结果进一步刻画了无圈超图概念中"无圈"的本质. 相似文献
20.
著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree:edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。 相似文献