强连通有向图的MSSS问题—Kneser图，区间图

发布时间：2020-08-21 12:00

【摘要】：对于强连通有向图D(V,X)而言,D的一个强连通支撑子图H,若对于Va ∈H,子图H-a都不具有强连通性,那么称H为极小强连通支撑子图.类比于连通图中的支撑树,容易看出一个强连通有向图D包含多个极小强连通支撑子图.我们称D的所有极小强连通支撑子图中包含弧最少的为最小强连通支撑子图DM.对于寻找强连通有向图D的最小强连通支撑子图DM的问题我们称其为MSSS问题.在许多情况下解决强连通有向图D的MSSS问题是非常有用的,但是这个问题很难实现,因为若D包含哈密尔顿圈,那么我们就必须寻找D的哈密尔顿圈.在本文中,我们进一步研究了两类重要的可以找到其最小强连通支撑子图的强连通有向图.本文第一章首先介绍了最小强连通支撑子图问题的研究背景,其次介绍了本文的基本定义和符号,最后简述了本文研究的核心问题,研究进展及本文的主要结果.本文第二章主要是确定了本文的主要研究方法.在第一节给出了可删弧的定义,这也是我们研究方法和算法所涉及的核心定义,第二节利用深度优先搜索算法确定可删弧集,第三节利用可删弧集内部的相关性定义一个由强连通有向图D(V,X)的可删弧集A(D)决定的无向图GA,并将我们寻找强连通有向图D(V,X)的最小强连通支撑子图DM问题转化为计算无向图GA的最大独立集问题.本文第三章与第四章,我们会结合第二章给出的算法解决这两个重要图类的MSSS问题,更精确的说,当可删弧集A(D)所构造的无向图GA是Kneser图或者区间图,我们就可以利用算法在多项式时间内计算出强连通图D的最小强连通支撑子图所包含弧的数量或者找出其最小强连通支撑子图.
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 崔秋月;刘娟;董畅畅;;超欧拉和双有向迹的强积有向图[J];四川师范大学学报(自然科学版);2018年04期

2 原军;刘爱霞;;局部内(外)半完全有向图可迹的充分条件[J];应用数学学报;2016年02期

3 韩婷婷;李瑞娟;;圆有向图中的泛弧[J];贵州师范大学学报(自然科学版);2017年01期

4 邓婕;池宏;许保光;;基于有向图相似的应急响应程序模块化问题研究[J];中国管理科学;2017年04期

5 崔秋月;刘娟;;关于超欧拉的幂有向图[J];廊坊师范学院学报(自然科学版);2017年03期

6 董畅畅;刘娟;;超欧拉路可合并有向图及半完全有向图（英文）[J];新疆师范大学学报(自然科学版);2017年03期

7 崔建;叶旺;;圆有向图的(1,2)步竞争图中存在哈密尔顿圈的条件[J];重庆工商大学学报(自然科学版);2017年06期

8 卢永红;;循环有向图的距离和与平均距离[J];山西师范大学学报(自然科学版);2014年01期

9 张新鸿;李瑞娟;李胜家;;圆有向图的(i,κ)步竞争图[J];应用数学学报;2013年06期

10 张新鸿;李瑞娟;李胜家;;关于强哈密尔顿连通有向图的一个反例[J];山西大学学报(自然科学版);2012年01期

相关会议论文 前10条

1 李刚;童

本文编号：2799350