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

作     者：程绩 

作者单位：重庆大学 

学位级别：硕士

导师姓名：龚劬

授予年度：2006年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：有向超图 超路径 可平面性 有向和标号 

摘      要：为了恰当地表示大型超网络、数据库系统、时间安排和线路设计等研究课题中各元素之间的关系,有向超图模型做为一般图的推广被自然的引入。由于其良好的应用背景,有向超图理论成为现在图论领域中迅速发展的子学科之一。 本论文首先综述了无向超图的基本概念和研究现状,然后统一各种文献中有向超图的概念。文章根据有向超边的大小定义了不同类型的有向超图,并通过作对称象和添加虚拟顶点等不同方法实现了各类有向超图之间的转换。另外定义了有向超图的基础超图和有向二部图,它们在后面的讨论中有非常重要的应用。 其次,在有向超图的性质方面,重点研究了路径、超路径间的关系,在这里定义顶点间连通与超连通。给出一个求解无向超图和有向超图中最短路径的有效算法,并且提出有向超图中的最短超路径问题。同时研究了有向超图的可平面性,通过定义有向超图的结构图,在有向超图的可平面性判断与其结构图的可平面性判断之间,在BF-超图的可平面性判断与无向超图的Zykov平面性判断之间建立起等价关系,并且证明这些判断都是可在线性时间完成的。 第三,有向超图的应用是本论文研究的重点之一,受无向超图的各种特殊标号方式的启发,提出了基于有向超图的一种新的标号方式——有向和标号,即对有向超图顶点的一一映射整数标号,使每一条有向超边的头顶点和尾顶点的标号和相等。结合定义给出了一个有向超图存在有向和标号的充要条件以及几个必要条件。将判断有向和标号的存在性和求解由关联矩阵确定的线性方程组联系起来,给出了有向和标号的算法以及标号的一般步骤。特别地,文章讨论了B-超图和有向星这两类特殊有向超图的标号情况,给出了B-超图有向和S的范围,并对不同类型的有向星标号情况作了讨论。最后提出了有向和标号继续研究的两个新方向: 1).添加孤立点后的标号问题;2).基于有向和标号的规划问题。 在系统建立有向超图理论的基础上,本文研究了有向超图的路径与超路径以及有向超图的可平面性这两个非常重要的性质。并结合实际问题的需要,研究了全新的标号方式——有向和标号,对有向超图给出了求解标号存在性以及标号方式的算法和求解步骤。