【摘 要】
：
图论是一门古老的数学分支,关于图论的文字记载最早出现在欧拉1736年的论著中。现如今图论在化学、物理学、生物学、运筹学、网络理论、信息论、控制论、经济学、社会科学等
论文部分内容阅读
图论是一门古老的数学分支,关于图论的文字记载最早出现在欧拉1736年的论著中。现如今图论在化学、物理学、生物学、运筹学、网络理论、信息论、控制论、经济学、社会科学等学科中都有着广泛的应用,并显示出其极大的优越性。同时,对图论中古老问题以及经典问题(如最短路问题、旅行售货商问题、中国邮递员问题等)的研究,促进了图论本身的发展。图的标号问题是图论中的一个经典问题,一个图的标号是其顶点集到整数集的一个映射,当考虑到不同要求的映射时就产生了各种类型的标号问题。图的割宽问题就是图的标号的一种,此问题在超大规模集成电路(VLSI)设计,电路布局,超大网络设计中都有着重要的应用。对一般图的割宽问题已经被证明是NP-完全的,因此我们致力于计算一些特殊图的割宽。图的割宽描述为先对顶点集V(G)的一个标号f(顶点集V(G)到{1,2,…,n}的双射),求其越过顶点的最大边数,然后对V(G)的所有标号求最大边数的最小值。这就相当于对图的顶点找到一个线性排列以及在线上用弧连接两点作为边的画法,使得垂直划分连续两点的最大边割最小化,我们称其为线性割宽lcw。本文在已知以及n-cube等特殊图的线性割宽的基础上,充分利用乘积图自身的性质,证明了下述结论：
其他文献
白钨矿结构的钼酸盐材料在光电材料领域有着极其广泛的应用。钼酸盐基质化合物具有结构稳定性好、化学组分可调性多,以及材料的合成温度低、光学性能丰富等优点。然而,钼酸盐
随着经济全球化的发展越来越快,国际体育的发展越来越繁荣,中国体育产业的发展也越来越兴盛。体育产业作为体育事业和国民经济的一部分,在促进国民身体素质提高的同时也为国家经济的发展和国际影响力的提升做出了巨大的贡献,中国也越来越多的参与到国际体育赛事的承办之中。前有2008年举国之力举办的北京奥运会、2010年的广州亚运会,2014年的南京青奥会以及接下来以地方政府力量承办的2019年武汉军运会和即将举
黄旗海作为内蒙古高原众多封闭型内陆湖泊之一,在反演干旱区气候变化方面起着极其重要的作用。关于黄旗海不同时间尺度的气候变化已经有大量的研究,但由于研究剖面以及测年方
由于很多新发现的软物质材料,如碳纳米管,在微观上都具有负曲率的结构特点,近年来越来越多的人开始将研究临界现象的统计物理模型放到非欧空间中的规则晶格结构,尤其是在负曲
教育是国之大计,党之大计。新时代背景下,我国高校思想政治教育面临着严峻考验与多重挑战,思想政治教育的“孤岛”现象以及体育艺术类专业课程的思政缺位,令人深思,亟待解决。上世纪90年代,作为一项体育与艺术高度融合的“体艺融合”性项目,体育舞蹈以体育类课程形态进入高等教育范畴,后逐步成为公共体育类课程与专业艺术类课程中的“新宠”。随着“健康中国”上升为国家战略以及高校体育、美育类课程的深化改革,体育舞蹈
设G是一个有限群,S是群G的不包含单位元1的子集,群G关于其子集S的(Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut(X)=Aut(Cay(G,S))中正规.令G=〈a,b|apq=b2=1,ab=a
本文主要研究一维零压相对论Euler方程组、一维零压气体动力学双曲守恒律系统以及带有Chaplygin的压力的Aw-Rascle交通模型含有delta函数初值的Riemann问题.本文共分为五章：第
水稻作为重要的粮食作物,优化其株型,提高其产量对解决世界粮食问题具有重要的意义。植物激素是由植物体内合成的,通过在植物组织内运输到作用部位,对植物的整个生长过程起到
湖北省地处中纬度内陆地区,每年春夏之交,强对流天气活动频繁,由于目前对强对流天气的微物理结构缺乏有效的观测手段,需要通过数值模拟来分析强对流云的发生发展过程。本文选
气象传感网具有体积小、成本低、部署易、对环境影响小、精度高等特点,适用于气象环境监测。由于气象传感器节点的密集部署和温度湿度等气象要素的时空连续性,导致节点采集数