当前位置:主页 > 科技论文 > 数学论文 >

扭曲超立方体和平面图的结构研究

发布时间:2024-12-11 02:30
  随着数字通讯技术和计算机技术的快速发展,大量的信息在计算机网络中传输.计算机的编码方式和信号在信道上传输的可靠性、有效性、适应性、经济性等性能成为计算机网络研究中的重要课题.本论文研究与网络的可靠性和效率相关的特殊图类的结构.论文的第一部分研究了扭曲超立方体的容错直径和宽直径.容错直径和宽直径是衡量网络的可靠性、有效性、经济性等性能的两个参数.设l是一个正整数,且图G是l-连通的.图G的l-容错直径,记为dlf(G),是满足下列条件的最小整数dd:对于任意的X(?)V(G),若|X| ≤ l-1,则G-X的直径不超过d;图G的l-宽直径,记为dl(G),是满足下列条件的最小整数d:对于任意的顶点x,y ∈ V(G),G中包含l条内部点不交的且长度不超过d的路.在限定顶点数和顶点最大度的条件下,超立方体和扭曲超立方体的直径比较小且具有良好的扩展性.因此,超立方体和扭曲超立方体在网络设计中被广泛应用.本文引进随机扭曲超立方体(RQn)的概念,研究了三类特殊扭曲超立方体Zn,k、Hn以及RQn的容错直径和宽直径,得到以下结果:(1)对于任意的n-维扭曲超立方体Gn∈ Qn,有dnf(Gn)≤3...

【文章页数】:118 页

【学位级别】:博士

【部分图文】:

图2.1:运用配对模型的方法探索邻点??

图2.1:运用配对模型的方法探索邻点??

这里将会多次运用这个思想.例如,考虑生成的一个过程.首先幵始于24个顶??点,其中每一个顶点包含4个点.现在图还没有一条边,目标是探索对于图中任意一个??顶点u包含4个点a?:6,c,d的匹配(边)的生成情况(见图2.1).点a在1-型匹配中只能??匹配点e.因为一个点必须匹配相....


图2.2:情况1.顶点U和W分别在图的两边且是相邻的.??

图2.2:情况1.顶点U和W分别在图的两边且是相邻的.??

第二章扭曲超立方体的结构研究成后就结束了这条路的寻找.因此,增加一个常数3长度上,这个并不会产生一个线性的项.??点u和w分别在图么的两边且是相邻的.??且I;?e氐所以它们只能通过n-型匹配相邻?此时只需要寻找另外的71-1条路.令叫,..., ̄_1是顶队是顶点r在B中的邻点.....


图2.3:情况2.顶点u和t;分别在图(〇7,的两边,它们不相邻且没有公共

图2.3:情况2.顶点u和t;分别在图(〇7,的两边,它们不相邻且没有公共

上面一样首先在4这一边令=?{埤,…,wn—2,?<—丨}且X?=?{%??/?_;!},其次在这一??边,令[/?=?{l;〗,...?且X?=?{%叫-1},分别应用推论2.4.1即可?见图2.4.??情况4.顶点u和t;在图的同一边.??情况4.1?M和U是相邻的.??因为....


图2.4:情况3.顶点w和t;分别在图么的两边,且它们不相邻但有一个公共的邻点.??

图2.4:情况3.顶点w和t;分别在图么的两边,且它们不相邻但有一个公共的邻点.??

?那么以概率为1—〇(2-2")可以得到两两互相不交的集合??然后继续前面的方法来暴露n-型匹配(即由A到S的匹配),当??1?S?S?n?—?3时.有%到V/的边;[/?_2到V的边;以及到W的边.见图2.5.??I?""""""??图2.5:情况4.1?u和u是相邻的.??情....



本文编号:4016038

资料下载
论文发表

本文链接:https://www.wllwen.com/kejilunwen/yysx/4016038.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户f4995***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com