论文部分内容阅读
几何图论讨论由于几何关系而产生的图结构以及图的几何表示和相关问题.本文研究竞争图和双竞争图,尤其是平面点集的双竞争图,以及两个平面图同时嵌入的交叉数问题.
第一部分是竞争图问题.给定有向图D=(V(D),A(D)).它的竞争图C(D)以V(D)为顶点集,以{uv∈(V(D)2):()w∈V(D),(uw),(uw)∈A(D))为边集;而它的双竞争图DC(D)以V(D)为顶点集,以{uv∈(V(D)2):()w1,w2∈V(D),(uw1),(vw1),(w2u),(w2v),∈A(D)}为边集.竞争图的概念是1968年著名生物学家Cohen在研究生态系统时提出的,后来衍生出双竞争图等概念.除了在生物上的应用,竞争图在编码理论,噪声信道通讯研究,无线电广播研究及复杂经济与能量问题的建模方面有广泛的应用.偏序集作为无圈且具有可迁性的有向图,也可以定义其竞争图和双竞争图.维数不超过2的偏序集以平面R2上的点作为顶点,有向弧从点(x1,y1)指向点(x2,y2)当且仅当x1>x2且y1>y2.我们把维数不超过2的偏序集的(双)竞争图称为平面点集的(双)竞争图.本文前四章对有向图和偏序集的竞争图和双竞争图,特别是对平面点集的竞争图和双竞争图,进行了讨论.
第一章主要讲述了竞争图的研究背景和发展现状.
第二章首先总结了竞争图判定以及竞争数的已有结果.然后给出了偏序集竞争图的刻划,并且揭示了图的偏序集(双)竞争数与其(双)相交数之间的关系.
第三章主要讨论平面点集的竞争图.我们证明了图G是平面点集的竞争图当且仅当G是区间图而且G的极大团中至少有一半是孤立点.这一结果回答了Cho和Kim提出的公开问题.
第四章主要讨论平面点集的双竞争图.这种双竞争图的集合我们记为().我们首先证明了()为梯形图的真子类,这一结果推广了Kim,Kim和Rho的结论,同时给出了判定某个图在图类D中的一些必要条件;然后找出D的两个极小禁用子图;最后讨论了D与梯形图子类及容忍图子类之间的关系.
第二部分研究两个平面图同时嵌入的交叉数问题.如果图G能嵌入在平面上,而且它的任意两条边除了公共端点外不相交,则G是平面图.考虑两个平面图,-个染成红色,另一个染成绿色.两个图同时嵌入在平面上时,在一定的限制条件下,红色的边与绿色的边会相交.我们称这样的交点为交叉点.在限制条件下,在所有的画法中交叉点的最小个数称为交叉数.本文第五章分别讨论了在三种限制条件下两个平面图同时嵌入的交叉数.