Randic指标与图的若干不变量

来源 :南开大学 | 被引量 : 0次 | 上传用户:ruhua529
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在历史上,图论与化学有着非常紧密的联系。化学结构可以很简单地表示成图的形式,这样的图也称为化学图,或者分子图。分子的拓扑指标足从化学图集合到实数集合的一个映射,理论化学家和数学家提出了众多的拓扑指标并进行研究.本文主要研究一种广受化学家和数学家关注的拓扑指标--Randic指标,研究Randic指标与图的其它若干不变量之间的关系,如色数,半径,直径,最小度,最大度,阶数和边数,等等.   1975年著名理论化学家、数学化学家Randic提出了连通性指标,即Randic指标。(化学)图G的Randic指标定义为R(G)=∑uv∈E(G)(d(u)d(v))-1/2,其中d(u)表示图G中顶点u的度数。Randic指标与分子的物理化学性质,如沸点、表面积等,都有着紧密的联系。1998年,著名数学家Bollobas和Erdos将R(G)中的-1/2替换为任意的实数α,从而提出了广义Randic指标的定义。理论化学家和数学家对广义Rndic指标进行研究,并且得到了很多重要而深刻的结果。   第一章是引言部分,介绍了Randic指标的定义、研究背景,以及本文中涉及到的相关概念和基本知识。以下五章为本文的主要贡献:   在第二章中,我们指出了Hansen和Melot的文章[Variable neighborhoodsearch for extremal graphs6:Analyzing bounds for the connectivity index,J.Chem.Inf.Comput.Sci.43(2003),1-14]中两个定理证明的错误,并给出了正确的证明.这两个定理刻画了化学树的Randic指标和叶子点数之间的联系.   在第三章中,我们讨论了图G的Randic指标R(G)和最小度δ(G)之间的关系,并部分解决了Bollobas和Erdos提出的公开问题。1988年,Shearer证明了如果图的最小度δ(G)≥1,那么R(G)≥√G≥√n/2,几个月后Alon将这个界改进到√n-8。1998年,Bollobas和Erdos证明,如果δ(G)≥1,则有R(G)≥√n-1,其中等号成立当且仅当G是星图。Bollobas和Erdos提出如下问题:给定图G的最小度δ(G),R(G)的最小值是多少?在2002年,Delorme,Favaron和Rautenbach针对这一问题提出了如下猜想:如果图G的最小度δ(G)≥k,那么R(G)≥k(n-k)/(√k(n-1),其中等号成立当且仅当图G是由完全二部图Kk,n-k做如下变换得到:在Kk,n-k知含有k个顶点的那部分内的任意两个顶点连一条边.提出猜想后,他们证明了k=2时猜想是成立的。我们验证了k=3时猜想的正确性,由此很容易地得到猜想中的不等式对所有的化学图也是成立的。更进一步,我们证明了当k≥4时,如果图的顶点数满足n≥3/2k3,则猜想是成立的。   在第四章的第一部分,我们完全解决了Caporossi和Hansen提出的关于图的Randic指标和色数的猜想:对顶点数n≥2的连通图G,R(G)≥x(G)-2/2+1/√n-1(√X(G)-1+n-X(G)),而且对所有的n以及2≤X(G)≤n,这个界是紧的,其中图G的色数X(G)是指使得图G有正常顶点着色(相邻顶点所着颜色不同)的最小颜色数目.在第二部分中我们考虑了Fajtlowicz提出的关于图的Randic指标和半径的猜想:对任意连通图G,R(G)≥r(G)-1,其中图G的半径r(G)=minν∈G mayu∈(G)d(u,ν)。根据Erdos等人的关于图的半径和最小度的结果,我们证明了若G是具有n个顶点,最小度为δ(G)的连通图,如果δ(G)≥n/5且n≥25,则猜想成立;更进一步,对任意实数0<ε<1,如果δ(G)≥εn,则对充分大的n,猜想都是成立的。   在第五章中,我们考虑了具有n个顶点、m条边的化学图的广义零阶Randic指标的极值问题,其中广义零阶Randic指标定义为0Rα(G)=∑u∈V(G)d(u)α。对任意的实数α,我们用图的顶点数和边数给出了广义零阶Randic指标的严格上界和下界,刻画了相应的极图。   在第六章中,我们研究了图G的反比度I(G)和直径D(G)的关系,其中反比度的定义为I(G)=0R-1(G)=∑u∈V(G)1/d(u)。Erdos,Pach和Spencer证明,对具有n个顶点的连通图G,若I(G)≥3,则有(2/3[r/3]+o(1)logn/loglogn≤μ(n,r)≤D(n,r)≤(6r+o(1))logn/loglogn,其中μ(G)是图G的平均距离,μ(n,r)=max{μ(G):I(G)≤r},D(n,r)=max{D(G):I(G)≤r}。Dankelmann等人将此上界改进了2倍,即D(G)≤(3I(G)+2+o(1))logn/loglogn。针对树和单圈图,我们将Dankelmann等人的上界改进了4/3·lolgn/loglogn倍,并且证明此时的界是最好的,确定了达到此上界的极图。
其他文献
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
人文素养是人外在风貌和内在气质的综合体现,是人最核心的人生观价值观的外在表现.本文从现代理工科大学生人文素养缺乏的现象入手,说明正确读史是理工科学生提升个人人文素
“晶红宝”是从以“瑰宝”为母本、“无核白鸡心”为父本的杂交后代中选育出的中熟无核葡萄新品种。2012年通过山西省农作物品种审定委员会审定并命名。该品种果穗双歧肩圆锥
电路划分问题是超大规模集成电路(VLSI)布线中的一个重要过程,它是降低集成电路布线复杂性、提高电路性能的一种有效方法,因此设计相应的电路划分算法就显得十分必要。针对该问
本文主要研究了两类生态一流行病模型,一类是食饵染病且具有非线性传染率的模型,另一类是捕食者染病且具有最优收获的Holling-Tanner系统.这两类模型将生物数学的两个分支即种
培养学生创新精神和实践能力为重点,深入推进素质教育,培养学生创新能力是历史教学的一项重要任务。
全局优化研究的是多变量非线性函数在某个约束区域上全局最优点的特征和计算方法.全局优化问题已广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域.分支定界
自矩阵的M-P逆被定义以来,矩阵的广义逆得到了飞速的发展,各种广义逆不断地被人们定义、研究。矩阵理论体系越来越完善,矩阵广义逆的应用也越来越广泛。鉴于此,本文在现有文献的
超几何函数、椭圆积分、偏差函数以及与其相关的其他特殊函数在数学学科的许多重要分支、某些其它学科及工程技术中都有着重要的应用。其中,Hersch-Pfluger偏差函数φK(r)是拟
移动平面法是由前苏联数学家Alexanderoff在20世纪50年代早期创立的。接下来的几十年里,Serrin,Gidas,Ni和L.Nirenberg,Caffarelli,Gidas,Spruck,Y.Li,W.Chen和C.Li,Chang and Yang等