论文部分内容阅读
本研究内容涉及图论的两个方面:强连通的弧-准传递有向图的结构;两类变换图是平面图的充要条件。有向图D是局部半完全的,如果它的每一个顶点的内邻集和外邻集都分别诱导出一个半完全有向图。受此启发,1993年,Bang-Jensen给出了弧-局部半完全有向图的定义,证明了半完全二部有向图中哈密尔顿路和圈的结论,以及这些问题的多项式时间可解决性都可以推广到弧-局部半完全有向图中。并且刻划了强连通的弧-局部半完全有向图的结构。第一章中,我们称不包含H3和H4作为诱导子图的有向图为弧-准传递有向图,即:若有z,w∈V(D)-{x,y},满足x→z,z→w,w→y或x→z,w→z,w→y,则x和y一定是相邻的顶点或者是同一个顶点.它可以看作是准传递有向图定义的推广.本文的第一章主要讨论了强连通的弧-准传递有向图的结构。无向图G的全图T(G)是以V(G)∪E(G)为顶点集的图,且T(G)中的两个顶点相邻当且仅当它们在G中相邻或关联。按照类似的方法,BaoYin Wu给出了G的变换图Gzyz的定义.根据这个定义,G的变换图Gxyz共有八类.目前关于这几类变换图已经有很多的结果,如关于它们的直径,连通性以及平面性等等。第二章得到了变换图G--+和G-+-的平面性的充要条件。本文的主要结果叙述如下:定理1.3.3设D是一个强连通的弧-准传递有向图,则D是半完全的或是半完全二部的,或D(≌)M或D(≌)M;推论2.3.1设G是一个图,则G--+是平面图当且仅当n≤3或G同构于2K1+K2,K1+K1,2,K1,3或K1+C3;定理2.3.2设G是一个图,则G-+-是平面图当且仅当n≤4且G(≌)K4-e。