（系统分析与集成专业论文）极大平面图的构造方法与几类特殊图的色数分析.pdf

亩塞篮星工程盔生亟生i 坚监塞 中文摘要 图论是离散数学的重要分支之一。着色问题是图论中研究较早的领域，也 是图论的重要研究内容，最近几年来一直是图论研究中的热点问题，但至今着 色问题仍是数学中未解决的难题之一。由于还未找到求图色数的有效算法，甚 至还未找到有较好性能比的有效近似算法，着色理论的应用受到了很大的限制， 这有待于我们去进一步的研究。 本文首先简单介绍了目前国内外关于图的着色问题的研究现状以及研究意 义。其次，通过研究极大平面图的构成原理，给出了构造极大平面图的加点法， 并证明了这种方法的可靠性。接着，本文给出了简单连通图的色数不大于2 的 充要条件。接下来，本文证明了任意一个简单平面图都是某个极大平面图的生 成子图，则任意一个简单平面图色数的上界是相应的极大平面图的色数。接着， 本文证明了顶点度都为偶数的极大平面图的色数为3 。最后，本文在证明极大 平面图都可以5 一着色的基础上，用数学归纳法证明了部分加点法产生的极大平 面图是可以4 着色的，并对其余的极大平面图提出了一个猜想，若这个猜想成 立，则可以证明极大平面图都可以4 着色，进而证明四色定理。 关键词：图论，色数，平面图，简单连通图，四色定理 直立盏盅工程盍堂塑生些途塞 a b s t r a c t g r a p ht h e o r yi s o n eo ft h ei m p o r t a n tc o m p o n e n t so fd i s c r e t em a t h e m a t i c s t h ec o l o rp r o b l e mi st h ee a r l ya n ds i g n i f i c a n tf i e l di ng r a p ht h e o r ya n di nt h e r e c e n t l yy e a r si ti sah o tp o i n ta l la l o n g , b u ti t h a sn o tb e e ns o l v e du n t i ln o w i t s a p p l i c a t i o n i sl i m i t e ds i n c et h ee f f e c t i v ea r i t h m e t i ce v e nt h eg o o da p p r o x i m a t e a r i t h m e t i cf o rt h ec h r o m a t i cn u m b e ro fag r a p hh a sn o tb e e nf o u n dt ot h i sd a y ，i t n e e d sf a r t h e rr e s e a r c h t h i sp a p e ri n t r o d u c e st h ec u r r e n ts i t u a t i o na n ds i g n i f i c a n c eo ft h er e s e a r c h0 1 3 t h ec o l o rp r o b l e ma ：【f i r s t a n dt h e na l la d d i n g - v e r t e xm e t h o di sp r e s e n t e df o rt h e p r o d u c t i o no f m a x i m a lp l a n eg r a p h st h r o u g has t u d yo n t h es t r u c t u r e so f t h e s eg r a p h s ， a n di tp r o v e sc r e d i b l e n e x tt h i sp a p e rs h o w st h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n o ft h a tt h ec h r o m a t i cn t t m b e ro fas i m p l ec o n n e c t e dg r a p hi sn o tm o r et h a n2 a f t e r w a r di ti sp r o v e dt h a tas i m p l ep l a n eg r a p hi sas p a n n i n gs u b g r a p ho fam a x i m a l p l a n eg r a p h , s ot h ec h r o m a t i cn u m b e rt o po fas i m p l ep l a n eg r a p hi st h ec h r o m a t i c n u m b e ro ft h ec o r r e l a t i v em a x i m a lp l a n eg r a p h s u b s e q u e n t l yi ti sr e v e a l e dt h a t3i s t h ec h r o m a t i cn u m b e ro fam a x i m a lp l a n eg r a p hi nw h i c ht h ed e g r e eo fe v e r yv e r t e x i sa ne v e nn u m b e r a tl a s t ，b a s e do nt h ep r o o fo ft h a te v e r ym a x i m a lp l a n eg r a p hi s 5 - c o l o r a b l e ，s o m em a x i m a lp l a n eg r a p h sw h i c ha r ep r o d u c e db yt h ef i r s ta n ds e c o n d m e a n so ft h ea d d i n g v e r t e xm e t h o dp r o v e4 - c o l o r a b l eb yt h em a t h e m a t i c si n d u c t i o n a n dac o n j e c t u r ei sg i v e nf o rt h eo t h e r s i ft h i sc o n j e c t u r eh o l d s ，e v e r ym a x i m a lp l a n e g r a p hc o u l db e4 - c o l o r a b l e ，a n du h e r i o r l yt h ef o u rc o l o r t h e o r e mw o u l db ep r o v e d k e y w o r d s ：g r a p ht h e o r y , c h r o m a t i cn u m b e r , p l a n eg r a p h , s i m p l ec o n n e c t e dg r a p h ， f o u rc o l o rt h e o r e m 学位论文独创性说明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除了引文外，所有实验、数据和有关材料均是真实的。 4 、本文除了引文和致谢的内容外，不包含其他人或其他机构已经发表或撰 写过的研究成果。 5 、其他同志对本研究所傲的贡献均己在论文中作了声明并表示了谢意。 作者签名：鱼1 盏 日期：丛i 矗。羔! 垫， 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规定、学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版； 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题 和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名：至9 鱼 日 期：2 1 1 & 上：卫! 疆峦培息工程盍坐亟生些硷塞 骨l j吾 图论( g r a p ht h e o i y ) 是离散数学的重要分支之一，目前已经广泛地应用于物理、化 学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、系统科学等自然与社 会科学几乎所有的学科领域。图论的产生和发展经历了两百多年，大体上可以划分为三个 阶段： 第一阶段是从1 7 3 6 年到1 9 世纪中叶，这时的圉论处于萌芽状态，多数问题是围绕着 游戏产生的。最具有代表性的是著名的瑞士数学家欧拉( le u l e r ) 于1 7 3 6 年发表的关于 哥尼斯堡七桥问题的论文，这篇论文被公认为图论历史上第一篇论文。 第二阶段从1 9 世纪中叶到1 9 3 6 年。这个时期中图论问题大量出现，如四色问题( 1 8 5 2 年) 和哈密顿( h a m i l t o n ) 问题( 1 8 5 6 年) ，同时出现了以图为工具去解决其他领域中一 些问题的成果。最有代表性的工作是基尔霍夫( k i r c h h o f f , 1 8 4 7 年) 和凯莱( c a y l e y ，1 8 5 7 年) 分别用树的概念去研究电网络和有机化合物的分子结构。1 9 3 6 年，匈牙利数学家柯尼 希写出了第一本图论专著有限图与无限图的理论。图论作为数学的一个新分支已基本形 成。 从1 9 3 6 年以后是第三阶段，由于生产管理、军事、交通运输、计算机和通讯网络等方 面许多离散性问题的出现，大大促进了图论的发展，图论被广泛地应用于物理、化学、计 算机科学、电子学、信息论、控制论、网络理论、管理科学、系统科学等自然与社会科学 几乎所有的学科领域。 着色问题是图论中研究较早的领域，也是图论的重要研究内容。四色猜想是着色理论 的主要冲击目标，众多数学家对四色问题绞尽脑汁。最具有代表性的工作是1 8 7 9 年肯普 ( k e m p e ) 提出的“构形”和“可约”性的概念、1 8 9 0 年赫伍德( h e a w o o d ) 证明了五色 定理以及1 9 7 6 年阿佩尔( a p p e l ) 、哈肯( h a k e n ) 与科赫( k o c h ) 用电子计算机证明了四 色猜想。 虽然已经用电子计算机证明了四色猜想使之成为四色定理，但很多人并不满足于计算 机取得的成就，他们仍然在寻找更简洁的从理论上证明四色定理的方法。 参考文献【9 】、【1 1 】、【1 3 、 1 4 】、 15 1 、【1 6 试图从理论上证明四色定理，但其证明均存 在漏洞。参考文献 1 2 】试图证明顶点度都为偶数的极大平面图的色数为3 ，但其证明也存在 漏洞。 本文的主要结论包括： 第一，通过研究极大平面图的构成原理，给出了构造极大平面图的加点法，并证明了 直峦篮盅工程太堂亟生些垃塞 这种方法的可靠性。 第二，给出了简单连通图的色数不大于2 的充要条件。 第三，证明了任意一个简单平面图都是某个极大平面图的生成子图，则任意一个简单 平面图色数的上界是相应的极大平面图的色数。 第四，证明了顶点度都为偶数的极大平面图扮色数为3 。 第五，在证明极大平面图都可以5 着色的基础上，用数学归纳法证明了部分加点法产 生的极大平面图是可以4 着色的，并对其余的极大平面图提出了一个猜想，若这个猜想成 立。则可以证明极大平面图都可以4 着色，进而证明四色定理。 图的着色i a - j 题的研究具有相当重要的现实意义，最近几年来一直是图论研究中的热点 问题，但至今着色问题仍是数学中来解决的难题之一。由于还未找到求图色数的有效算法， 甚至还未找到有较好性能比的有效近似算法，着色理论的应用受到了很大的限制，这有待 于我们去进一步的研究。 2 直瘟篮息工程盎堂亟望些监童 第一章图论和着色问题 1 1 图论的发展 现实世界中的许多问题都可以归结为研究一些事物及其之间是否具有某种联系的问 题。例如在铁路货运系统中，人们关心的是货物集散地及其之间是否有铁路相通；在电话 通讯问题中人们关心的是电话机和电话机之间是否有电话线连接；在一个讨论小组中哪些 人互相认识等。如果用点( 称为顶点) 来表示事物，用连接两点的线条( 称为边) 来表示 事物之间的联系，则这些问题的描述可以用点线图来表示，这种点线图就是图论中所讨论 的图。 图论壤早起源于著名的哥尼斯堡七桥问题。普瑞格尔河从古城哥尼斯堡市中心流过， 河中有两个小岛，筑有七座古桥，如图1 - 1 1 ( a ) 所示，a 、b 、c ，d 表示陆地。 4 c ( a ) 图1 - 1 一l 哥尼斯堡七桥问题及其图论模型 d 佑) b 问题要求从这四块陆地中任何一块开始，通过每座桥正好一次，再回到起点。然而 无数次的尝试都没有成功。瑞士数学家欧拉( l e u l e r ) 于1 7 3 6 年解决了这个问题，他将 这个问题抽象为第一个图论问题：即把每一块陆地用一个点来代替，将每一座挢用连接相 应的两个点的一条线来代替，从而得到一个图，如图1 1 - 1 中的( b ) 。欧拉证明了这个问题 没有解，并且推广了这个问题，给出了对于一个给定的图是否能够以上述方式遍历的判定 法则。这项工作使欧拉成为图论( 及拓扑学) 的创始人。 在1 8 4 7 年，基尔霍夫( k i r e h h o f f ) 在解决电路理论中求解联立方程时，用一个只由点 和线组成的结构来代替原来的电网络，即把每个电网络用基本图来代替，并且引入了“树” 的概念，但是他的发现却长期没有受到人们的重视。 1 8 5 6 年，英国数学家哈密顿( h a m i l t o n ) 发明了一个所谓环球旅行的游戏：用一个正 十二面体，它的2 0 个顶点各标志世界著名的2 0 个城市，要求游戏者从某一城市出发，沿 正十二面体的棱运行，经过每个城市仅一次，最终回到出发点。这个游戏后来称为哈密顿 直塞矗基王显盔生亟望些诠奎 问题，从中抽象出一个图论中非常重要的概念一哈密顿环，并且派生出货郎问题：一个 货郎担了百货到各村去卖，为他设计一条售货路线，使他每个村子只经过次且走过的路 线最短。由于运筹学、计算机科学和编码理论中的很多问题都可以转化为哈密顿问题，从 而引起广泛的注意和研究。 1 8 5 7 年凯莱( c a y l e y ) 在有机化学领域中发现了一组重要的图，称为树，他应用树来 计算饱和氢化合物c 。h 2 n 2 的同分异构体的数目。 直到1 9 3 6 年。才有第一本图论专著有限图与无限图的理论( 译自德文) 问世，其 作者是匈牙利著名数学家柯尼希。它总结了图论两百年的成果，是圈论发展的第一座里程 碑。图论作为数学的一个新分支已基本形成。 此后的几十年，由于生产管理、军事、交通运输、计算机和通讯网络等方面许多离教 性问题的出现，图论进入发展与突破的快车道，现已成长为数学科学的一个重要分支。图 论中蕴含着强有力的思想、漂亮的图形和巧妙的论证，即使是非常困难的尚未解决的问题， 它的表述也可能是平易近人的。现实生活中处处可以发现图论问题，图论是最接近生活、 最容易阐述的- - f 7 学科。图论的分支很多，如算法图论、极值图论、网络图论、代数图论、 随机图论、模糊图论、超图论等等。 从二十世纪六十年代开始，图论的算法受到了更多的重视。由于现代科技尤其是大型 计算机的迅猛发展，无论是数学、物理、化学、天文、地理、生物等基础学科，还是信息、 交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。目前，图论 在生物网络的结构与动力学稳定性、广义合作网络、城市交通网络、制造业中零部件通用 性分析与用量预测以及销售点的分布、销售量的分布、经济网络、通讯网络、网络模拟中 的应用正处于起步阶段。因而，研究图论问题及其算法具有极其重要的理论和现实意义。 4 直立信息王程盍堂亟肇些纶毫 1 2 图论基本知识 定义1 2 1 1 】 一个图g 是一个三元组，这个三元组包含一个顶点集v ( g ) ，一个边集e ( g ) 和一个关 系，该关系使得每一条边和两个顶点( 不一定是不同的点) 相关联，并将这两个顶点称为 这条边的端点。 定义1 - 2 2 m 一个有向图g 是一个三元组，其中包含一个顶点集v ( g ) ，一个边集e ( g ) 和一个为每 条边分配一个有序顶点对的函数。有序对的第一个顶点是边的尾部，第二个顶点是头部； 它们统称边的端点。 定义l - 2 - 3 图g 的阶，记为n ( g ) ，是图g 中的顶点数。图g 的大小，记为e ( g ) ，是g 中边的条 数。 定义1 - 2 4 一个圈是一条边，它的两个端点是相同的。 定义i - 2 5 1 】 重边是具有同一对端点的多条边。特别的，有向图中的重边是具有相同有序端点对的 多条边。 定义1 - 2 【l 】 一个简单图是不含圈和重边的图。 我们用点的集合和边的集台来确定一个简单无向图，边的集台被表示为一组无序点对 的集合，我们用e - - - t l v ( 或e - - = v u ) 来表示一条以u 、v 为端点的边e 。 同样的。我们也可以用点的集合和边的集合来确定一个简单有向图，边的集合被表示 为一组有序点对的集合，我们用e = u v 来表示一条从u 到v 的边e 。e 的尾部为u ，头部为v 。 v 是u 的后继，u 是v 的前驱。我们用u v 表示“存在一条从u 到v 的边”。 定义1 - 2 - 7 1 1 如果顶点v 是边e 的端点，则称v 和e 是关联的。如果两条边关联同一个顶点，则称 这两条边是关联的。 定义1 - 2 8 f l l 5 直盏癌盅至程盔堂亟望些监塞 当1 1 和v 是一条边的两个端点时，那么它们是邻接的且互为邻居。 定义1 - 2 9 【l 】 一条路径是一个简单图，其顶点可以排序使得两个顶点是邻接的当且仅当它们在顶点 的序列中是前后相继的。 定义1 - 2 1 0 t 1 1 一个环是个顶点和边数相等的图，其顶点可以放置于一个圆周上使得两个顶点是相邻 的当且仅当它们在圆周上相继出现。n 一环是具有n 个顶点的环。 定义1 - 2 1 l 【1 】 通道是由顶点和边构成的一个序列v o 、。1 、”l 、e k 、v k ，使得对于1 i k ，边e i 的端点为v - 1 和v i 。迹是无重复边的一条通道。一条u 。v 通道或u ，v 迹的第一个顶点是 u ，最后一个顶点是v ，它们称为通道或迹的端点。如果通道或迹的端点相同，则称它是闭 合的。 定义1 - 2 1 2 1 1 】 图g 中顶点v 的度，记为d ( v ) ，是关联到v 的边的条数，注意v 上的圈在计算度时要 计算两次。最大的顶点度记为( g ) ，最小的顶点度记为8 ( g ) 。如果a ( g 户6 ( g ) ，则称g 是 正则的。如果所有顶点度是k ，则称g 是k - 正则的。 定义l - 2 1 3 令v 是个有向图中的顶点。出度d + ( v ) 是以v 为尾部的边的条数。入度d ( v ) 是以v 为头部的边的条数。出邻域或后继集n + ( v ) 是 x e v ( o ) ：v x ) 。入邻域或前驱集n ( v ) 是 x v ( g ) ：x v 。 定义1 - 2 1 4 1 1 图g 的子图是一个图h ，它满足v ( h ) v ( g ) ，e ( h ) 量e ( g ) 且h 中边的端点的分配和 g 中的一样，我们用h g 来表示“g 包含h ”。 定义1 - 2 1 5 【1 1 g 的一个生成子图是顶点集为v ( g ) 的一个子图。 定义1 - 2 1 6 1 】 一个从g 到h 的同构是一个双映射f 它将v ( g ) 映射到v ( h ) ，将e ( g ) 映射到e ( h ) ， 使得g 的端点为u 、v 的每条边映射到条端点为f f u ) 和f ( v ) 的边。 6 一 一一 直壶筐息王程盍堂殛望些途童 定义1 - 2 - 1 7 1 1 】 一个完全图是简单图，其任意两个顶点都是邻接的。 定义1 - 2 ，1 8 1 1 如果g 中的每一对顶点都属于某一条路径，图g 是连通的；否则，称g 是非连通的。 定义1 - 2 1 9 f 1 1 图g 中的连通分量是其最大的连通子图。 定义1 - 2 - 2 0 1 1 图的割边或割点是一条边或一个顶点且删除它会增加连通分量的数日。我们用g - e 和 g - m 分别表示从g 中删除一条边e 和删除一个边集m 所得到的子图，用g v 和g s 分别 表示从g 中删除一个顶点v 和删除一个顶点集s 所得到的子图。 定义1 - 2 2 1 1 1 1 图g 的一个分离集或点割是一个集合s v ( g ) ，它使得g s 连通分量多于一个。g 的 连通度，记作g ) ，是这样一个顶点集合s 的大小的最小值，它使得g s 不连通或者只有 一个顶点。如果图g 连通度至少为k ，则称它是k 连通的。 定义1 - 2 - 2 2 1 1 】 由边构成的断连通集是一个集合f e ( g ) ，它使得g f 连通分量多于一个。如果个 至少有两个顶点的图的每一个断连通集至少含有k 条边，则称该图是k - 边连通的。至少有 两个顶点的图g 的边一连通度，记作k ，( g ) ，是断连通集大小的最小值( 这与k 是使g 为k 。 边连通图的最大值等价) 。 定理1 2 - 1 1 1 】 一条边是割边当且仅当它不属于任何一个环。 定理1 - 2 2 【1 1 在含有n 个顶点的连通图中，边的最小条数是n 1 。 定义1 - 2 2 3 1 1 一个不包含环的圈称为是无环的。一个森林是一个无环图。一棵树是一个连通的无环 图。 定理1 2 - 3 树的每条边都是割边。在树中添加一条边恰好形成一个环。 7 亩毫信息王程峦堂砸望些垃童 定理1 2 4 【l 】 对于n 顶点图g ( n 1 ) ，下面的命题等价( 并刻画了具有1 1 个顶点的树的特征) ： ( a ) g 是连通的并且无环。 ( b ) o 是连通的并且有n 1 条边。 ( c ) g 有n - 1 条边并且无环。 定义l r 2 2 4 1 】 图g 的一个k - 着色是一个标号映射f ：v ( g ) 一s ，其中l s f = k ( 通常取s = k 】) ，s 中的标 号称为颜色。一个k - 着色称为一个真着色，如果图g 中相邻顶点具有不同的标号。一个图 穗为可k - 着色，如果它有一个k 真着色，图g 的色数烈g ) ，指的是使图g 可l 。着色的最 小整数k 。 ( 注：因为不能为同一个顶点着不同的颜色，所以有圈的图不能被着色。因此，本文中讨 论的图都是不带圈的。) 定义1 - 2 - 2 5 1 】 图g 的一个k - 边着色是一个标号映射 e ( g ) 一s ，其孛t s t = k ( 通常，我们设s = k j ) ， 这些标号称为颜色。一个k - 边着色是真的，如果相互关联的边具有不同的标号。一个图是 可k - 边着色的，如果它有一个真k 边着色。无圈图g 的边- 色数r ( g ) 是使得g 是可k - 边着 色的最小k 值。 ( 注：一个带圈的图没有真的边着色。) 定义1 - 2 2 6 2 边连通平面图的一个真面着色是为其各个面分配颜色使得在边界上具有公共边的面 有不同的颜色。 定义1 - 2 2 7 1 1 如果一个图存在没有交叉的作图，则称该图是可平面的。这种作图称为g 的平面嵌入。 一个平面图是可平面图的一个特定平面嵌入。 定义1 - 2 2 8 1 】 极大可平面图是一个简单可平面图且它不是其他可平面图的生成于图。 定义1 - 2 - 2 9 】 三角剖分是每个面的边界均为3 环的简单平面图。 ( 注：平面图中，面的边界包括面内的割边) 8 直富信息j 王猩盍堂巫堡些监塞 定义1 2 3 0 川 一个图是欧拉图，如果它有一个闭合迹包含所有的边。如果我们不关心闭合迹的第一 个顶点是什么而仍然保持边的循环顺序，则称之为回路。一个图中的欧拉回路或欧拉迹是 一个包含所有边的回路或迹。 定义1 - 2 3 l 【1 】 哈密顿图是有生成环的图，生成环也称为哈密顿环。 9 直壶篮盅工程盘堂亟望些监塞 1 3 图论的应用 。 目前，图论已经广泛地应用于几乎所有的学科领域。下面是几个图论应用的实例。 1 化学领域的应用 在1 9 世纪，数学家a r t h u rc a y e y 用图论来研究简单的烃分子由碳原子和氢原子 组成的化合物。他用树对烃进行建模，令树的顶点集v ( t 产 。】，c 2 ，c 3 ，c 4 h l ，h 2 ，h 3 ， 1 1 4 ，h 5 ，h 7 ，h s ，h 9 ，h i o ，边集e ( t 产 o i h l ，c i c 2 ，c i h 9 ，c f h i d ，c 2 h 2 ，c 2 h s ，c 2 c 3 c 3 h 3 ， c 3 h 7 ，c 3 “，c 4 h 4 ，c a h j ，c 4 h 6 1 ，树t 如图1 - 3 一l 所示。 h 1h 2h 3h 4 i p h i 0c 1、0 2c 3。c 4王 -， ，r r- iiiiii h 91 1 8h 7h 6 图1 - 3 - 1 用树对烃进行建模 在此模型中，c a y l e y 用项点表示碳原子和氢原子，用边来表示原子间的化学键。图1 3 2 表示了另外一种烃，虽然分子式都是c 4 h l o 但它们的物理化学性质不同。 kh 9h i 0 ， i， 厶 c 4c 2 c 3- - 1 rr1r- i b -1r- h 1c 11 1 3 i h 2 图i - 3 2 另外一种烃 2 商业应用：仓库零售店问题 商业上，经常用图来对仓库和零售店进行建模。令v = f w l ，w 2 ，w 3 ，。l ，r 2 ，r 3 ，r a 1 0 直塞篮息工程点茎亟望些监室 r 5 表示3 个仓库和5 个零售店，e = ”1 1 1 r ，w l r 2 ，w 2 r 2 ，w 2 r 3 ，w 2 r 4 ，w 3 r 3 ，w 3 r 5 ) 表示每个仓 库与每个零售店之间的供货关系，如图1 - 3 - 3 所示。 w 1w 2w 3 r lr 2r 3r 4r 5 图1 3 3 仓库与零售店之问的供货关系 3 最短航线问题 对城市间的航线建立图模型g ，如图1 3 - 4 所示，v ( g ) = a ，b ，c ，d ，e ) 表示5 个城 市，e ( g ) = a b ，a d ，b e ，b e ，d e 表示城市间的直达航线，每条边上数字的表示飞行距离， 从中找出从d 到c 的最短航线。 5 abc d e 图l ，3 - 4 城市间的航线 4 邮政路线问题 图1 - 3 5 是一个城市街道的图模型g ，边表示街道，顶点表示街道的交叉路口。现有 一个邮递员从顶点1 出发，它能否恰好通过每条街道一次最后回到起点? 6 固1 - 3 - 5 城市街道的圈模型 直立篮星工程左堂亟望些论室 5 旅行销售商问题 一个销售商要从他所在的城市出发，乘飞机去5 个城市，然后回到出发点，如图1 ，3 ，6 ， 顶点表示城市，h 是出发点，边表示城市问的直达航线。他怎样才能访问每个城市恰好一 次，最后回到出发点? dc 图1 - 3 - 6 城市间的直达航线 b 6 对分配模型 有一旅行团组织一批人去旅游，其中有一些人是朋友。他们乘坐的旅行车位子是成对 的。为了让旅途更愉快，旅行图负责人要将成对的朋友安排坐在一起。现对此问题建立图 模型g ，其中的顶点表示人，两个顶点之间的边表示这两个人是朋友，如图1 - 3 7 所示。 求解该问题需要用到图的匹配的相关知识。 b cd 图1 - 3 - 7 朋友关系图 1 2 e 一 直立篮息工程太堂亟望些监奎 1 4 四色问题的提出和发展 在图论历史上，对图的着色问题的研究与著名的四色猜想密切相关，四色猜想是图论 乃至整个数学领域最为著名的猜想之一。 四色猜想的内容是：在一个平面或球面上的任意地图能够只用四种颜色来着色，使得 两个相邻的国家着不同的颜色。这里每个国家必须是一个单连通区域，两个国家相邻是指 它们有一段公共的边界，而不仅仅只有一个公共点。 四色问题的提出来自英国。1 8 5 2 年，毕业于伦敦大学的弗南西斯格思里( f r a n c i s g u t h r i e ) 来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地 图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能 从数学上加以严格证明呢? 他和在大学读书的弟弟佛德雷克( f r e d e r i c k g u t h r i e ) 决心试 一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。 1 8 5 2 年8 月2 3 日，佛德雷克就这个问题的证明请教了他的老师、著名数学家德- 摩 根( d em o r g a n ) ，摩根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名 数学家哈密顿( h a m i l t o n ) 爵士请教。哈密顿接到摩根的信后，对四色问题进行论证。但 直到1 8 6 5 年哈密顿逝世为止，问题也没能够解决。 1 8 7 8 年，英国当时最著名的数学家凯莱( c a y l e y ) 正式向伦敦数学学会提出了这个问 题，于是四色猜想成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四 色猜想的大会战。1 8 7 9 年，肯普( k e m p e ) 提交了证明四色猜想的论文，宣布证明了四色 定理，大家都认为四色猜想从此也就解决了。 ( a )( b ) 图i - 4 一i 肯普定义的正规图和非正规图 肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的 国家相遇于一点，这种地图就说是“正规的”，如图卜4 一l ( a ) ；否则为非正规地图，如图 卜4 1 ( b ) 。一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色 种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正 规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。 肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一个国家数 最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻屋数少于六个，就 直童信息工程盘堂亟望业诠毫 会存在一个国家数较少的正规地图仍为五色的，这样一来就不存在极小正规五色地图了。 这样肯普就认为他已经证明了四色猜想但是后来人们发现他错了。 回 雷l - 4 2 肯普提出的4 不可避免构形” 不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。第一个概念 是“构形”。他证明了在每张正规地图中至少有一国具有两个、三个、四个或五个邻国， 不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、 四个或五个邻国组成的一组“构形”( 如图卜4 - 2 ) 是不可避免的，每张地陶至少含有这四 种构形中的一个， 肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证 明了只要五色地图中有一国具有四个邻国就会有国家数减少的五色地图。自从引入“构 形”，“可约”概念后，逐步发展了检查构形判断是否可约的一些标准方法。能够寻求不可 避免构形集，是证明四色问题的重要依据。但要证明一些大的构形可约，需要检查大量的 细节，这是相当复杂的。 1 1 年后，即1 8 9 0 年，数学家赫伍德( i t e a w o o d ) 指出了肯普证明的漏洞，并沿用肯普 的证明方法证明了用五种颜色可以对任意地图着色。赫伍德的证明采用了数学归纳法，对 国家个数进行归纳，下面是赫伍德的证明。 国家数不太于5 时，任意地图是可以用五种颜色着色的。 假设国家数为n ( n 5 ) 时的任意地图是可以用五种颜色着色的。国家数为n + 1 时， 地图中必定存在一个国家v ，其邻国数不超过5 。将v 与它的一个邻国合并，则合并后的地 图是可以用五种颜色着色的。再来考虑从已经用五种颜色着色的合并后的地图中分离出v 时如何为v 着色。 若v 的邻国数小于5 或v 的邻国的颜色数小于5 ，则v 可以用和邻国不同的颜色着色， 即地图是可以用五种颜色着色的。 若v 的邻国数等于5 且邻国的颜色数等于5 ，对其邻国按如下的方式调色，可以使得 五个邻国的颜色数变为4 。 用h 。表示所有用颜色i 和j 着色的国家，在h d 的任意个连通的区域中将这两种颜 色互换，任意两个相邻国家的着色仍然是不同的。在v 的五个邻国中，必定存在两个国家 1 4 直立篷星王程态生亟主望、业监奎 ( 假设分别着l 和j 颜色) 在h i 的两个不同的连通区域中，则将其中一个连通区域中的两 种颜色互换，就使得v 的邻国的颜色数变为4 ，则v 可以用和邻国不同的颜色着色，即地 图是可以用五种颜色着色的。 因此，任意地图都是可以用五种颜色着色的。 在冲击四色猜想的尝试中，另外值得一提的是，1 8 8 0 年泰勒( t a i t ) 曾断言“每个3 一 正则3 一连通平面图都是哈密顿图”，并在这个假设下给出了四色猜想的证明。但是，在1 9 4 6 年。w t t u t t e 构造了一个3 一正则3 一连通非哈密顿图，从而否定了泰勒的证明。 后来的数学家对四色问题绞尽脑汁，但始终一无所获。人们开始认识到，这个貌似容 易的题目，其实是一个可与费马猜想相媲美的难题。 进入2 0 世纪以后，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1 9 1 3 年，美国著名数学家、哈佛大学的伯克霍夫( b i r k h o f f ) 利用肯普的想法，结合自己新的 设想，证明了某些大的构形可约。后来美国数学家富兰克林于1 9 3 9 年证明了2 2 国以下的 地图都可以用四色着色。1 9 5 0 年，有人从2 2 国推进到3 5 国。1 9 6 0 年，有人又证明了3 9 国以下的地图可以只用四种颜色着色。随后又推进到了5 0 国。这种推进仍然十分缓馒。 电子计算机的发明，促使更多数学家对四色问题迸行研究。从1 9 3 6 年就开始研究四色 猜想的海克( h e e s c h ) ，公开宣称四色猜想可用寻找可约图形的不可避免构形集来证明。他 的学生丢雷编写了一个计算机程序，海克不仅能用程序产生的数据来证明构形可约，而且 描绘可约构形的方法从改造地图转变为从数学上的“对偶图”着手。海克把每个国家的首 都标出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都( 称为顶点) 及铁路( 称为边) 外擦掉其他所有的线，剩下的称为原图的对偶圈。到了六十年代后期， 海克引进一个类似于在电网络中移动电荷的方法来求不可避免构形集。在海克的研究中第 一次以颇不成熟的形式出现了“放电法”，这对以后关于不可避免构形集的研究是个关键， 也是证明四色定理的中心要素。 美国伊利诺大学哈肯( h a k e n ) 在1 9 7 0 年着手改进“放电过程”，后与阿佩尔( a p p e l ) 合作编制程序。在1 9 7 6 年5 月，他们在美国伊利诺斯大学的三台电子计算机上，用1 2 0 0 个小时作了1 0 0 亿逻辑判断，找到了一个包含1 9 3 6 个可越构形的不可避免集，完成了四色 定理的证明，轰动了世界。当两位数学家将他们的研究成果发表的时候，当地的邮局在当 天发出的所有m 件上都加盖了“四色足够”的特制m 口戳，以庆祝这一难题获得解决。 到1 9 8 3 年，更精细的工作得到了一个由1 2 5 8 个可约构形组成的不可避免集。1 9 9 6 年， n e i1r o b e r t s o n 、d a n i e ls a n d e r s 、p a u ls e y m o u r 和r o b i nt h o m a s 用同样的方法再现了 这个证明，他们将用来得至u 不可避免集的启发式规则减少到3 2 条，得到了一个由6 3 3 个可 直立篮恳王程盘堂亟土生业监塞 约构形组成的不可避免集。到1 9 9 7 年，四色定理的证明在一台桌面工作站上花大约3 小时 就可以得到。 与许多科学上的难题一样，解决四色猜想的意义不仅仅在于其本身，而是在验证这个 猜想的过程中各种各样的尝试推动丁数学理论的发展，特别是图论中着色问题的研究与应 用。四色猜想的证明不仅解决了一个历时一百多年的难题，而且成为数学史上一系列新思 维的起点。在四色问题的研究过程中，不少新的数学理论随之产生，也发展了很多数学计 算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，四色定理在 有效地设计航空班机日程表，编写计算机程序上都起到了推动作用。 然而，很多数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书 面证明方法。直到现在，仍有不少数学家和数学爱好者在寻找更简洁的证明方法。 1 6 直立焦息_ i 程盍生亟望些业室 1 5 着色问题的应用 现实生活中，很多问题都可以转化为着色问题。比如有些事物的基本属性要求它们之 间相互隔离，涉及这些事物的问题就可以用图着色来解决。比较典型的着色问题有下面几 类： ( 1 ) 动物园围栏设计 现代动物园允许动物尽可能地自由活动，但因为两个原因围栏仍是必要的：第一，需 要一个基本的围栏把动物关在动物园内；第二，需要围栏将捕食者与被捕食者隔离开。某 动物园有n 种动物a 】，a 2 ，a n ，壤少需要多少围栏? 我们构造简单无向图g = ( v ，e ) ，其中， v ( g 户 8 1 ，a 2 ，) ， 边4 弓e ( g ) 表示动物a 捕食动物a j 。 则需要的最少围栏数等于图g 的色数。着色相同的顶点所表示的动物可以放在同一围 栏中。 ( 2 ) 贮藏问题( s t o r a 辨p m b l e m ) 某工厂生产n 种化学产品c ，e 2 ，c 且。其中某些产品是互不相容的，它们若互相接 触会引起爆炸，该厂必须把不相容的化学产品储藏在不同的仓库中。试问至少要有几个仓 库? 我们构造简单无向图g = ( v ，e ) ，其中， v ( g 产 c l ，c 2 ，c i i ， 边c 而e ( g ) 表示化学产品c i 与c j 互不相容。 则仓库的最小数目等于图g 的色数。着色相同的顶点所表示的化学产品可以放在同一 仓库中。 ( 3 ) 电视频道分配问题 某地区有n 架电视发射台t 1 ，t 2 ，t n 。主管部门为每家电视台分配一个频道。为 排除干扰，使用同一频道的发射台之间的距离必须大于指定的正数d 。试问该地区至少需 要多少频道? 构造简单无向图g v ，e ) ，其中， v ( g ) ： t l ，t 2 ，l ) ， 边t t j e ( g ) 表示l 与1 ：i 之间距离d 。 则需要的最小频道数目等于图g 的色数。 1 7 直塞篮息工握盔坐殛生业j 垒童 ( 4 ) 考试安排问题 某高校有n 门选修课”i ，v 2 ，v n 需要进行期末考试，同一学生不能在同一天里参 加两门课程的考试，f 萄该校的期末考试至少要几天? 构造简单无向图g = 4 时，在瓴中，任意一条边u v 的两例都有两个面， 且这两个面只有u v 一条公共边，则u 、v 的度必定不小于3 。又因为边u v 是在g 。中任意 选择的，因此g 。中所有顶点的度都不小于3 ，即5 ( g n ) 3 。该命题成立。 命题2 - 1 - 3 8 ( 6 。) 5 证明： 当n 6 时，因为g 。是简单图，所以6 ( g 。) m 1 5 。 当n 7 时，由引理2 - 1 2 ，g 。有3 n - 6 条边，则g 。的所有顶点度之和为6 n 1 2 ，可得 6 n - 1 2 n 6 ( g j ，即n 6 6 ( g 。) 1 2 。若a ( o 。) 6 ，则6 - 8 ( g 。) 0 ，则不等式n 6 一a ( g 。) 】1 2 不成立，因此8 ( g 。) 5 。 综上所述，命题成立。 由引理2 - 1 - 2 ，在k ( k 3 ) 个顶点的极大平面图g k 中，按照如下三种方式中的一种 增加顶点，可以得到k + 1 个顶点的极大平面图g k + l 。 ( 1 ) 面内加点添三边 g k 面内加点添三边方式如图2 - 1 2 所示，图中面a 边界上的三个顶点在该面之外还可 能与其他的顶点相连。 闰2 - 1 之极大平面图中面内加点添三边 2 l 直立值息王程盘坐亟望些论童 ( 2 ) k 4 时，去一边加点添四边 g k 去一边加点添四边方式如图2 1 3 ，图中a 和b 两个面之外的区域中还可能包含其 他的边或顶点。 ( 3 ) k 5 时，去两 g k 去两边加点 其他的边或项点。 图2 1 - 4 五个以上顶点的极大平面图中去两边加点添五边 区域中还可能包含 按上述方法由3 个顶点的极大平面图g 3 开始，可以构造n ( n 4 ) 个顶点的极大平面 图瓯，这种构造极大平面图的方法称为加点法。 由3 个顶点的极大平面图g 3 开始，只采用上述的( 1 ) 和( 2 ) 两种方式构造n ( n 4 ) 个顶点的极大平面图g 。的方法称为部分加点法。 直立信息工程盘堂亟生、业逾童 2 2 加点法算法分析 定义2 - 2 一l 平面图g 的某个面的长度是围成该面的( 所有) 闭合通道的总长。 ( 注：面内的割边在计算该面的长度时要被计算两次) 命题2 - 2 1 极大平面图每个面的长度为3 。 证明； 由引理2 。1 1 2 ，极大平面图是个三角剖分。由定义l - 2 - 2 9 ，三角剖分中每个面的边界 都是3 环，