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

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

对于强连通有向图D(V,X)而言，D的一个强连通支撑子图H，若对于(V)a∈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
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
强连通有向图; Kneser图; 区间图;

相似文献

中文文献
外文文献
专利

1. 无线传感器网络中基于有向图的强连通支配集的构造 [J] . 徐培培 ,吴振华 . 南昌航空大学学报（自然科学版） . 2016,第002期
2. 有向图的强连通分量及应用 [J] . 吴金全 . 软件 . 2014,第003期
3. 完全二部有向图的强连通可靠性 [J] . 吴颖娟 . 江汉大学学报（自然科学版） . 2012,第001期
4. 本原极小强连通有向图的重下scrambling指数 [J] . 尹作香 ,邵燕灵 . 河南师范大学学报：自然科学版 . 2012,第6期
5. n阶本原极小强连通有向图k-指数的最小值 [J] . 胡亚辉 ,曾艳辉 . 数学理论与应用 . 2011,第003期
6. 当m=n+1时的极小强连通图 [C] . 江卫新 ,赵衍才 . 山东省计算机学会2005年信息技术与信息化研讨会 . 2005
7. 强连通有向图的谱半径与最大度 [A] . 张绍唯 . 2020

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

目录

摘要

著录项

相似文献

相关主题

期刊订阅