检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

随机图的广义3-连通度

数学学报（中文版） 2014年第2期57卷 321-330页

作者：顾冉李学良史永堂南开大学组合数学中心天津300071

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子... 详细信息

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.

关键词：连通度内部不交树广义连通度随机图阈值函数

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

折叠超立方体的广义3-连通度

山东大学学报（理学版） 2022年第11期57卷 42-49页

作者：王军震张淑敏葛慧芬青海师范大学数学与统计学院青海西宁810008 高原科学与可持续发展研究院青海西宁810008 青海师范大学计算机学院青海西宁810008

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V′,E′),使得S⊆V′。如果连接S的两棵斯坦纳树T和T′,满足E(T)∩E(T′)=Φ且V(T)∩V(T′)=S,则称T和T′是内部不交的。定义κ(S)为图G中内部不相交S-斯坦... 详细信息

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V′,E′),使得S⊆V′。如果连接S的两棵斯坦纳树T和T′,满足E(T)∩E(T′)=Φ且V(T)∩V(T′)=S,则称T和T′是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_(k)(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ_(2)(G)=κ(G)。证明了κ_(3)(FQ_(n))=n,其中FQ_(n)是n-维折叠超立方体。

关键词：广义连通度斯坦纳树折叠超立方体

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Cayley图的广义3-连通度

Cayley图的广义3-连通度

作者：张燕新疆大学

学位级别：硕士

计算机网络常用连通图表示,其服务器用点表示,服务器之间的连接用边表示.所以,网络的性能可用图的参数来衡量.虽然经典连通度是衡量网络容错性的重要参数之一,但它并不能精确地衡量大型网络的容错性.为了完善经典连通度,很多学者对经典... 详细信息

计算机网络常用连通图表示,其服务器用点表示,服务器之间的连接用边表示.所以,网络的性能可用图的参数来衡量.虽然经典连通度是衡量网络容错性的重要参数之一,但它并不能精确地衡量大型网络的容错性.为了完善经典连通度,很多学者对经典连通度进行了推广.本文就着重研究其中一个推广—广义k-连通度.设G是一个阶为n的连通图,k是整数,且2≤k≤n.设S(?)V(G),T是G中的一棵树,若S(?)V(T),则称树T是G的一棵S-树.令{T1,T2,…,Tr}是图G中S-树的集合,若E(Ti)∩E(Ti)=(?),且V(Ti)∩V(Tj)= 其中1≤i≠j≤r,则称其是内部不交的.令κG(S)表示图G中内部不交S-树的最大数目.用κk(G)表示图G的广义k-连通度,其中κk(G)=min{κG(S)|S(?)V(G),且|S|=k}.显然,G的广义2-连通度κ2(G)恰好是κ(G).近几年,很多学者非常注重广义连通度的研究,并且证明了确定一般图G是否存在k棵内部不交的S-树是NP-完全问题.本文分两章.除第一章引言之外,第二章研究了由完全图生成的Cayley图CTn,由轮图生成的Cayley图WGn,和由三角塔生成的Cayley图TTn这三类图,并确定了它们的广义3-连通度,其结果如下:κ3(CT)=n(n-12-1,其中n≥ 3;κ3(WGn)=2n-3,其中n ≥ 4;κ3(TTn)=2n-4,其中n≥3.

关键词： Cayley图广义连通度路树

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

完全对换图的广义3-连通度（英文）

曲阜师范大学学报（自然科学版） 2019年第1期45卷 1-6页

作者：张燕阿依古丽.马木提新疆大学数学与系统科学学院新疆维吾尔自治区乌鲁木齐市830046

令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树.

关键词：完全对换图广义连通度内部不交的S-树邻点

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

网络图的两个可靠性参数

网络图的两个可靠性参数

作者：周宇康北京化工大学

学位级别：硕士

图的条件连通度是除了点连通度之外的另外一种探索网络结构的方法,在研究网络图容错率中有很多应用。对一个连通图G =(V,E),点集F(?)V记作G的Rκ点割如果G-F不连通且V-F中的每一个点在G-F中至少有k个邻点。我们用κk(G)表示图G所有的R... 详细信息

图的条件连通度是除了点连通度之外的另外一种探索网络结构的方法,在研究网络图容错率中有很多应用。对一个连通图G =(V,E),点集F(?)V记作G的Rκ点割如果G-F不连通且V-F中的每一个点在G-F中至少有k个邻点。我们用κk(G)表示图G所有的Rκ点割中元素最少的集合的大小。凯莱图在互联网络中有很好的属性,如点对称性、边对称性、层次结构可分解、高容错度等,因此凯莱图研究在设计和分析网络方面有很多的应用。令Sym(n)是基于{1,2,...,n 的对称群,T是Sym(n)中的一个置换集,图G(T)由点集{1,2,...,n}和边集{ij:(ij)(?)T}构成。如果G(T)是轮图,那么我们简单地将凯莱图Cay(Sym(n),T)记作WGn。图的广义连通度是图的连通度的另一种自然推广,常被用作衡量网络G的稳定性。给定图G =(V,E)和顶点数大于等于2的顶点集合S(?)V,若i≠j且1≤i,j≤r,则图G中满足V(Ti)(?)V(Tj)= S的边不交的树T1,T2,...,Tr叫做S斯坦纳树,我们用kG(S)表示图G中S斯坦纳树数量的极大值。对于满足2≤k≤n的正整数kk,图G的广义kk连通度κK((G)定义为κk(G)= min{κG(S)|S(?),|S|=k},也就是说,κk(G)是κG(S)在取遍G中所有的k元顶点子集S后的最小值。本文,我们探索了由轮图所生成的凯莱图(记作WGn)的κ1(WGn)和κ2(WGn)值;探索了凯莱图冒泡星图(记作BSn)的广义3连通度κ3(BSn)值,并分别证明了在n≥5时κ1(WGn)=4n-6,κ2(WGn)=8n-18,在n ≥ 3时K3(BSn)= 2n-4。

关键词：凯莱图轮图容错率条件连通度广义连通度冒泡星图斯坦纳树

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

某些网络的树和圈相关问题分析

某些网络的树和圈相关问题分析

作者：魏超北京交通大学

学位级别：硕士

近年来,基于连通度的可靠性分析受到了网络研究者的广泛关注.虽然传统的连通度可以用来衡量两个节点之间的连通强度,但这种方法在评估网络的多个节点集合之间的连通强度时是不够的.广义连通度作为连通度的推广能够有效解决上述问题.令S(... 详细信息

近年来,基于连通度的可靠性分析受到了网络研究者的广泛关注.虽然传统的连通度可以用来衡量两个节点之间的连通强度,但这种方法在评估网络的多个节点集合之间的连通强度时是不够的.广义连通度作为连通度的推广能够有效解决上述问题.令S(?)V(G),κ(S)表示图G中内部不交的S-树T,T,···,T的最大数目r.这里内部不交的S-树是指满足V(T∩T)=S,E(T∩T)=(?)的树,其中i,j∈{1,2,···,r}且i j.定义κ(G)=min{κ(S)|S(?)V(G),|S|=k}是图G的广义k-连通度,其中k≥2.此外,在网络的设计和分析中,一个重要的问题就是它的图嵌入能力.圈是并行和分布式计算的最基本结构之一.如何将多个圈嵌入到网络中是一项重要研究内容,其中,图G的k-不交圈覆盖是指在图G中嵌入k个不交圈且恰好覆盖G的全部顶点.本论文分别研究了基于树结构的广义连通度问题和基于圈结构的两个不交圈覆盖问题.首先,结合数学归纳法和对故障点的随机分布进行分类讨论,分别确定了n-维平衡超立方体BH和n-维增广立方体AQ的广义3-连通度.其次,证明了n-维平衡超立方体BH的两个不交的偶泛圈覆盖的存在性.论文结构如下:第一章是绪论,主要介绍了本文用到的基本概念,广义连通度和两个不交的偶泛圈覆盖的背景知识,简要给出了本文研究的两类网络的定义及主要工作.第二章首先给出了广义连通度和n-维平衡超立方体BH的相关结论.然后基于BH的结构特点和性质,证明了BH的广义3-连通度为2n-1,其中n≥1.第三章首先给出了n-维增广立方体AQ的相关性质,其次证明n=3,4,5时,AQ的广义3-连通度分别为4,5,8,最后证明n≥6时,AQ的广义3-连通度为2n-2.第四章基于BH的结构性质,证明了BH的两个不交的[4,2]-偶泛圈覆盖的存在性.该结论推广了BH的哈密尔顿性以及偶泛圈性在圈长满足4≤≤2-4下的结果.第五章中对本文进行了总结,并给出了进一步的研究方向.

关键词：平衡超立方体增广立方体广义连通度两个不交的偶泛圈覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

完全二部图的强子图连通度

应用数学进展 2022年第6期11卷 3646-3650页

作者：程睿绍兴文理学院数理信息学院浙江绍兴

无向图G的广义k-连通度是在1985年由Hager引入的定义,这个概念后来又被人们推广到有向图中并提出了强子图k-连通度的定义。近年来,强子图k-连通度的研究在有向图上取得很多重要结果。在本文中,我们研究并给出了完全二部有向图上的强子... 详细信息

无向图G的广义k-连通度是在1985年由Hager引入的定义,这个概念后来又被人们推广到有向图中并提出了强子图k-连通度的定义。近年来,强子图k-连通度的研究在有向图上取得很多重要结果。在本文中,我们研究并给出了完全二部有向图上的强子图k-连通度的若干结果。

关键词：广义连通度强子图k-连通度完全二部图