特殊图类的彩虹点染色毕业论文(编辑修改稿)

特殊图类的彩虹点染色毕业论文(编辑修改稿)内容摘要：

G, AC。 A7: GT, MA, LA。 A8: LA,GT, S。 A9: AC, S, LA。 A10： GT， S。 建立如下图所示的模型，把课程看作为图 G 的顶点，两顶点之间的连线当且仅当有某个学生同时选了这两门课程。 图 2 如果我们用相同的颜色给同一时段进行的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。 储藏问题 一家公司制造 n 种化学制品 nCCC ,......, 21 ，其中某些制品是互不相容的，如果它们互相接触，则会 引起爆炸，作为一种预防措施，公司希望把它的仓库分为间隔，以便把不相容的化学制品储藏在不同的间隔里，试问：这个仓库至少应该分成几个间隔。 问题处理：构造一个图 G ，其顶点集是 },......,{ 21 nvvv 两个顶点 iv 和 jv 相连当且仅党化学制品 iC 和 jC 互不相容，则仓库的最小间隔数即为 G 的顶点数。 4 彩虹染色方面的著名定理 四色与五色定理 四色定理 如果在 平面 上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不 相同 ；另一个通俗的说法是：每个 地图都可以用 少 于四种 的 颜色 来染色，而且没有两个邻接区域的颜色相同。 邻接 的 两个区域 指 的 是 它们有一段公共的边界，而不仅仅是一个公共的交点。 1852 年，刚毕业于伦敦大学的格斯里 (1831— 1899)发现：给一张平面地图正常着色，至少需要 4 种颜色。 这就是著名的 4色定理。 当这个定理被提出后，很多科学家都希望能对此进行证明，但都没有成功。 也有一些证明当时被确立后来又被推翻，经过了各种专家学者的一个多世纪的研究和证明，直到 1976 年才由两位美国数学家通过电子计算机得以完全的证明。 但这个证明一直受到一些数学家的质疑，因为直到现在都没有数学家不借助计算机能够证明。 五色定理 把一个平面分成若干的区域，给这些区域进行染色，并使任意相邻的区域染上不同的染色，满足这些条件所需的颜色数最多为五种。 五色定理 稍弱于 比 四色定理 ，但是 它证明起来就容易多了。 1879 年，阿尔弗雷德布雷肯普给出了四色定理的一个证明 方法 ， 被当时的人们所接受 ，但 11 年后，珀西约翰希伍德却 发现了这个证明中存在了一些错误 ，他 对 肯普的证明加以修改， 就 得到了现在的 五色定理。 我们对图的顶点作数学归纳证明。 当 1n 时，结论显然。 设 kn 时，结论成立。 考虑 1kn 的平面图 G。 因 G 是平面图，所以 5)( G。 设 5)()(  Gud  ，令 uGG 1。 由归纳假设， 1G 是可用 5种颜色正常顶点染色的。 设 c是 1G 的 5着色方案。 (1) 如果 5)()(  Gud  , 显然 c 可以扩充为 G 的 5 正常顶点染色； (2) 如果 5)()(  Gud  , 分两种情况讨论。 情形 1 在 c下，如果在与 u 相邻接点中，至少有两个顶点着相同颜色，则容易知道， c 可以扩充为 G 的 5 正常顶点着色； 情形 2 在 c 下，设在与 u 的相邻接点中， 5个顶点着了 5种不同颜色。 图 3 贪心（ greedy）着色法 用色 1， 2，…逐步（按某一顶点排序）对每个顶点进行正常着色，每次选用尽可能少的颜色进行着色。 例如，对任意图 G ，按任一顺序进行贪心着色，则每当尝试对某一顶点 v 着色时，其邻集 )(vN 中至多出现 )(an 种色，因此总可从 1n种颜色中挑选一中着在 v 上。 整个着色过程至多用 1n 种颜色，故 G 为 )1(n 可着色的。 从而得到推论。 显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。 假如我们事先知道图 G 的一个 n 着色为 ),......,( 21 xVVVC 。 按 ),......,( 21 xVVV 的顺序任作一顶点排序（同一色集 iV 内随意排序），按此顺序进行贪心着色，显然恰好使用了 x 种颜色。 因此，设法构想一适当的顶点排序进 行贪心着色，往往可能得到一个较好的着色结果（如 Brooks 定理之证明）。 5 特殊图类的彩虹点染色 广义  图的彩虹点染色 广义  图的介绍 在讨论广义  图之前，我们先来了解几个定义。 首先是彩虹 k 连通，如果一条路的边分别染不同的颜色，那么这条边染色路就是一条彩虹路。 如果图 G 中任意两个顶点之间是连通的，并且由 k 条内部顶点不相交的彩虹路连通，那么边染色图 G 就是彩虹 k 连通的，其中 Nk。 接下来，我们给 出彩虹 k 连通数)(Grck 的定义：若存在图 G 的一个边染色，使用 t 种颜色就能够使得图 G 彩虹 k连通，其中 t 是最小的整数，那么彩虹 k 连通数为： tGrck )(。 对于 1 连通图的彩虹连通数，记作 )(Grc ，即 )()( 1 GrcGrc 。 本文的概念定义部分介绍了，一个图 G 是 k 连通的，当且仅当任意两个顶点之间是连通的，并且由 k 条内部顶点不相交的路径连通。 因此，前面定义的 )(Grck 仅仅是针对 k 连通图而言的。 我们继续说明 )(Grck ，对于 1k ， Caro 等人证明了，如果图 G 的阶数为 n ，那么 32)( nGrc  ，如果图 G 是 2 连通的，即 2k ，那么 )(2)( nOnGrc 。 Chandran 等人证明了，如果图 G 的最小度为  ，那么 313)(   nGrc ，并且证明了对于所有阶数为 n ，最小度为  的连通图 G 都是适用的。 因此，如果图 G 是l 连通的，那么 313)(  l nGrc。 另外，上文有说明图 G 是 3 连通的，即 3k ，可以采用改善后的界，即 5 )1(3)(  nGrc。 首先，了解 l 连通 图： 定理 1 如果 G 是一个 l 连通图， 2l ，顶点 1ln ，那么 l nlGrc )1()(2 。 在情况 2l 中，如果图 G 是一个 2 连通串并联图是一个简单图，从三个顶点 3K开始，反复运用一个操作序列，这个序列是一个分支，由一条边变换成双条边，反复增加分支边。 那么这样的 2 连通图就是一个著名的亚族。 证明定理 1，我们是通过先证明一个强有力的定理 4 的结论，然后间接证明定理 1。 定理 2 如果 G 是一个 l 连通图， 2l ，顶点 1ln ，那么存在图 G 的一个边染色，至多是 l nl )1(  种颜色满足以下结论： )1( 对于任意两个顶点 )(, GVvu  ，这里存在两条不相交的彩虹 vu 路； )2( 对于任意一个顶点 )(GVu ，任意集合 )(GVX ，且 2X ，这里两条彩虹 Xu 路，只有顶点 u 相同； )3( 对于任意两个集合 )(, GVYX  ，且 2, YX ，这里的两条彩虹 YX 路不相交。 对于 )2( 而言，如果 Xu ，那么其中的一条路径取自顶点 u。 类似的，对于 )3( ，如果 X 和 Y 相交，那么一条适合的路径是一个点，这点在 YX 中。 显然，定理 1是来自定理 4 ，所以先证明定理 4 ，证明之前先给出一个定理 5。 定理 3 )( 定理Fan 令 G 是一个 k 连通图。 对于任意的顶点 )(GVu 和任意集合)( uGVX  ， kX ，这里有从 u 到 X 的 k 条路径，使得对于其中的任意两条路，仅仅只有一个共同顶点 u。 定理 4 ，证明：首先定义图 G 的一些子图 GHHH t  10 ，其中 0t ，)()( GVHV t 。 因为任意的 l 连通图都含有一个顶点至少是 l 的圈，于是令 0H 是图 G 的一个顶点至少是 l 的圈。 现在，假设找到这样一些图 10 , iHH  ， 1i ，如果 )()( 1 GVHV i  ，那么集合 ti HH 1 ，否则的话，这里存在一个顶 点)( )( 1 ii HV GVv。 根据定理 3， iv 发出 l 路到 1iH ，这里的每对路径仅仅汇集与 iv ，那些 l 路是 lK,1 的一个细分。 令 iH 是一些 l 路 1iH 的集合。 重复这个过程，直到结束。 对于每个 i ， ti0 ，归纳证明了，存在一个 iH 的边染色，至多使用l HVl i)()1(  种颜色，使得定理 4 中的 )1( 到 )3( 的性质成立，这里使用 iH 代替 G。 那么，集合 ti 就意味着对于 G 而言定理 4 成立。 接下来，先对每个 iH 定义一个边染色。 显然， 0H 是一个圈，它是彩虹染色的。 假设 1iH 有一个边染色，颜色是 色，色， m1 ，其中 ti1。 通过附加一个细分的 lK,1 到 1iH 得到图 iH ，其中 l 条路径汇集于顶点 iv。 假设路径是 l ,1 ，1)()( 1  lQeQe 。 对于 2l 的 情 况 ， 可 以 假 设 1)()( 21  QeQe。 令lF 1 ， )( 1 ij HV 是路劲 jQ 的另一个端点，其中 lj1。 分别把 jQ的第一条边和最后一条边射入到 iv 和 j。 情况 1： 12)(1  lFVl ， lFVQe  )()( 1 ，。