Welch-Powell图的点染色在现实生活中的应用(2)
时间:2018-03-16 20:25 来源:毕业论文 作者:毕业论文 点击:次
染色理论是图论发展的重要分支之一。它起源于著名的“四色猜想”，就是在一个平面或球面上的任何地图总可以用至多四种颜色给每一个国家染色，使得没有两个相邻的国家染有相同的颜色。 经过四年的应用数学的本科教育，我了解到生活及科学领域中许多问题都可以由数学模型来建立，然而以图的形式来建立数学模型近年来更是推陈出新，它对图中某些对象按照一定规则进行分类，而染色正是对这些分类方法的一种直观的表现。所以染色问题是解决诸如时间表问题、排序问题、交通状态、运输安排、电路设计和贮藏问题等涉及任务分配的实际问题的基本方法[3]。 1.2 国内外的研究现状与发展 1.3 文中符号说明 1. [6]: 定义图 为一个有序对 2. [6]: 完全图 3. [6]: (顶)点集 4. [6]: 边集 5. [6]: 图 的色数 6. [6]: 图 的最大度 7. [6]: 图 的最小度 8. [6]: 度序列 9. [6]: 顶点的度 10. [6]: 图 的独立数 1.4 基本概念 图[7]：一个图是一个有序二元组 ，其中 是一个有限集合，称为 的顶点集合，其元素称为顶点; 是 元素的无序对的集合，称为 的边集合，其元素称为边。为方便起见，我们通常分用以 和 分别表示图 的顶点集合和边集合， 和 分别表示图 的顶点数和边数。若 和 都是有限的，则称图 是有限图，否则称为无限图。若 ，则称图 为 阶图。 完全图[7]：每两个各不同顶点之间都有一条边相连的简单图称为完全图。 导出子图[7]：若 且 包含了 中所有满足 的边 ，则称 是 的导出子图。 邻接矩阵[8]：有 个顶点的图 的邻接矩阵 是一个 矩阵，其中如果 邻接 则 ，否则 。 独立集[8]：一个图的点独立集(简称独立集)是指图中一些互不相邻的点构成的点子集。图 中含点数最多的独立集称为 的最大独立集。最大独立集所含的顶点数称为独立数，记为 ，简记为 。 二、与点染色相关的定义及定理 2.1 相关定义 定义1[4] 图 的一个正常 染色是指 种颜色 到 的各顶点的一个分配，使任意两个相邻点有不同的颜色。 定义2[4] 若 有正常 顶点染色，则称 是 顶点可染色的，给 进行正常染色所需要的最少颜色数称为 的色数，记为 。若 ，则称 为 色图。 定义3[4] 给定图 的一个 染色，用 表示 中染以第 色的顶点集合 ，则每个 都是 的独立集，因而 的一个 染色对应 的一个划分 ，其中每个 是独立集。反之，给出 的这样一个划分 ，其中每个 均是独立集 ，则相应的得到 的一个 染色，我们称 的这样一个划分为 的一个色划分。每个 称为色类 。因此 的色数 就是使这种划分成为可能的最小自然数 。 定义4[4] 设定图 是 染色图，若对 的所有 染色导出的关于 的划分均相同，则称 为唯一 可染色图，简称唯一可染色图。 (责任编辑：qin) |