论文摘要
设G=(V,E)是简单图,子集F(?)V,若子集VF的导出子图不含圈,则称子集F是图G的反馈点集.其中包含顶点数最少的子集F称为图G的最小反馈点集,其顶点数称为图G的反馈数,用f(G)表示.反馈数是互联网络拓扑结构图的一个重要参数,在诸多领域内有着广泛的应用.例如,估计并行处理器的性能、光纤网络中波长转换器的安装问题、网络传输过程中避免广播风暴问题以及计算机操作系统死锁避免问题等.由于计算一般图的反馈数问题已被证实是NP困难的,目前的研究主要集中在对特殊图类反馈数的算法研究或反馈数的上下界估计上,本文主要目的是寻求其反馈数的精确值.蜂巢网格是1997年Stojmenovic首次提出的.蜂巢网格的直径和节点(顶点)度数均优于其它网络,具有可观的应用前景.本文主要探讨平面蜂巢网格、六角纳米管和环面蜂巢网格反馈数的精确值问题,利用递归构造法得到以下主要结果:1、平面蜂巢网格HMn、ZZ(m,n)和C(m,m,n,)的反馈数分别为:(1)f(HMn)=9/2n2-15/2n+4;(2)f(ZZ(m,n))=[1/2mn=];(3)f(C(m,m,n))=mn-[n/2].2、六角纳米管N(m,n)和N(m,m,n,)的反馈数分别为:(1)f(N(m,n))=n(m+1)/2;(2)f(N(m,m,n))=mn.3、环面蜂巢网格HTn的反馈数为f(HTn)=9/2n2-9/2n+2.
论文目录
文章来源
类型: 硕士论文
作者: 苏雪丽
导师: 任海珍
关键词: 蜂巢网格,反馈点集,反馈数,无圈子图
来源: 青海师范大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 青海师范大学
分类号: O157.5
DOI: 10.27778/d.cnki.gqhzy.2019.000359
总页数: 58
文件大小: 2032K
下载量: 13
相关论文文献
- [1].无限网格图的邻和可区别边染色[J]. 宁夏师范学院学报 2018(07)
- [2].在网格图中比较角的大小[J]. 数理天地(初中版) 2019(06)
- [3].基于自适应阈值的网格图像行分割算法[J]. 计算机与网络 2012(23)
- [4].状态网格图的LDPC码在OFDM系统中的应用[J]. 电视技术 2010(12)
- [5].基于超网格的重叠网格守恒插值方法[J]. 航空学报 2018(03)
- [6].基于网格图像自动检测的镜头畸变校正[J]. 电视技术 2015(17)
- [7].基于状态网格图的差分跳频G函数构造方法研究[J]. 电子科技大学学报 2011(04)
- [8].跳跃的蓝[J]. 父母必读 2019(07)
- [9].应用Super Map的城市部件和万米网格图制作研究[J]. 科技创新导报 2010(10)
- [10].以党建品牌开拓创新之路[J]. 理论学习 2008(06)
- [11].一道网格作图题的解法探究[J]. 中学生数学 2019(02)
- [12].春[J]. 人民公安 2019(06)
- [13].埃尔莫尔的L形拼装格[J]. 初中生学习(低) 2011(03)
- [14].隐藏的秩序——网格在书籍设计中的运用[J]. 南京艺术学院学报(美术与设计) 2018(03)
- [15].TD-SCDMA系统中维特比译码的规律研究及仿真性能分析[J]. 电子测试 2008(07)
- [16].审题草率易出错 概念不清常丢分——2010年泰州市中考数学试卷阅卷心得之一[J]. 初中生世界 2011(Z3)
- [17].网格图的多重2-分离L(2,1)-标号[J]. 科学技术与工程 2011(23)
- [18].自由边界条件下的两类网格图的ABC指标[J]. 廊坊师范学院学报(自然科学版) 2015(05)
- [19].应用SuperMap的宁波市部件和万米网格图制作研究[J]. 科技资讯 2010(05)
- [20].一种利用图进行图像分割的高效方法[J]. 山东师范大学学报(自然科学版) 2008(02)
- [21].交通事故车辆变形与碰撞前车速关系定量分析[J]. 汽车与安全 2009(01)
- [22].利用白板网格图培养学生空间想象力[J]. 中国信息技术教育 2008(07)
- [23].三维网格作图实验中的教学设计探讨[J]. 实验科学与技术 2011(S1)
- [24].基于Matlab编程的扫描数据处理技术[J]. 科技信息 2010(11)
- [25].可重用零件特征的快速设计技术[J]. 中国机械工程 2018(23)
- [26].基于维特比算法的卷积码译码器设计[J]. 舰船电子工程 2009(05)
- [27].基于FPGA的卷积码Viterbi译码器实现方法[J]. 科学技术与工程 2013(18)
- [28].建筑图形的语言定义及分析理解[J]. 微型机与应用 2009(21)
- [29].何时需要分类?[J]. 初中数学教与学 2010(01)
- [30].有限元法的后置处理[J]. 考试周刊 2013(86)