关于平面图的全染色的几个结果

来源 :山东科技大学 | 被引量 : 0次 | 上传用户:redredlove
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对图论的研究已经有二百多年的历史,最早关于图论的文章是在1736年由欧拉完成的,该文章解决了著名的哥尼斯城堡七桥问题.自20世纪六十年代以来,图论得到了迅猛发展,图论方面的结果大量涌现,其中图的染色理论在图论研究中占有重要的地位,图的染色理论在最优化、计算机理论、网络设计等方面有着重要的应用.本文旨在讨论平面图的全染色.  本文讨论的图均为简单无向有限的平面图.对于一个图G=G(V(G),E(G),ψG),V(G),E(G)分别表示其顶点集合和边的集合,ψG为点和边的关联函数.对于顶点v∈V(G),我们用d(v)表示其度数,△(G)和δ(G)分别表示G中顶点的最大度和最小度,简记为△和δ.在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G),E(G),v(G),ε(G).  若图G可以表示在平面上,并且任两条边仅在其端点处才可能相交,则称G是可平面图.图G的这种平面上的表示方法称为G的一个平面嵌入,或称平面图.一个平面图G把平面划分为若干个连通区域,这些区域的闭包称为G的面,图G所有的面构成的集合记为F.一个面f∈F所关联的边的个数(割边计算两次)称为面f的度,用d(f)或r(f)表示.若G的两个面有一条公共边,则称这两个面相邻.如果G是连通的平面图,则有|V|-|E|+|F|=2(Euler公式).  根据一定的规则将一组目标划分为不同的种类,这是数学中的一个基本方法.不同的规则决定着该组中任意一对目标是否在同一类中.图的染色理论就是研究这类问题的一门理论,它有着相当广泛的应用背景.各种形式的日程表问题、时间表问题以及排序问题,从根本上来说都可以归结为染色问题.  图G的全k染色是指至多用k种颜色,对G的顶点和边同时染色,使得相邻的两个元素(点和点,边和边,点和边)染以不同的颜色.图G的全色数xT(G)是指G的全k染色中最小的正整数.如果一个图G的全色数xT(G)=△(G)+1,则称G为第一类图.对于G的全色数xT(G),已有的结果可以总结为:  (1)对△(G)≠6的平面图,有xT(G)≤△(G)+2;  (2)对△(G)≥9的平面图,有xT(G)=△(G)+1.  本文对平面图的全染色进行了讨论.全文共分三章.第一章介绍了图论中的一些基本概念,综述了当前全染色理论的主要研究成果和本文的一些主要结果.第二章我们考虑最大度较小的平面图的全染色.Behzad和Vizing分别对全染色进行了研究,提出了下面的猜想:  猜想 对任意图G,都有△(G)+1≤xT(G)≤△(G)+2.该猜想被称为全染色猜想.  本章的主要结论为:  如果平面图G的最大度△(G)≥5,并且G既不含4-圈也不含5-圈,则xT(G)=△(G)+1.  第三章中提出了图的最优全染色与强度的定义,并得到了几类平面图的全染色和与强度.
其他文献
关于偏微分方程的最优控制问题已有大量的工作,目前,已经有很多数值方法可以用来解决最优控制问题.在现有的文献中,大多是采用标准有限元来研究最优控制问题,而关于混合有限
本文第1章简单地介绍了线性多层规划的起源及其发展历史.并着重介绍了线性多层规划问题模型的结构,以及现有的针对线性多层规划问题算法已有的成果。  第2章给出了研究本文
关于偏微分方程类型的最优控制问题,众多学者已经做了大量研究。目前,很多数值方法可用来求解最优控制问题,而有限元方法则是最为重要的数值方法之一,其应用也极为广泛。  
设f1,f2,f3都是次数大于1的有理函数和R={f1,f2,…,fm},其中fi(i=1,2,…,m)是如下形式的有理函数:  fi=zli+2+aili+1zli+1+···+ai1z+ai0/bikizki+···+bi1z+bi0=Qi/Pi
物理等学科领域中许多数学模型、系统和过程的模拟都是基于用分数发展方程来描述的,这很自然地导致了对分数发展方程的研究.近年来,分数发展方程的理论取得了长足的发展,获得
本文考虑流体耦合颗粒的系统.颗粒用Smoluchowski方程描述,流体用不可压的Navier-Stokes方程来描述.流体受到颗粒产生的压力,流体带颗粒一起运动并使颗粒发生形变.由于颗粒的