风何图论中的若干问题

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:laden167
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
几何图论讨论由于几何关系而产生的图结构以及图的几何表示和相关问题.本文研究竞争图和双竞争图,尤其是平面点集的双竞争图,以及两个平面图同时嵌入的交叉数问题.   第一部分是竞争图问题.给定有向图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是平面图.考虑两个平面图,-个染成红色,另一个染成绿色.两个图同时嵌入在平面上时,在一定的限制条件下,红色的边与绿色的边会相交.我们称这样的交点为交叉点.在限制条件下,在所有的画法中交叉点的最小个数称为交叉数.本文第五章分别讨论了在三种限制条件下两个平面图同时嵌入的交叉数.
其他文献
学位
学位
特殊矩阵,顾名思义是指具有特殊的结构或性质的矩阵.特殊矩阵在计算数学,应用数学,经济学,统计学,物理学,生物学,计算机科学等诸多领域都有着广泛的应用.因此,无论从理论研究方面还是实
对目标进行定位和跟踪是典型的动态系统状态估计问题,在模型满足线性、高斯条件下,很多滤波算法可获得很好的跟踪效果。但若目标在高机动、多模型、非高斯、强噪声的运动背景下
在小学语文教学实践中,要想有效的提升整体的教学质量与效果,就要深入教学改革,加强合作学习,合理的应用各种教学方式与手段,构建一个高质量的教学环境,为学生的语文知识学习
本文旨在研究求解非凸半定规划的一类非线性Lagrange方法的收敛速度.其中的非线性Lagrange函数是基于L(o)wner算子构造的并且关于约束是非线性的。 在简要介绍了半定规划
本文主要研究了自变量分段连续微分方程数值解的稳定性和振动性。主要研究内容包括:第一章,概要地介绍了自变量分段连续时滞微分方程的研究目的和意义,以及近些年来在该领域的研
本文应用KAM理论有关的技巧与方法,主要研究了以下的几个问题:   1、非线性拟周期系统的约化   考虑了下面实解析非线性拟周期系统:(x)=Ax+f(t,x,ε),|x|≤r,(1)其中x∈R2
本文讨论了受控的带马尔可夫调制的跳扩散模型及其在保险金融中的应用.文中主要研究带马氏调制的跳扩散模型的随机控制问题,资产定价问题,以及几个首达时的分布.各章主要内容如
利用60Co-γ射线辐照大豆科丰14种子,获得1株具有持绿特征的突变体,该突变体经多年选育,形成20个突变系。本文从生育期、生物学性状、生育后期叶片中叶绿素含量和叶片耐衰老