补倍图的染色

【www.zhangdahai.com--其他范文】

摘要：补倍图的概念是由张忠辅教授在文献Zhang Zhongfu,Qiu pengxiang,Zhang donghan and Bian liang.The doule graph and complement double graph of graph.数学进展,2008,37（9）,303-310.中提出的概念,在计算机科学数据库的关系中有着较好的应用.设是一个简单图,若， 且 ,

我们称为 的补倍图,其中 为的拷贝.

本文对路的补倍图的点染色和边染色问题进行了讨论,分别给出了路的补倍图的点色数和边色数.

关键词：路 补倍图 点染色 边染色

第1章 绪论

1.1补倍图染色的研究背景及研究现状

图论是离散数学的重要组成部分,是近代应用数学的重要分支.人们常称1736年时图论历史元年,因为在这一年瑞士数学家欧拉（Euler）发表了图论的首篇论文——《哥尼斯堡七桥问题无解》,所以人们普遍认为欧拉是图论的创始人.1936年,匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《有限图与无限图理论》,这是图论史上的重要里程碑,它标志着图论将进入突飞猛进发展的新阶段.进40年来,随着计算机科学的发展,图论更以惊人的速度向前发展,有人形容说:真是异军突起,活跃非凡.其主要原因有二:其一,计算机科学的发展为图论的发展提供了计算机工具;其二,现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系,从而推动科学技术不断地攀登新的高峰.作为描述事物之间关系的手段和工具,目前,图论问题在许多领域诸如,计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到了广泛应用.图论中所讨论的"图"是有结点和带方向或不带方向的弧线连接而成的线状图,不是直线、圆、椭圆、曲线等在微积分、解析几何、几何学中讨论的图.例如,点可以表示人,连线表示一对朋友;或者用点表示通讯站,而连线表示通讯路线.在这类图形中,人们主要感兴趣的是给定两点是否有一条线连结,而不考虑点的位置及连线的长短曲直.这类事例的数学抽象,就产生了图的概念.

染色问题是图论的重要内容,图的着色问题的研究起源于四色猜想,四色猜想的提出来自英国。1852年,毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:"看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家着上不同的颜色."这个结论能不能从数学上加以严格证明呢?弗南西斯·格思里和他的弟弟经过研究始终未能得出结论,后来直到1865年哈密尔顿逝世为止,问题也没有能够解决。1872年,英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878-1880年两年间,著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布证明了四色定理,大家都认为四色猜想从此也就解决了。11年后,即1890年,数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久,泰勒的证明也被人们否定了。后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。进入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行.美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国.1960年,有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。电子计算机问世以后,由于演算速度迅速提高,加之人机对话的出现,大大加快了对四色猜想证明的进程。1976年,在J. Koch的算法的支持下,美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明。四色猜想的计算机证明,轰动了世界,当时中国科学家也有在研究这原理。它不仅解决了一个历时100多年的难题,而且有可能成为数学史上一系列新思维的起点。四色猜想问题得到证明后人们将染色问题开始进行推广。日程表安排问题便可抽象为图的染色理论。

例如:（日程表与图的着色问题）

假设要安排参议院的会议日程表,如果两个委员会有相同成员,则不能将这两个委员会的会议安排在同一时间.我们需要多少个不同的时间段呢?将这样一个安排日程表的问题,我们可以引申为图的着色问题.我们为每个委员会构造一个顶点,如果两个委员会有相同的成员,则相应的两个顶点是相邻的,我们要给这些顶点分配标记（时间段）使得每条边的端点都有不同的标记,

如图1.1-1

有三个独立集,我们可以给每一个独立集分配一个标记,图中的所有成员必须被分配不同的标记,故这个例子至少需要3个时间段.

因为我们只对顶点集的划分感兴趣且标记没有数值意义,因此将他们称为颜色会更方便,于是有了点染色的问题．随着研究的深入与发展之后就有了点染色,边染色,全染色和邻点可区别的全染色问题.

补倍图是是张忠辅教授在数学进展中提出的概念,在计算机科学数据库的关系中有着较好的应用.本文主要进行补倍图的点染色和边染色的研究.

1.2基本概念及符号说明

定义1 一个无向图是一个有序的二元数组〈V,E〉,记作G,其中,

⑴V≠φ称为顶点集,其元素称为顶点或结点.

⑵E称为边集,它是无序积V＆V的多重子集,其元素称为无向边,简称边.

定义2 在无向图中,关联一对顶点的无向边如果多于一条,则称这些边为平行边,平行边的条数称为重数.即不含平行边也不含环的图称为简单图.

定义3 对无环图G的每个顶点涂上一种颜色,使相邻的顶点涂不同的颜色,称为对图G的一种着色.若能用K种颜色给G的顶点着色，就称对G进行了K着色,也称G是K—可着色的.若G是K—可着色的,但不是（k-1）—可着色的,就称G是K色图,并称这样的K为G的色数,记作X（G）=k,不混淆时,色数X（G）也可记作x.

定义4 对图G的每条边涂上一种颜色,使相邻的边涂不同颜色,称为对图G边的一种着色.若能用k种颜色给G的边着色,就称G是k—边可着色的.若G是k—边可着色的,但不是（k-1）—边可着色的,就称k是G的边色数,记作X’=k.

定义5 设G(V,E)是一个简单图,若

,我们称 为 的补倍图,其中 为 的拷贝.

引理1 若C2k为2k阶偶圈，则 ，

其中k为正整数.

引理2 若图G为简单图，则 是正则图.

第2章 补倍图的染色问题

2.1路的补倍图的点染色

定理1 设 为n阶路,则

证明 分三种情况

情况1：当n=3时

显然为6阶偶图,由引理1可知， 是2-可着色的，即，图2.1-1给出了 的2-点染色．

图 2.1-1

情况2：当n=4时

令 为 的同构图.首先 ，用对 的点依次循环着色，由定义5， 的顶点中， 与 ， 邻接，因此 不能着 .故可用 给 着色.同理可用 给 着色，由 与 不邻接，而与 邻接， 与 ， 邻接知 不能着

，因此可用 给 着色，

由上述方法可知， 是3-可着色的，即，图2.1-2给出了 的3-点染色．

图2.1-2

情况3：

证毕

图2.1-3 图2.1-4

2.2路的补倍图的边染色

定理2 设Pn为n阶路，则

证明 由于 的每个顶点的度数

故给 作点染色时至少需要n-1种颜色，即

为证明，只需给出 的一个点染色的方案，使 可以用n-1种颜色染完即可.

设映射 满足

情况1：当时

情况2：当时

证毕

结论

本文讨论了路的补倍图的点染色和边染色问题,得出以下主要结果：

定理1 设Pn为n阶路,则

定理2 设Pn为n阶路，则

以上两个定理给出了路的补倍图的点色数和边色数，以上结论均在本文中给出了证明.在讨论路的补倍图的点染色和边染色问题的过程出，本人提出以下两个猜想：

1.路的补倍图的全染色

定理3 设Pn为n阶路,则

2. 路的补倍图的邻边可区别的全染色

定理4 设Pn为n阶路,则

参考文献:

[1]张忠辅,仇鹏翔,张东翰,卞量,李敬文,张婷.图的倍图与补倍图(英文)[J].数学进展. 2008.7 03期

[2]刘永平,张忠辅,谢继国,苏旺辉.路和圈的倍图的邻点可区别全染色[J].甘肃高师学报.2007.(02)

[3]苏旺辉,刘永平,谢继国,张忠辅.完全图的倍图的邻点可区别全染色[J].兰州理工大学学报.2008.(03)

[4]安常省，冯旭霞.几类特殊图的补倍图的点色数[J].天水师范学报.2008.3.02期

[5]刘永平,刘玉胜.离散数学[M].第一版.兵器工业出版社.2006.12

[6]王树禾.图论[M]. 第一版.高等教育出版社.2004

[7]（美）（韦斯特）DouglasWest;李建中,骆吉洲（美）（韦斯特）DouglasB.West著;李建中,骆吉洲译.图论导引[M].第一版.机械工业出版社,2006.02

[8]刘缵武.应用图论[M]. 第二版.国防科技大学出版社,2006.01

[9]张先迪，李正良.图论及其应用[M].北京:高等教育出版社，2005

推荐访问:染色 补倍图