距离为给定值的点对数目的若干问题

来源 :南开大学 | 被引量 : 0次 | 上传用户:guigui1998
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
极值图论是图论领域中的一个重要分支。在极值图论中一个重要的研究方向是保证图具有某种性质的前提下图的相关参数的变化,包含限制子图的极图问题是这一方向下的一个重要课题,而在这一课题中最有代表性的例子就是Turán类型问题。  早在1940年,著名数学家Turán就给出了一个分析极图的工具,同时也是图论中的一个重要的定理——Turán定理:对于任意的整数r,n,其中r>1,任何一个具有n个顶点的不包含r个顶点的完全图作为子图的简单图的边数至多为Tr-1(n),其中Tr-1(n)是Turán图的边数,n≥r。自此之后,Turán类型问题成为研究的热点问题。许多著名学者对这个问题进行了研究,并取得了许多漂亮的结果。其中,Bollobás等人对于图中含有给定长度的路的数目的极值问题进行了研究,并刻画了相应的极图。受Bollobás等人对于树上给定长度路的数目的研究的启发,Tyomky等人提出了这样一个问题:对于任意一个含有n个顶点的图,它含有距离为k的点对的最大数目是多少呢?为了探究这一问题,他们给出了一些猜想,并用计算机验证了给定确切值的小点图。更进一步,他们对于有限制条件的图得到了如下的结论:当k充分大且n足够大时,一个n阶且不含任三个顶点两两距离值为k的图中含有最大距离为k的顶点对的数目至多为(n-k+1)2/4,等号成立当且仅当此图k-同构于一个“双扫帚”。  实际上,距离相等的点对数目的极值问题很早就引起了人们的关注。当k=3时,此问题就成为化学图论中的一个著名的指数——Wiener极化指数,它是由著名化学家H.Wiener在1947年提出的。Wiener极化指数主要是在理论化学中用来反映分子的物理化学性质,药学性质等各种性质。具体来说,它可以被用在一些无圈和单圈的碳氢化合物中来量化其结构性质。很多研究人员都对此指标进行了一系列的研究并取得了一些好的结果。其中,树和单圈图中具有最大、最小的Wiener极化指数的极图已被完全刻画。  对于一般的k值,此问题的研究是困难的。本论文主要是针对给定k值为2和3的点对数目问题进行研究并得到了一些相应的结果。全文共分为五章。在第一章中,我们介绍了本文所涉及到的基本概念,研究背景以及主要结果。  在第二章中,我们主要对Tyomkyn和Uzzell的一个猜测进行了研究。猜测如下:一个具有n(≥5)个顶点且不含有三个顶点两两距离为2的简单图的距离为2的点对数目不超过(n-1)2/4+1。对于顶点数小于11的情形,他们用计算机验证了其正确性。而在这一章,我们通过对图结构的分析得到了一个更一般的结论:对于一个n(≥5)阶且不含有三个顶点两两距离为2的简单图,如果它含有一个顶点,其邻域至多被两个团覆盖,那么该图的距离为2的点对的数目至多为(n-1)2/4+1,并且我们完全刻画了其极图。  在第三章中,我们主要研究了图积下的Wiener极化指数。图积是图论中构造新图的重要方法,在网络构造和设计中有着重要的应用。在这一章,我们研究Wiener极化指数在四种图积(卡氏积、强积、直积、字典积)下的变化,并给出了图积下Wiener极化指数的关系式。  在第四章中,我们主要研究了双圈图的Wiener极化指数。杜等人给出了对于树的Wiener极化指数的一个线性算法并刻画了具有最大Wiener极化指数的极图。随后一些研究者给出了计算树、单圈图的Wiener极化指数的公式,并且刻画了给定直径、最大度条件下的单圈图中的最大、最小的Wiener极性指标的极图。在这一章中,我们给出了双圈图的Wiener极化指数的计算公式,并且刻画了具有最大、最小Wiener极化指数相应的极图。  在第五章中,我们总结了这类Turán类型问题,列出了几个已知的猜想和问题,并给出了几个有待继续探索研究的方向。
其他文献
相容结构是指一个线性空间上的两个相同类型的代数结构,这两个代数结构对应乘法的任意线性组合还构成原来类型的代数结构.双代数结构是满足一定“相容性”条件的一个代数结构
凸性和广义凸性在优化问题、均衡问题和变分不等式问题研究中起着非常重要的作用,这主要是因为凸函数在凸集上的局部极值也一定是其全局极值.但是,凸函数的局限性也十分明显.
新课程标准实施后,人们都在努力追求课堂教学的高效率。从事小学数学教学多年,深感离开了学生的自主学习,那么高效就不可能实现。而学生的自主学习如果离开了课堂上听、说、
股票市场作为金融市场的一个重要组成部分,股票的趋势与波动反映了一个国家的政治、经济和社会状况,能够指导国家宏观调控。但股票市场是一个十分复杂的非线性动力系统,影响股价
边界层问题在物理、力学和工程等实际领域中是十分重要的。至今,绝大多数工作是对边界层现象进行实验分析和数值模拟,其数学理论是很欠缺的。近几年对于不可压缩Navier - Sto
粗糙集是由波兰数学家Pawlak首先提出的一种处理不完备和不确定性知识的新型数学工具,已经在机器学习、决策分析、知识获取、模式识别和专家系统等领域取得了一些成功的应用
令Gσ是简单无向图G的一个定向图,它具有顶点集V={v1,…,vn}和弧集Γ。定向图Gσ的斜邻接矩阵定义为一个n×n矩阵S(Gσ)=(sij),其中sij=1且sji=-1如果〈vi,vj〉∈Γ,否则sij=sji
可靠性是衡量软件质量的重要指标之一。目前软件可靠性计算的方法粗略分为基于可靠性增长模型和基于架构的可靠性模型。基于架构的软件可靠性模型在可靠性计算过程中考虑了软
蛋白质三维模型相似性分析是生物信息学重要研究课题之一。蛋白质三维模型相似性分析研究有助于我们了解蛋白质的结构及其功能,从而在医药研究、计算机辅助设计蛋白质分子、
简单图G的k-边染色c称作G的k-一般邻点可区别边染色,如果▽u,v∈V(G),有Sc(u)≠Sc(v),其中Sc(x)表示与点x相关联的边的颜色所构成的集合,本文分为以下四个部分:   第一部分给出