有向图的可迹性与泛连通性点对

摘要

本文分为两章对局部内(外)半完全有向图及其扩张有向图的可迹性和竞赛图及扩张竞赛图中的泛连通性点对这两个方面分别作了讨论. 第一章里我们研究了局部内(外)半完全有向图及扩张的局部内(外)半完全有向图的可迹性问题.1.1节介绍了与内容相关的概念和引理.1.2节证明了对于连通的n阶局部内半完全有向图D，若它中任意不相邻的受控点对{x，y}，满足d(x)≥n，d(y)≥n-1，或d(x)≥n-1，d(y)≥n，则D是可迹的.同时还证明了对n阶连通的局部内半完全有向图D中的任意不相邻的受控点对{x，y}，若min{d+(x)+d-(y)，d-(x)+d+(y)}≥n-1，则D可迹.然后，利用逆图的性质我们把这两个结论推广到连通的局部外半完全有向图中.1.3节研究了n阶连通的扩张局部内半完全有向图D的可迹性.我们证明了对于D中任意不相邻的受控点对{x，y}和D中任意不相邻的控制点对{u，v}，如果d(x)≥n，d(y)≥n-1，或d(x)≥n-1，d(y)≥n，且d(u)≥n-1，d(v)≥n-1，则D是可迹的.同时我们将此结论推广到了连通的扩张局部外半完全有向图中. 第二章研究了竞赛图和扩张竞赛图中的泛连通性点对.首节给出了与内容相关的基本概念和相关结论.2.2节证明了阶为n的连通的但非强连通的竞赛图T中存在两点u,v使得{u，v}是T的泛连通性点对，并且给出了寻找这个点对的一个好算法.同时我们还得到若D是可传递的竞赛图，则在D中存在唯一的泛连通性点对.2.3节给出了扩张竞赛图中存在泛连通性点对的两个充分条件，并且证明了若D是可传递的多部竞赛图，且不是竞赛图，则D中无泛连通性点对.

目录

文摘

英文文摘

引言

第一章局部内(外)半完全有向图的可迹性

第二章竞赛图与扩张竞赛图中的泛连通性点对

结论

参考文献

发表文章目录

致谢

个人简介及联系情况

承诺书