《关于若干特殊图的限制染色》由会员分享，可在线阅读，更多相关《关于若干特殊图的限制染色（29页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学 硕士学位论文 关于若干特殊图的限制染色 姓名：张志芳 申请学位级别：硕士 专业：应用数学 指导教师：徐常青 2010-12 河北工业大学硕士学位论文 关于若干特殊图的限制染色 摘要 = ( (),()是简单图， 给定非负整数， 图的-(,1)-全 标号是一个映射 : () () 0,1,，使得：对任意两个 相邻顶点，有() = ()；对任意两条相邻的边，有 () = ()；对任意一对关联的点和边 ()， ()，有 ()() . (,1)-全标号的跨度是指两个标号差的最大值， 图 的(,1)-全标号的最小跨度叫图的(,1)-全标号数， 记作 (). 针 对两类直积图 和 研究了(,
2、1)-全标号问题，完全 确定了其(,1)-全标号数.另外得到了偶完全图2的带限制条件的 ,1-染色， 其中 2且 + 2. 关键字：直积图， 偶完全图，(,1)-全标号，(,1)-全标号数，,-染 色，,-色数 i 关于若干特殊图的限制染色 ON RESTRICTED COLORING PROBLEMS OF SOME SPECIAL GRAPHS ABSTRACT A (,1)-total labelling of a graph is a function from ( (),() to the set 0,1, such that () = () if and are two adjac
3、ent vertices, () = () if and are two adjacent edges, and () () if an edge is incident to a vertex . The span of a (,1)-total labelling is the maximum diff erence between two labels. The mimimum span of a (,1)-total labelling of is called the (,1)-total number and denoted by (). For the direct produc
4、t graphs and , we completely determine their (,1)-total number. We also obtain the ,1- chromatic number of even complete graph, where 2 and + 2. KEY WORDS: direct product graph, even complete graph, ,1-total labelling, ,1-total number, ,-coloring, ,-chromatic number ii 关于若干特殊图的限制染色 符号说明 1. ()图的顶点集.
5、2. ()图的边集. 3. ()图的顶点数. 4. ()图的边数. 5. ()顶点的度. 6. (G)图的最大度. 7. (G)图的最小度. 8. 顶点集 的导出子图. 9. = 图和同构. 10. 图是的子图. 11. (, )二部图的二分类. 12. ,完全二部图. 13. 完全图. 14. 直积图. 15. ()图的点色数. 16. ()图的边色数. 17. ()图的全色数. 18. ()图 的(,1)-全标号数. 19. ,()图的,-色数. 20. ()的邻居. 21. ()与顶点关联的所有边组成的集合. 22. ()与顶点关联的所有边的标号的集合. 23. -点标号为的顶点. 24
6、. -边标号为的边. 25. ,整数集合, + 1,. 26. : ,与-点关联的边的可用标号集为,. iv 河北工业大学硕士学位论文 第一章 绪论 图论是离散数学中非常活跃的分支之一， 以图为研究对象.虽然它是一门非常年轻的学 科，但是成熟非常快，可以在诸多科学领域像计算机科学、化学、物理、战略学等学科中应 用.自1736年，Euler解决了著名的柯尼斯堡七桥问题并从中引出 “图” 的概念， 从此诞生 了一个全新的数学分支图论. 20世纪60年代以来，图论飞速发展，许多伟大的数学家 为此做出了重大贡献， 并取得了丰硕的成果.图的染色理论是图论研究领域中的一个重要分 支，源于150年前的“四色
7、猜想” ，在最优化、计算机理论、网络设计等方面有着重要的应 用(见文献1-3). 1-1图的染色背景 图论的染色理论源于著名的 “四色猜想” ， 是图论研究的一个热点. 19世纪中叶，Francis Guthrie提出用四种颜色就可以对任意一张地图进行染色的猜想.这个猜想指出平面上任何 一张地图都可以只用四种颜色给各个国家染色，使得任何两个有共同边界的国家染不同的 颜色.“四色猜想” 提出后， 一些数学家力图给出严格的证明， 但是一直没有成功.直到1976 年美国以利诺大学数学家Appel和Haken借助计算机，花了1200个小时，才证明了“四 色猜想”的正确性， 使得“四色猜想”成为“四色定
8、理”(见文献4-5).但是数学家们仍期待 用更简洁的数学方法证明“四色定理”.“四色定理”成为数学家们感兴趣而一直未能用常 规数学方法解决的世界数学难题之一， 推动着图染色理论的发展. 本质上，图的染色是根据特定的规则对给定图的元素(顶点、边、面)的一种划分，通常 把划分过程看成是给每一个元素分配一种颜色的过程.任意图的染色问题都包含三个要素： 需要染色的元素， 加在颜色上的限制和加在划分上的限制.各个要素或要素之间的组合不同， 可以得到不同的染色问题，如点染色、边染色、全染色及其它许多染色问题.图的染色理论 在现实生活中有着广泛的应用， 渐渐成为众学者研究的重要领域， 已经得到了许多有趣而实
9、 用的结果， 并拓展出许多新的染色分支. 在图的染色问题中，最早出现的是面染色，随后出现了点染色和边染色，这是最古典 的染色问题. Behzad6及Vizing7在1965年又引入了全染色概念，由此点染色、边染色、 全染色成为图染色问题的三大经典染色.随着对染色问题的深入研究，又提出了许多新的 染色问题，如列表染色(见文献8)、均匀染色(见文献9)、圈染色(见文献10)、强染色(见 文献11)、邻点可区别全染色(见文献12)、哈密顿染色(见文献13-14)、距离标号(见文 献15-16)、,-染色(见文献17)等. 1 关于若干特殊图的限制染色 图染色理论有着非常广泛的应用， 生活及科学领域中
10、许多问题都可以转化为图的染色问 题.用图的形式建立这些问题的数学模型，然后对图中的对象按一定规则进行划分，染色只 是对其中划分方法的一种简单直观的表达方式.因此可以用染色理论解决最优安排问题、 排 课表问题、 收款台设置问题、 运输方案设计、 储藏问题和网络设计等诸多问题(见文献1-3). 1-2图的基本定义及经典染色的基本知识 本节介绍图的一些基本定义及三种经典染色的基本知识， 以便后面各章的应用. 定义1.2.118图是一个有序三元组( (),(),()，其中 ()是有限非空 顶点集，()是与 ()不相交的有限边集，()是关联函数， 它使的每条边对应 的无序顶点对(不必相异)， 若是一条边
11、， 而和是使() = 的顶点， 则称连接 和，和称为的端点. 的顶点数和边数分别记为()和(). 定义1.2.218一条边的端点称为与这条边关联， 反之亦然.与同一条边关联的两个顶点 称为是相邻的，与同一个顶点关联的两条边也称为相邻的.邻接到的所有顶点称为的 邻居， 记作(). 定义1.2.318图中与顶点关联的边的数目叫做顶点的度，记为().图 的最小度和最大度分别记为() = () : ()和() = () : (). 定义1.2.418端点重合为一点的边称为环， 端点不相同的边称为连杆. 定义1.2.518如果一个图的顶点集和边集都是有限的， 称为有限图.只有一个顶点的图 称为平凡图，
12、其他所有的图都称为非平凡图.既没有环也没有两条连杆连接同一对顶点的图 称为简单图. 定义1.2.618每一对不同的顶点都有一条边相连的简单图称为完全图. 个顶点的完 全图记为. 定义1.2.718二部图是指它的顶点集可以分为两个非空子集和，使每条边的 一个端点在中，另一个端点在中，这种分类(, )称为图的一个二分类.完全二 部图是具有二分类(, )的简单图，其中的每个顶点都与的每个顶点相连，若 = ， = ， 则这样的完全二部图记为,. 2 河北工业大学硕士学位论文 定义1.2.818如果对所有的 ()， 都有() = ， 则称图是正则的. 定义1.2.918若 () ()，() ()， 则称
13、图是的子图.若是 的子图且 () = ()，则称为的生成子图.如果 是的一个非空子集，以 为顶点集， 以的两个端点都在 中的边为边集所组成的图， 称为的由 导出的 子图， 记作 . 在不产生混淆的情况下，我们把()，()，()分别简记为()，.本文所 用术语和符号与文献18一致， 因此对于未定义的术语请参阅文献18.下面给出经典染色 点染色、 边染色和全染色的概念及基本知识. 定义1.2.1018设 = ( (),()，且设0,1,., 1是一个颜色集合，若 是一个从 ()到0,1,.,1的映射， 即 : () 0,1,.,1， 则称是 的一个-顶点染色，简称-染色.若任意相邻的顶点1,2 ()，都有(1) = (
