【摘 要】
：
平图是指能够画在平面上使得它的边仅在端点处相交的图.在这篇文章中我们只讨论无向的简单平图.简单图是没有重边也没有环的图.设G=(V(G),E(G),F(G))是一个平图,其中V(G),E(G
论文部分内容阅读
平图是指能够画在平面上使得它的边仅在端点处相交的图.在这篇文章中我们只讨论无向的简单平图.简单图是没有重边也没有环的图.设G=(V(G),E(G),F(G))是一个平图,其中V(G),E(G),F(G)分别是G的点集,边集,面集.对于面f∈ F(G),它的边界上的点数称为面f的规模,记为g(f).对一个平图G,G的最小面规模记为g(G).设{1,…,k}是颜色集.图G的顶点的k-染色定义为:φ:V(G)→{1,…,k}.若k种颜色在f∈F(G)上全部出现,则称f是k-多色的.如果一个顶点的k-染色φ使得G的每个面(包括无界面)都是k-多色的,则称φ为图G的一个多色kk-染色.G的多色染色数是使得G存在多色k-染色时最大的k,记为p(G).定义:p(g)=min{p(G)|g(G)=g}即p(G)表示最小面规模为g的平图类多色数的下确界.首先,我们定义平图G的简化对偶图H(G).H(G)也是一个平图.H(G)的点集就是F(G).如果G的两个面有公共的二度点,则这两个面在H(G)中对应的两个点是相邻的.如果我们将一个二度点染上一种新颜色,二度点关联的两个面同时得到了这种新颜色.我们的工作拓展了Alon等人p(g)≥「3g-5/4」的结果.我们讨论了三类特殊的平图,分别是简化对偶图为奇圈、偶圈和星的平图.借助于H的边覆盖分解,我们可以将p(g)的下界从「3g-5/4」提高到「3g-5+w/4」,其中w≥0是一个整数.我们给出了当w>0时的相关结论,在这些情形下推广了Alon等人的相关结果.其次,对于一般的简单平图,根据简化对偶图的边覆盖分解讨论了多色染色.对于任意的平图,最小度至多是5.根据Gupta的结果任意的简单图G可以分解成s个不相交的边覆盖,其中δ(G)-1≤s≤δ(G).我们可以将p(g)的下界从「3g-5/4」提高到「3g-5+sw/4」,其中w≥0是一个整数.本论文共分四章进行讨论.第一章,我们主要介绍了图的多色染色问题背景及重要意义,给出了本篇论文中所涉及到的基本概念与符号,并且列出了本文的主要结果.第二章,我们讨论了三类特殊平图的多色染色问题.第三章,我们讨论了一般平图的多色染色问题,拓展了一些之前的结果.第四章,我们给出了多色染色中可进一步研究的问题.
其他文献
本文以Baker et al.(2016)构建的经济政策不确定性指数作为中国经济政策不确定性的代理变量,研究经济政策不确定性与我国商业银行贷款拨备计提的关系。结果表明经济政策不确定性与商业银行的贷款拨备之间存在显著的正相关关系。这是因为经济政策不确定性会对加大银行与企业之间的信息不对称程度、降低客户偿债能力以及影响银行管理层在计提贷款拨备时对企业偿债能力的估计,导致商业银行在经济政策不确定性增加时
随着现代计算机体系结构迎来发展的黄金时期,多核架构成为越来越多处理器的选择。然而,目前多核系统的任务调度算法存在收敛速度较慢、难以跳出局部极值等问题,提出一种稳定、高效的任务调度算法,对于充分发挥多核处理器的架构优势和提升任务集合的计算并行度都具有重要意义。论文围绕生物地理学算法的不足,提出算法改进策略。首先引入栖息地相似度的概念来表征个体之间的差异,在初始化生态系统时,只允许相似度足够小的个体加
动产多重买卖,是指出卖人将同一动产先后卖给不同的买受人,这种现象在商品交易中经常出现。在当今社会经济生活中,商品交易往往数额巨大,多重买卖一旦发生将会带来重大影响,
图像风格迁移是指学习一幅画作的艺术风格,然后再把这种风格应用到另外一张图片上。风格迁移通过提取出画作中的风格语义,并以数据表达出图像的风格特征,从而对另外一张图片的风格进行修饰,修改图像特征,实现风格迁移。图像风格迁移对于图像修复和图像分类都有着重要的作用,是计算机图像处理中的一个重要研究方向。近年来伴随着神经网络的发展,许多基于神经网络的图像风格迁移方法被提出,然而将这些方法用于中国绘画,效果却
随着汽车工业的快速发展,人们不仅关注汽车的动力性能,而且更加注重汽车的乘坐舒适性。汽车行驶过程中车身壁板结构引起低频振动使车腔内产生结构噪声,影响驾驶员的乘坐舒适
高速铁路追踪间隔时间是高速铁路列车运行管理的重要指标,是影响高速铁路通过能力的重要参数。目前我国运营中的大部分高速铁路,普遍将5分钟作为最小的追踪间隔时间。随着社会运输需求的增加,许多线路的能力利用接近饱和,迫切需要研究压缩其至3分钟或4分钟的可行性。实际上,我国很多高速铁路是以3分钟的最小追踪间隔时间为设计标准的。然而在运营过程中发现,当列车以3分钟间隔时间追踪运行时,会出现无法发挥额定功率导致
焊缝缺陷识别领域中,主要使用人工查看焊缝透照图的方式进行缺陷鉴别。这种传统的方式不仅低效而且准确率低。现今传统机器学习方法很难对非固定形状或难以移动的焊接成果进行缺陷判定,所以需要一套合适的流程来实现此类焊缝的缺陷检测工作。本文收集了包含13006个焊缝的数字化X射线图像作为卷积神经网络的原始图像。由于样本缺陷类别分布不均,并且原图像信噪比过低,所以使用缺陷位置和非缺陷位置切割的方法进一步标注原图
由于人类活动具有非马尔可夫性,并且人类活动背景日趋复杂,为了确保人们的安全,人们在很多地方都安装摄像头,但是仅仅通过摄像头只能起到监控作用,并不能完全避免危险的发生。近年来,学者们提出的人类活动分层表示模型,为人类活动预测和危险预警提供了新思路。本文以精确的目标跟踪检测方法为基础,通过构建不同场景下的人类活动表示模型来进行活动预测,而且活动预测可以让人们提前预防危险,在人们的生活中意义重大。在本文
论文以鄂尔多斯盆地东部绥德-吴堡地区山西组山1段致密砂岩储层为研究对象,运用矿物岩石学、岩石力学、地球物理测井等学科的理论和方法,系统开展了目标区山1段砂岩储层的物质组成、结构、岩石力学及脆性等特征研究。基于岩石力学实验和测井资料分析进行动、静态岩石力学参数的转换,建立了基于岩石力学参数的单井脆性连续性评价模型,并探讨了储层脆性的影响因素,为研究区储层的可压裂性评价和压裂段的优选提供基础资料。通过
目的:安息香中分离提纯的齐墩果酸(Oleanolic acid)化合物体内外抗HSV-1活性,以及抗病毒机制的探究,为开发新型抗HSV-1药物奠定理论基础。方法:通过CCK8实验法在不同细胞上检测了Oleanolic acid毒性,利用空斑减数实验、病毒基因组DNA拷贝数、病毒滴度等方法检测了Oleanolic acid抗HSV-1活性,通过不同时间点加药探究了Oleanolic acid作用阶段