论文摘要
近五十年来,随着计算机科学和互联网技术的发展,图论得到了广泛的重视.各种形式的覆盖问题成为图论领域重要的研究方向.覆盖问题在VLSI设计（超大规模集成电路设计）、程序测试、网络问题、环协议、代码优化等方面有着广泛应用.本文主要研究图的路覆盖问题.给定一个图G=（V,E）和图G中路的集合p={P1,P2,…,Pr},定义Pi=（Vi,Ei）,1≤i≤r,若路集合p满足：（1）Vi∩Vj=（?）,i≠j；（2）Uir=1 Vi=V,则称路集合P是图G的一个路覆盖.最小路覆盖的基数称为图G的最小路覆盖数,记为c（G）.路覆盖问题就是寻找图G中有c（G）条路的路覆盖.在本文第一部分里,我们给出了顶点数大于1的树T路覆盖数的下界p-eh-1,其中p表示叶子数,eh表示连接两个度大于2的顶点的边数.第二部分,我们得到了块图G与块-割点-树（block-cutpoint-tree） TG的最小路覆盖数之间的关系,从而给出了一类终端块数为b的块图的最小路覆盖数是b-1,其中终端块是割点数等于1的块.此外,对于一些特殊树状图,我们得到了其最小路覆盖数的精确值.最后,我们把关于树状图路覆盖数的结果应用到图的L（2,1）-标号问题和Hamiltonian completion问题上.得到了一些图的L（2,1）-标号数入（G）、洞指标ρ（G）和Hamiltonian completion问题的hc（G）的精确值.
论文目录
相关论文文献
- [1].中考中的覆盖问题[J]. 中学生数学 2009(22)
- [2].无线网络系统覆盖问题分析与优化研究[J]. 科技与创新 2014(15)
- [3].应用Femtocell快速解决室内3G信号弱覆盖问题[J]. 中国新通信 2013(04)
- [4].最大覆盖问题研究[J]. 科技传播 2011(22)
- [5].覆盖问题解决技巧的深入探讨[J]. 软件导刊 2010(09)
- [6].有关几何图形的覆盖问题[J]. 初中生世界 2008(36)
- [7].WCDMA网覆盖问题引起掉话实例分析[J]. 广东通信技术 2008(08)
- [8].最小基数箱子覆盖问题[J]. 河南教育学院学报(自然科学版) 2009(04)
- [9].LTE覆盖问题及对策探讨[J]. 信息与电脑(理论版) 2014(12)
- [10].一种基于大数据的弱覆盖问题识别与优化系统[J]. 信息通信 2018(07)
- [11].LTE室分方案及建设策略[J]. 通讯世界 2017(08)
- [12].最小费用箱子覆盖问题及其算法[J]. 湖南大学学报(自然科学版) 2008(02)
- [13].LTE系统深度覆盖问题分析及解决方案[J]. 无线互联科技 2019(22)
- [14].深度覆盖问题精准定位及解决方案的探讨[J]. 信息技术与信息化 2019(05)
- [15].一种新型4G弱覆盖问题规划分析方法[J]. 科技与创新 2017(06)
- [16].最大弧覆盖问题的一种邻域搜索算法[J]. 计算机仿真 2014(10)
- [17].基于服务质量的多目标逐渐覆盖问题[J]. 公路交通科技 2013(10)
- [18].LTE-R容量和覆盖问题[J]. 中国新通信 2012(24)
- [19].WCDMA网络优化中覆盖问题研究分析[J]. 浙江水利水电专科学校学报 2010(02)
- [20].无线传感器网络路径覆盖问题研究[J]. 电子与信息学报 2010(10)
- [21].关于正方体和长方体填充覆盖问题的注记[J]. 南开大学学报(自然科学版) 2015(01)
- [22].遗传算法在航班覆盖问题中的应用研究[J]. 中国民航大学学报 2008(06)
- [23].基于MDT数据的地下场景覆盖问题识别系统设计[J]. 电信工程技术与标准化 2020(06)
- [24].LTE MR弱覆盖问题的原因分析及处理[J]. 信息通信 2017(08)
- [25].最小权点覆盖问题的一个近似算法[J]. 数学的实践与认识 2015(12)
- [26].超平面覆盖问题的参数化改进算法[J]. 计算机研究与发展 2012(04)
- [27].GSM-R系统无线场强过覆盖问题分析[J]. 上海铁道科技 2016(01)
- [28].CDMA到LTE的覆盖问题及其演进方案浅析[J]. 移动通信 2013(Z1)
- [29].基于LIB的有色箱覆盖问题[J]. 计算机工程与设计 2008(09)
- [30].LTE网络弱覆盖问题分析及优化[J]. 科技创新与应用 2019(17)