学位论文 > 优秀研究生学位论文题录展示

多部竞赛图的（拟）外弧泛圈点问题

作　者: 赵会玲
导　师: 李胜家
学　校: 山西大学
专　业: 运筹学与控制论
关键词: 多部竞赛图外弧泛圈性路收缩
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 12次
引　用: 0次
阅　读: 论文下载

内容摘要

本文分为四章。研究内容主要涉及两个方面：(1)多部竞赛图中经过给定顶点所有外弧的圈问题；(2)强连通竞赛图,即每部中只有一个顶点的强连通多部竞赛图中的外弧泛圈点的个数的研究。第一章主要介绍了本文的研究背景和要解决的科学问题。第二章是预备知识。我们详细介绍了一些基本的但是非常重要的定义,并且还详细给出了在第三、四章中将要用到的所有的引理、定理和推论。第三章主要研究了多部竞赛图中经过给定顶点所有外弧的圈问题。竞赛图中外弧泛圈点个数的问题已研究的相对完善,但在多部竞赛图中这个问题则显得比较困难。2004年,Guo and Volkmann在文献[6]中证明了强连通的半完全n-部(n≥3)有向图中每个顶点都包含在一个Cq-圈中,并且对每个q∈{3,…,n｝,使得V(C3)(?)…(?)V(Cn)成立。受竞赛图中外弧泛圈点问题的启发,我们考虑在某些限定条件下的多部竞赛图中某个顶点的所有外弧是否具有上述性质。我们给出本章的主要结论：定理3.1：若D是一个强连通的n-部(n≥3)竞赛图,κ(D)=1且D中每条弧都包含在D中的一个3-圈中,则D中至少包含3个顶点v1,v2,v3使得每个vi(i=1,2,3)的外弧都包含在一个Cj·-圈中,且对每个j∈｛3,4,…,n｝,均有V(C4)(?)…(?)V(Cn)成立。第四章主要研究了连通度为1且最小外度至少为2的竞赛图中外弧泛圈点的个数问题。关于竞赛图中外弧泛圈点个数的问题已有许多结果。Feng证明了s-强连通(s≥3)的竞赛图含有s+1个4-外弧泛圈点且证明了3-强连通的竞赛图至少包含3个外弧泛圈点；Guo证明了2-强连通的竞赛图包含至少3个外弧泛圈点。因此只剩下连通度为1的竞赛图中外弧泛圈点个数的研究。下面我们给出本章的主要结论：定理4.2：设T是含n个顶点的竞赛图,κ(T)=1并且最小外度至少为2。则T至少包含3个外弧泛圈点。

多部竞赛图的（拟）外弧泛圈点问题

内容摘要

全文目录

相似论文