共查询到20条相似文献,搜索用时 15 毫秒
1.
G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E. 相似文献
2.
设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度. 相似文献
3.
讨论了树的代数连通度.利用移接变形给出树的代数连通度的一种变化关系,同时给出了两类树的代数连通度与直径的关系. 相似文献
4.
关于图的代数连通度的注记 总被引:3,自引:1,他引:3
n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 . 相似文献
5.
【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先,利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图;其次,利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的,从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图,克服了以往利用图的最小度,最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征,但无法得到此类图的连通度的上界这一弊端。 相似文献
6.
对任一个n阶单图G,用a(G)表示G的代数连通度,Gc为G的补图.通过代数连通度与Laplacian谱半径的关系,给出了几类图的Nordhaus-Gaddum的代数连通度的和的界. 相似文献
7.
给定最大度的树的代数连通度 总被引:1,自引:0,他引:1
研究给定最大度的树在移接变形下的代数连通度的变化.这些结果可以用来刻画给定最大度和顶点个数的树中具有最小代数连通度的极图,并且给出了该极图的代数连通度的一个下界. 相似文献
8.
9.
对任一个n阶单图G,用a(G)表示G的代数连通度,GC表示它的补图.针对双圈图,即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(GC),当且仅当G≌G1时等式成立. 相似文献
10.
文章通过研究双星图的代数连通度的极限点 ,给出树的代数连通度的极限点的分布范围 :[0,(3- 5)/2] ,以及分布情况的一个结论 : ε>0 ,至少存在一个树类 ,其代数连通度的极限为r>0 ,且r<ε。 相似文献
11.
12.
13.
对任一个凡阶单图G,用0(G)表示G的代数连通度,Gc表示它的补图.针对双圈图.即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(G^C),当且仅当3G兰G1时等式成立. 相似文献
14.
对任一个n阶简单图G,用a(G)表示G的代数连通度.在已有文献研究的基础上,通过分类研究和个别图具体研究,证明了对任一含有两个基本圈的简单图G,有1≤a(G)+a(Gc). 相似文献
15.
有向图和二部有向图连通度的下界已由Hellwing和Volkmann给出.定向图是没有二圈的有向图.文章研究了这类特殊的有向图-定向图,同时通过改进Hellwing等人的证明方法,得到了定向图和二部定向图连通度的更好的下界. 相似文献
16.
17.
图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果,例如,量化一个图或网络的脆弱程度,便始于图的连通性研究。因此,我们总是希望图能具有较高的连通度。对n个顶点的图G来说,当连通度不小于顶点数n的一半时,我们认为这个图有较高的连通度。本文试图给出图具有较高连通度的一个充分必要条件。我们指出,对一个给定的正整数k且k≤2n,有κ(G)≥n-k成立当且仅当对顶点集V(G)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=k,G[S,T]=G[S∪T]-E(G[S])-E(G[T])。 相似文献
18.
张梅琼 《福建师范大学学报(自然科学版)》2021,(3):20-28
软件定义网络(software defined network,SDN)在快速发展中面临许多新挑战,其中能耗问题尤为突出.学者们提出了许多节能方案,但目前已有的方案存在依赖传统网络背景,需要实时流量数据,不易部署,连通稳定性兼顾不全等问题.因此,提出一种基于代数连通度的软件定义网络节能算法(energy saving ... 相似文献
19.
对于连通图G,矩阵Q(G)=D(G) A(G)称为图G的拟拉普拉斯矩阵,其中D(G)为图的度对角矩阵,A(G)为图的邻接矩阵.本文利用矩阵的一些性质,推导出连通图的拟拉普拉斯谱半径的一个上界.并将该上界与已有的一些结论结合具体图例作了优越性比较. 相似文献
20.
用k1>0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}. 相似文献