论文部分内容阅读
有向图的控制图是由D.C.Fisher等人在研究有向图的竞争图时提出的概念,并在同一篇文章中完全刻画了竞赛图的控制图的结构.已经证明有向图的控制图的补图同构于有向图补图的竞争图,而竞争图广泛应用于生态系统,无线电广播研究及噪声信道下通信的研究等方面.因而,有向图的控制图越来越受到学者们的关注.多部竞赛图是竞赛图的一种重要推广,本文在竞赛图的控制图的基础上,研究几类多部竞赛图(正则多部竞赛图,扩充竞赛图,二部竞赛图)的控制图.通过观察顶点数较少的多部竞赛图的控制图的特点,找到所研究的图类的控制图的规律,并给出证明. 本文共分为四章. 第一章综述控制图的应用背景,研究现状以及一些与本文相关的基本概念. 第二章研究了正则多部竞赛图的控制图,刻画了正则多部竞赛图的控制图的结构特征,通过证明得到了:G是每个部集恰有m个顶点的正则n部竞赛图( n>3)的控制图,当且仅当G是下面的情形之一: (i)如果 m=2,则 G是 k个私加上2n-2 k个孤立点构成的图,这里 k可取0,1,2,…,n—2, n; (ii)如果 m>3,则 G是空图. 第三章研究了扩充竞赛图的控制图,给出了求解扩充竞赛图的控制图的算法,通过证明得到了:设 D= T[S1,&S2,…,Sn是扩充竞赛图,其中 T是 n个顶点的竞赛图, V(T)=[vl,v2,...,vn},Si(i=1,2,…,n)是孤立点集,设x,y GV(D),则 xy是 D的控制图 dom(D)中的一条边当且仅当下面三种情形之一成立: ⑴存在 i,j∈{1,2,…,n}使得 Si={x}, Sj={y}, i≠ j,且 Si, S j对应于T上的顶点 v“ v j满足 V i,V j是 dom(T)的一条边; (ii)存在 i, j∈{1,2,…,n}使得Si={x},|Sj|≥2,y∈ Sj,且氏, Si,Sj对应于T上的顶点 v i,v j满足 v i,v j是 dom(T)的一条边,且在 T中,υi→υj; (iii)存在 i∈{1,2,…,n}使得Si={x,y},且在 T中 Si对应的顶点 v控制除其本身之外的所有顶点. 第四章从矩阵的角度研究了二部竞赛图及其竞争图,并给出了一般有向图的控制图与竞争图的关系,由此给出二部竞赛图的补图的竞争图,通过证明得到了: (1)设D=是一个有向图,则dom(D)=[C(Dc)]c,其中C(De)是D的补图的竞争图. (2)设 m>1,n>1是整数,G是 n+ m个顶点的无向图,则下面两个叙述等价: (i) G是某个二部竞赛图H=( X, Y)的竞争图,其中|X|= m,Y|= n; ( ii)存在布尔矩阵此处公式省略:,使得 G是 A的行图.其中 O1,O2分别是m×m和 n×n的零矩阵,B和 C分别是mxn和 nxm的布尔矩阵,且 BT+ C是一个全1矩阵.