有向超图理论及其有向和标号

来源 :重庆大学 | 被引量 : 0次 | 上传用户:seryhugjkghj
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
为了恰当地表示大型超网络、数据库系统、时间安排和线路设计等研究课题中各元素之间的关系,有向超图模型做为一般图的推广被自然的引入。由于其良好的应用背景,有向超图理论成为现在图论领域中迅速发展的子学科之一。本论文首先综述了无向超图的基本概念和研究现状,然后统一各种文献中有向超图的概念。文章根据有向超边的大小定义了不同类型的有向超图,并通过作对称象和添加虚拟顶点等不同方法实现了各类有向超图之间的转换。另外定义了有向超图的基础超图和有向二部图,它们在后面的讨论中有非常重要的应用。其次,在有向超图的性质方面,重点研究了路径、超路径间的关系,在这里定义顶点间连通与超连通。给出一个求解无向超图和有向超图中最短路径的有效算法,并且提出有向超图中的最短超路径问题。同时研究了有向超图的可平面性,通过定义有向超图的结构图,在有向超图的可平面性判断与其结构图的可平面性判断之间,在BF-超图的可平面性判断与无向超图的Zykov平面性判断之间建立起等价关系,并且证明这些判断都是可在线性时间完成的。第三,有向超图的应用是本论文研究的重点之一,受无向超图的各种特殊标号方式的启发,提出了基于有向超图的一种新的标号方式——有向和标号,即对有向超图顶点的一一映射整数标号,使每一条有向超边的头顶点和尾顶点的标号和相等。结合定义给出了一个有向超图存在有向和标号的充要条件以及几个必要条件。将判断有向和标号的存在性和求解由关联矩阵确定的线性方程组联系起来,给出了有向和标号的算法以及标号的一般步骤。特别地,文章讨论了B-超图和有向星这两类特殊有向超图的标号情况,给出了B-超图有向和S的范围,并对不同类型的有向星标号情况作了讨论。最后提出了有向和标号继续研究的两个新方向:1).添加孤立点后的标号问题;2).基于有向和标号的规划问题。在系统建立有向超图理论的基础上,本文研究了有向超图的路径与超路径以及有向超图的可平面性这两个非常重要的性质。并结合实际问题的需要,研究了全新的标号方式——有向和标号,对有向超图给出了求解标号存在性以及标号方式的算法和求解步骤。
其他文献
利用Zope和Mishin提出的Ti-A1势函数形式,采用嵌入原子势描述原子间的相互作用,选取含25%A1原子的Ti-A1无序固溶体为研究对象,开展在两种给定降温速率和不同压力条件下Ti-A1合金
以利用物探资料寻找隐伏铁矿的工作为例,通过对某地区重磁电十字剖面资料的推断解释,总结了减少物探异常解释多解性的思路与做法,提出在布置外业工作和收集资料时,就应考虑为
在信息化时代,如何有效运用现代信息化技术,通过财务内部控制实现全面风险管理成为医院管理研究的热点。阐述了医院内部控制的目标,剖析了当前医院内部控制和风险管理存在的
本刊讯2017年5月,经中国科学引文数据库(Chinese Sciences Citation Database,简称CSCD)的定量遴选、专家定性评估评议,本刊入选中国科学引文数据库核心库(2017—2018年度证书编
以乌努格吐山试验区钻孔岩芯中MgO、CaO、Na4O贫化现象为切人点,结合乌努格吐山斑岩铜钼矿床蚀变分带明显和矿化特征,发现钻孔中CaO、MgO、Na2O等组分相对各自丰度明显贫化的信
目的比较枸橼酸钠抗凝与低分子肝素钠抗凝对高危出血倾向患者连续血液净化(CBP)的凝血、电解质、血脂和炎症因子的影响。方法收集2015年1月~2017年3月在我院行CBP治疗的125例
预算执行审计实施五年来,探索出了一些好的方法,积累了许多好的经验,也取得了比较明显的成效.但还面临一些亟待解决的问题,值得我们深思和研究.
目的:研究和探讨优化大型综合医院辐射安全管理体系、降低工作人员和公众辐射风险的策略。方法:运用SWOT分析法对大型综合医院辐射安全管理现状和对策进行深入解析研究。结果
目的:研究基质金属蛋白酶(MMP)在急性胰腺炎(AP)肺损伤(APALI)与炎症后组织重建中的作用及机制。方法:应用雨蛙素、L-精氨酸制备大鼠急性水肿型胰腺炎(AEP)模型和急性坏死型
[背景与目的]肠易激综合征(irritable bowel syndrome,IBS)是常见的功能性肠病,其发病机制尚不清楚。在前期工作中,本课题组应用蛋白质组学方法,通过双向凝胶电泳及质谱分析