【摘 要】
:
n-维超立方图Qn的顶点集是所有的长为n的二元串(binary string),其中的两个顶点相邻当且仅当它们恰好只在一个坐标上不同.超立方在很多方面都有应用,比如在编码理论,计算机系统结构,数学化学和种系遗传学等领域.如果一个图G能等距离地嵌入到超立方,则称G为一个部分立方图(partial cube)部分立方图在区位理论,网络理论和化学图论中都有应用背景.注意到Qn中的两个顶点的距离就是它们的
论文部分内容阅读
n-维超立方图Qn的顶点集是所有的长为n的二元串(binary string),其中的两个顶点相邻当且仅当它们恰好只在一个坐标上不同.超立方在很多方面都有应用,比如在编码理论,计算机系统结构,数学化学和种系遗传学等领域.如果一个图G能等距离地嵌入到超立方,则称G为一个部分立方图(partial cube)部分立方图在区位理论,网络理论和化学图论中都有应用背景.注意到Qn中的两个顶点的距离就是它们的汉明距离(Hamming distance),所以一个图如果是部分立方图,则就可以很容易地设计出这个图点对之问的距离.研究一个图是否是部分立方图是个基本的问题.斐波那契立方图是由超立方图的不含有两个连续1的顶点导出的子图.当它作为互连网络结构被提出来后,备受人们关注.许多斐波那契立方图的变形和推广形式,比如卢卡斯立方图,Extended-斐波那契立方图,Enhanced-斐波那契立方图,斐波那契(p,r)-立方图和广义斐波那契立方图等也被提出来,它们被统称为斐波那契类立方图.其中n-斐波那契(p,r)-立方图由Egiazarian和Astola提出,这类图为超立方Q。中那些含连续1的个数不超过r,且在这样的两个连续的1组成的子串之间所含的0的个数不少于p的顶点导出的子图.广义斐波那契立方图Qn(f)由Ilic,Klavzar和Rho提出,他们定义的广义斐波那契立方图Qn(f)为超立方Qn中不含有二元串f作为因子的顶点导出的子图.已经知道斐波那契立方图是部分立方图,一个很自然的问题就是哪些斐波那契类立方图也是部分立方图呢.本文考虑了两种斐波那契类立方图一斐波那契(p,r)-立方图和广义斐波那契立方图等距离嵌入到超立方图中的问题.全文共分五章.第一章首先介绍了本文所涉及的图的几个基本概念;其次介绍了图的等距离嵌入以及超立方图的有关概念,并介绍了部分立方图的一个经典刻画;然后介绍了斐波那契立方图和几种斐波那契类立方图以及这些图的一些性质与应用;最后列出了本文的主要结论.第二章研究了斐波那契(p,r)-立方图等距离嵌入到超立方图的问题.我们确定了n-维斐波那契(p,r)-立方图Γn(p,r)是部分立方图当且仅当p=1,或者p≥2且r≤p+1.进而我们指出Γn(p,r)是Qn的等距离子图当且仅当它是部分立方图,并且对于斐波那契(p,r)-立方图来说,部分立方图,semi-median图和almost-median图是等价的.在第三章我们解决了Ilic, Klavzar和Rho提出的一个问题和三个猜想.他们提出问题是:如果Qd(f)不是Qd的等距离子图,那么是否存在d,,使得Qd(f)能够等距离地嵌入到Qd,中去呢?同时他们还给出一个猜想:如果Qd(f)是Qd的等距离子图,则Qd(ff)也是Qd的等距离子图.他们的另一个猜想是:对于任意一个坏串f,都有B(f)<2|f|,其中B(f)是Qd(f)不能等距离地嵌入到Qd的最小维数d.在第三章我们首先证明了对于任意的一个坏串f,Qd(f)都有2或者3-critical words,并据此指出了上述的问题的答案是否定的,并证明了这两个猜想.他们还有一个猜想是:如果f是恰好含有两个0的坏串,则f是2-等距的当且仅当f=12r-1012r-1012r+1,其中r≥0.在第三章我们说明了这个猜想是不正确的,并且指出:如果f是恰好含有两个0的坏串,则f是2-等距的当且仅当f=1r01r012(r+1),其中r≥0.在第四章我们首先研究了某些具有特殊结构的禁用因子的广义斐波那契立方图在超立方图的等距离嵌入性,给出了若干有2n个或者2n+1个块的好串和坏串;然后讨论了具有4个块和5个块的禁用因子的广义斐波那契立方图在超立方的等距离嵌入性,给出了全部的有4个块和5个块的好串和坏串,并对每一个坏串f给出了Qd(f)能等距嵌入的超立方的(最大)维数;最后由这些讨论,给出了所有的长是6和7的禁用因子对应的广义斐波那契立方图在超立方的等距离嵌入性.第五章对本文的工作进行了总结,并对以后的研究工作进行了展望.
其他文献
利用ANSYS Workbench对2800型压裂泵曲轴进行有限元分析,研究了实际工况下曲轴的应力分布。通过分析阶梯型圆角结构的尺寸与曲轴最大应力的关系,得出随着圆角尺寸r的增大,曲轴最大应力曲线呈现出先降低后增大的趋势;随着圆角尺寸h的增大,曲轴的最大应力呈现先降低后增高的趋势,且在h大于3.5mm以后应力值趋于平缓,从而得到阶梯型圆角的最优尺寸,对比普通圆角结构曲轴,阶梯型圆角结构明显地优化了
作为语文教师,我们常常发现,反复强调的知识点,到了学生这里却不曾留下深刻的印记;教师教过、并且以为学生已然掌握的知识技能,却并未在新的学习情境中得以理想化的显现;教师鼓励、提倡学生提出问题,然而学生根本提不出问题,或是提出的问题往往与文本核心相去甚远。究其原因,一是教师一直以来形成的思维习惯,我们迫切希望学生学得精准、学得牢靠,为教而教,因此,知识点与能力点,
受弦理论,特别是AdS/CFT对偶的研究启发,膜世界理论提出了新的额外维紧致机制,为解决层次问题提出了全新的解决方案,同时也为中微子手征性、暗物质、宇宙学常数问题等长期没有解决的问题提供了新的可能的解决方案。虽然在四维时空中,Einstein的广义相对论很好地描述我们的观测,但是Einstein理论面临一些的问题,比如奇点和不可重整化问题。为了解决这些问题,我们需要量子引力。虽然我们依然不知道完整
基于年际平均降水量和年际平均潜在蒸腾量比值的干燥度指数是定量测量陆地气候干燥程度的科学指标。干燥度指数越小,气候越干燥,比如沙漠地区的干燥度指数接近于零。干燥度指数还可以用来划分干旱半干旱区:小于0.05是极端干旱区,在0.05和0.2之间的是干旱区,0.2-0.5是半干旱区,0.5到0.65之间的则是湿润偏干区。定量的研究干燥度演变及其演变机制对水资源使用、陆地使用管理有重大意义。本论文在前人工
本文主要研究了一般椭圆算子在均匀化问题中的一致正则性和收敛速率的问题。本研究的进展是基于下面的三个方面。其一,在上世纪80年代末,M. Avellaneda和林芳华发表了一系列的论文,系统的研究了只有主部项的二阶椭圆算子带Dirichlet边值条件在均匀化问题中的一致Holder估计,Lp估计(1
称一个代数是有限基的,如果它满足的等式可以由有限多个等式导出.否则,称这个代数是非有限基的.有限代数的有限基问题是泛代数的经典研究课题.对于一些经典的代数系统,如,有限群、有限环、有限格以及有限李代数,已经被证明是有限基的.但有限半群的有限基问题仍是一个公开问题.本学位论文主要利用句法分析的方法,研究了n元链上的一类变换半群,(域,半环,分配格上的)二阶上三角矩阵半群及广义Rees矩阵半群的有限基
本论文的主要内容包括两部分:首先,利用基于协变密度泛函的五维集体哈密顿量研究了A~100区原子核低激发谱中的三轴性;其次,给出了轴对称形变的相对论Hartree-Fock理论的理论框架,并在坐标空间求解出介子场和库仑场传播子,且精确再现了原有平均场的结果。A~100区原子核三轴性基于PC-PK1能量泛函的五维集体哈密顿量研究了丰中子Mo同位素链及N=60同中子素链低激发结构。研究表明,当考虑了三轴
物种丰富度沿环境梯度变化的决定因素一直是生态学研究的重点之一,理解物种丰富度的一般性决定因素对物种保护尤为重要。影响物种丰富度的因素大体包括两个方面:环境因素和生物因素。关于物种丰富度的环境决定因素,已有很多种假说被提出但是只有一小部分对物种丰富度有潜在的预测能力。环境异质性假说和能量假说中的生产力假说都是被频繁讨论的对象,但仍没有一个共识性结论。除了被广泛证据支持的物种丰富度与环境异质性之间的正
2000年以来,全球增暖过程中出现了增暖速度减缓的阶段性特征,部分学者称之为“全球增暖的停滞(Global Warming Hiatus)”。同期,欧亚大陆冬季冷事件频繁发生。由此,气象工作者再度将注意力转向关于冬季低温事件的研究。对冬季低温事件研究必然会涉及如下的一些科学问题:(1)如何客观识别区域性低温事件(Regional Low Temperature Event,RLTE),近50多年R
本博士学位论文主要考虑了几类具有复杂非线性项的椭圆问题解的存在性及多解性.在这里,复杂非线性是指:带有非线性边界条件,算子是非线性的,外力项不满足(AR)条件.本文共有六章:第一章是绪论,主要介绍了本文的研究背景,研究的问题以及得到的主要结论.第二章是预备知识,介绍了后面要用到的比较原理,非线性泛函分析知识,变分法以及椭圆方程的一些重要的结论.第三章,我们研究了有界区域上的带有非线性边界条件的椭圆