关于图的外连通控制、对控制及定向图的控制

来源 :天津大学 | 被引量 : 0次 | 上传用户:jrelt
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的控制理论是图论研宄中最活跃的领域之一.基于解决实际问题的需要,产生了诸多类图的控制,大体分为关于无向图的控制和关于有向图的控制两类.本文亦从实际问题出发,研宄了删去一条边对图的外连通控制数的影响,“对控制”的一些变形,并对满足控制数和其逆向图相等的有向图进行了研究.  对图G=(V,E),如果VS中的每个顶点都和S中至少一个顶点相邻,且G[VS]是连通的,则称V的子集S是图G的外连通控制集.外连通控制集的最小基数(r)c(G)称为图G的外连通控制数.本文首先给出了树删去一条边后对应的外连通控制数的可达下界,然后定义了关于边删除的(r)c-严格图(r)c-稳定图,并对其相关性质进行了讨论.  如果由N(S)导出的子图G[N(S)]中包含一个完美匹配,则称顶点子集S(C)V为邻对控制集,.如果控制集S弱导出的子图G w[ S]中包含一个与图G的最大匹配数相等的匹配,则称S为图G的弱邻域对控制集.本文给出了以上控制的上下界,进而研宄了多种“对控制”的变形之间的关系,同时还给出了在树中寻找邻对控制集的算法.  容是图G通过对每条边赋以一个方向得到的定向图,将容的每条弧的方向逆转得到定向图岔-. Y(GG)表示容的最小控制数.文章给出了满足γ(G)=γ(GG-)的定向图G的界,接着讨论了具有该类定向图的无向图的性质.此外,我们还得到如下结论:对于路和圈,它们的定向图和其对应的逆向图的最小控制数之差可以无限大.
其他文献
本文讨论了一类次二次Hamilton系统周期解的存在性和多重性问题.对于存在性问题的研宄,首先我们通过变分法,将Hamilton系统周期解的问题转化为对应泛函的临界点的问题,然后利用