有向无环图的stanly问题研究

发布时间：2017-10-12 19:33

  本文关键词：有向无环图的stanly问题研究

  更多相关文章： 有向无环图 区间图 面格 闭包矩阵 关联矩阵

【摘要】：有向图无环图是一种有着非常重要应用价值的图,它可以对许多实际问题进行建模。本文主要研究有向无环图的一些性质,主要是研究有向无环图的传递闭包和传递归约的相似性问题,也即偏序集的关联矩阵和覆盖矩阵在什么情况下是相似的。这个问题最早由Stanly提出,被称作Stanly’s problem。我们对Stanly’s problem作了较为深入的研究,建立了由传递归约矩阵确定传递闭包矩阵和由传递闭包矩阵确定传递归约矩阵的代数公式。这为计算机由其中一个矩阵计算另一个矩阵带来很大便利;具体的,我们对下面三种情况给出了肯定的回答:有向区间图、邻接矩阵是阶梯形矩阵的有向无环图、三维多面体的面格。最后我们利用计算机进行图的数值模拟。并给出了反例的一种构造办法。
【关键词】：有向无环图 区间图 面格 闭包矩阵 关联矩阵
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-7
• 1 概论7-12
• 1.1 绪论7-8
• 1.2 预备知识8-11
• 1.3 论文结构11-12
• 2 有向无环图的传递闭包和传递归约矩阵12-18
• 3 幂零矩阵相似条件18-21
• 4 有向区间图21-28
• 5 阶梯形矩阵28-31
• 6 三维多面体面格的传递闭包与归约相似性31-36
• 7 不相似反例矩阵的构造36-39
• 致谢39-40
• 参考文献40-44
• 附录44-46

【相似文献】

中国期刊全文数据库 前10条

1 张京良;关系传递闭包计算的补充[J];曲阜师范大学学报(自然科学版);2002年03期

2 翟璐璐,谢维奇;关系传递闭包的计算[J];河南教育学院学报(自然科学版);2005年01期

3 牛丽芳;王绪柱;段周波;;T-合成下的传递闭包[J];山西煤炭管理干部学院学报;2006年01期

4 程鹤;耿双军;;基于摄动思想的传递闭包聚类法的分析与应用[J];兰州交通大学学报;2007年04期

5 刘宏兵;周文勇;郭振;;基于模糊关系传递闭包的聚类方法[J];信阳师范学院学报(自然科学版);2008年01期

6 陈中标;;关于传递闭包算法的探讨[J];科技信息;2009年07期

7 汪小燕;;一种新的传递闭包算法研究[J];苏州科技学院学报(自然科学版);2011年04期

8 张世伟 ,朱文兴;广义模糊关系传递闭包的若干性质[J];江苏工学院学报;1986年01期

9 杨林;对传递闭包两个结论的改进[J];长沙大学学报;1999年02期

10 赵峰,刘文斌;一类典型模糊阵及其在传递闭包化简中的应用[J];青岛海洋大学学报(自然科学版);2003年02期

中国重要会议论文全文数据库 前4条

1 徐东坤;鲁明羽;;模糊聚类传递闭包失真问题研究[A];第三届中国智能计算大会论文集[C];2009年

2 邱淑芳;刘龙章;王泽文;;传递闭包矩阵t(R)算法的探讨[A];模糊集理论与模糊应用专辑——中国系统工程学会模糊数学与模糊系统委员会第十届年会论文选集[C];2000年

3 吕旭东;饶群;陈钢;王能斌;;一个带传递闭包功能的扩展SQL语言[A];第十一届全国数据库学术会议论文集[C];1993年

4 史开泉;;Fuzzy传递闭包■~*的 S-K-Q 算法[A];模糊数学和系统成果会论文集[C];1991年

中国硕士学位论文全文数据库 前4条

1 杨海峰;有向无环图的stanly问题研究[D];华中科技大学;2015年

2 赵峰;一般模糊矩阵传递闭包的计算、简化与应用[D];中国海洋大学;2003年

3 袁桂蓉;一种混合模糊聚类算法及其应用[D];重庆师范大学;2010年

4 刘承玉;基于源代码的隐蔽通道分析方法若干关键问题的研究[D];北京交通大学;2010年

，

本文编号：1020467