几何图论中的若干问题

论文摘要

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

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 绪论
• §1.1 竞争图
• §1.2 竞争数
• 第二章 竞争图和竞争数
• §2.1 准备知识
• §2.1.1 各种竞争图
• §2.1.2 各种竞争数
• §2.1.3 相交图与相交数
• §2.2 竞争图的判定
• §2.2.1 有向图的竞争图
• §2.2.2 偏序集的竞争图
• §2.3 竞争数的刻划
• §2.3.1 有向图的竞争数
• §2.3.2 偏序集的竞争数
• 第三章 平面点集的竞争图
• §3.1 准备知识
• §3.2 平面点集的偏序集的性质
• §3.3 平面点集的竞争图的判定
• 第四章 平面点集的双竞争图
• §4.1 平面点集的双竞争图是梯形图
• §4.1.1 准备知识
• §4.1.2 DC（D）的性质
• §4.1.3 定理4.1.1的证明
• 2的一些说明'>§4.1.4 对DPK²的一些说明
• §4.2 D的两个极小禁用子图
• 2上的分布情况'>§4.2.1 D中某些图的顶点在R²上的分布情况
• §4.2.2 定理4.2.1的证明
• §4.3 D与其它图类的关系
• §4.3.1 图类以及可比较性
• §4.3.2 D与梯形图子类的关系
• §4.3.3 D与容忍图类及其子类的关系
• 第五章 带限制条件的两个平面图同时嵌入的交叉数
• §5.1 准备知识
• §5.2 主要结果
• 2²（G₁∨G₂）和Cr₂²（G₁∧G₂）的精确值'>§5.2.1 Cr₂²（G₁∨G₂）和Cr₂²（G₁∧G₂）的精确值
• 3²（G₁∨G₂）的上界'>§5.2.2 Cr₃²（G₁∨G₂）的上界
• 第六章 结束语
• 结束语
• 参考文献
• 附录一 致谢
• 附录二 作者读博士期间发表和录用论文情况