图论及其应用

《图论及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

信息与通信工程研究生系列教材图论及其应用孙惠泉编著北京 内容简介本书系统介绍了图论的基本知识，如树、连通性、遍历问题、匹配、顶点着色、边着色、平面图和网络等。作为正文的补充，书中收集了大量经典的习题，并在书后附有提示及解答，以便自学。与一般图论书不同的是，本书指明了许多应用中常见的图论问题是ＮＰ困难问题，便于读者在科研工作中及时注意这种问题。本书力求立论严谨、简明易懂，只要是有一定数学基础的高中毕业生都可看懂。本书特别强调推理（而且还是在离散对象上的推理）的重要性，因为这是培养独立科研能力的必由之路。本书可作为大学信息类及计算机类硕士研究生及高年级本科生的图论教材或参考书，也可作为其他相关专业科技工作者及图论爱好者的学习参考书。图书在版编目（ＣＩＰ）数据图论及其应用／孙惠泉编著．—北京：科学出版社，２００４　（信息与通信工程研究生系列教材）ＩＳＢＮ７０３０１３８６６Ｘ　Ⅰ．图…　Ⅱ．孙…　Ⅲ．图论研究生教材　Ⅳ．Ｏ１５７．５中国版本图书馆ＣＩＰ数据核字（２００４）第０６８５８０号责任编辑：匡敏姚庆爽／责任校对：宋玲玲责任印制：张克忠／封面设计：陈敬出版北京东黄城根北街１６号邮政编码：１００７１７ｈｔｔｐ：／／ｗｗｗ．ｓｃｉｅｎｃｅｐ．ｃｏｍ印刷科学出版社发行各地新华书店经销２００４年９月第一版开本：Ｂ５（７２０×１０００）２００６年８月第三次印刷印张：１７１／４印数：４５０１—６０００　　　　字数：３４００００定价：２７．００元（如有印装质量问题，我社负责调换枙环伟枛） 前言本书是作者在给北京邮电大学研究生和本科生讲授了二十多年“图论及其应用”课程的基础上，将教学资料及体会整理编写而成的。通过这些年的教学，除了因许多图论算法已包含在数据结构等教科书中，以及教学时间不足等原因外，笔者越来越感到应该把侧重点放在训练学生掌握图论基本证明方法上。如果一个学生学完这门课后，仍然不能自己判定自己做的作业是对或错，那么可以说他没有学好这····门课。掌握了基本证明方法也就有了这方面的自学能力，这将使学生在科研工作中，面对图论（网络）的新旧结论以及专业知识纵横交错的复杂对象，会感到更自主、更自在。为此，在定理证明中，笔者往往不满足于一个证明，但凡有来自名家的经典证明，书中一般都会收录其中。因此，第一个证明总是“正统的”，其他证明只好请读者“自取”。书中的附录及打号的章节也属“自取”部分。甩掉这些内容后，６０学时的教学并不轻松，其根源是掌握基本证明方法要有不少揣摩和适应的功夫。此外，笔者对许多ＮＰ完全或ＮＰ困难的图论问题，在相关的章节中都及时加以指出，以便在设计算法时明确方向，这是本书的另一重要特色。习题是学好图论的必由之路，不但要多做，而且要做好。凡是序号用黑体字标出的习题，都应尽量做。本书除了有题解外，对打号的习题还有提示。题解主要是为自学的读者提供参考。大多数习题都是较容易的，有些只是对正文的一个补充，因此一般读者应尽量不要看题解，自己做往往比看题解更省时省力，何况看题解的效果并不好。此外，笔者还把一部分内容转移到了习题中。虽然笔者尽量完善本书，但由于时间仓促，疏漏之处仍在所难免，敬请读者不吝施教，不胜感谢。本书的出版得到了北京邮电大学以郭军教授为首的信息工程学院院领导的大力支持，以及胡正名、阮传概、陆传赉诸教授和罗群、王维嘉、卓新建等同事的关心和帮助，特此一并表示感谢。科学出版社匡敏女士为本书的出版做了不少工作，在此一并致谢。孙惠泉２００４年６月１８日于北京·ｉ· 目录前言第１章图的基本概念………………………………………………………………１　　１．１　图的概念……………………………………………………………１　　１．２　同构…………………………………………………………………５　　１．３　图的矩阵和顶点的度………………………………………………９　　１．４　子图…………………………………………………………………１１　　１．５　路和连通性…………………………………………………………１４　　１．６　圈……………………………………………………………………１８　　１．７　最短路问题…………………………………………………………１９第２章树…………………………………………………………………………２３　　２．１　树和割边……………………………………………………………２３　　２．２　边割和键……………………………………………………………２８　　２．３　割点…………………………………………………………………３４　　２．４　连线问题……………………………………………………………３６　　２．５生成树的计数及Ｃａｙｌｅｙ公式……………………………………３９第３章连通度……………………………………………………………………４２　　３．１　连通度………………………………………………………………４２　　３．２　块……………………………………………………………………４５　　３．３Ｍｅｎｇｅｒ定理……………………………………………………４８　　３．４　可靠通信网的建设问题……………………………………………５４　　３．５边的共圈性及共闭迹性…………………………………………５４第４章遍历问题…………………………………………………………………５７　　４．１　Ｅｕｌｅｒ环游…………………………………………………………５７　　４．２　最优环游……………………………………………………………５９　　４．３　Ｈａｍｉｌｔｏｎ圈………………………………………………………６２　　４．４　旅行售货员问题……………………………………………………６７　　４．５Ｈａｍｉｌｔｏｎ问题进阶………………………………………………６９第５章匹配………………………………………………………………………７４　　５．１　匹配…………………………………………………………………７４　　５．２　独立集、团、覆盖和匹配间的关系…………………………………７６　　５．３　偶图的匹配和覆盖…………………………………………………７７·ｉｉｉ· 　　５．４　完美匹配……………………………………………………………８２　　５．５　人员分派问题………………………………………………………８６　　５．６　最优分派问题………………………………………………………８９　　５．７稳定匹配…………………………………………………………９２第６章着色问题…………………………………………………………………１００　　６．１　边着色……………………………………………………………１００　　６．２　排课表问题………………………………………………………１０７　　６．３　顶点着色和色数…………………………………………………１０８　　６．４　Ｂｒｏｏｋｓ定理………………………………………………………１１６　　６．５　围长和色数………………………………………………………１１７第７章平面图……………………………………………………………………１１９　　７．１　平图和平面图……………………………………………………１１９　　７．２　对偶图……………………………………………………………１２４　　７．３　Ｋｕｒａｔｏｗｓｋｉ定理………………………………………………１２６　　７．４　五色定理和四色猜想……………………………………………１２９　　７．５　平面性算法………………………………………………………１３５第８章有向图……………………………………………………………………１３８　　８．１　有向图……………………………………………………………１３８　　８．２　竞赛图……………………………………………………………１４３　　８．３　有向Ｈａｍｉｌｔｏｎ圈…………………………………………………１４７第９章网络………………………………………………………………………１５０　　９．１　流…………………………………………………………………１５０　　９．２　最大流最小割定理………………………………………………１５６　　９．３Ｍｅｎｇｅｒ定理进阶………………………………………………１６１　　９．４　可行流……………………………………………………………１６５第１０章ＮＰ－完全问题………………………………………………………１７１　　１０．１　引言……………………………………………………………１７１　　１０．２　优化问题的三种提法…………………………………………１７１　　１０．３　Ｐ类和ＮＰ类…………………………………………………１７３　　１０．４　多项式变换及ＮＰ完全性……………………………………１７９　　１０．５　Ｃｏｏｋ定理………………………………………………………１８０　　１０．６　六个基本ＮＰＣ问题……………………………………………１８２习题提示……………………………………………………………………………１９１习题解答……………………………………………………………………………１９４参考文献……………………………………………………………………………２７０·ｉｖ· 第１章图的基本概念１１　图的概念图论是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人，既有许多天才的数学家，也有不少业余爱好者。我们先来看几个著名的例子：¨Ｋｏｎｉｇｓｂｅｒｇ七桥问题¨在贯穿古普鲁士Ｋｏｎｉｇｓｂｅｒｇ城（第二次世界大战时划归原苏联，改名Ｋａｌｉｎｉｎｇｒａｄ，今属白俄罗斯）的Ｐｒｅｇｅｌ河上有七座桥连接两岸及河中的两个小岛（如图１１１所示，第二次世界大战时已几乎夷为平地）。当时困扰当地居民的一个问题是：是否存在一种走法，走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因。问题被提到当时在ＳｔＰｅｉｔｅｒｓｂｕｒｇ的数学教授Ｅｕｌｅｒ（１７０７～１７８２）面前，他把每块地用一个顶点代替，把每座桥用连接对应顶点的一条边代替，把问题抽象为图１１２中的图。为解决这个具体问题，他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明。这结果发表于１７３６年，并被公认为第一篇图论文章，他本人也被尊崇为图论和拓扑学之父。图１１１图１１２电网络为了解出电网络中每个分支电流所满足的线性联立方程组，Ｋｉｒｃｈｈｏｆｆ于１８４７年发展了树的理论。作为物理学家，Ｋｉｒｃｈｈｏｆｆ却有着数学家的思维方式，他把具有电阻、电容、电感等的电网络，只用对应的顶点和边来代替，每边并不附带其·１· 对应元件类型的任何表示，即他把电网络N用其潜含的（基础）图G代替。由此他指出，为了求解该方程组，只要解其中对应于基本圈的那些方程即可。这里基本圈是指由G的任一生成树T所确定的那些圈（即每条不属于T的边在T上所确定的圈）。例如图１１３的网络共有３个基本圈。Ｋｉｒｃｈｈｏｆｆ的方法已成为电网络机助分析和设计的基础。图１１３四色猜想这个由伦敦的一名中学生在一百多年前提出的猜想是说，每个地图至多用４种色就可以“正常”着色了（即，可以使每两个有公共边界的国家都涂上不同的颜色）。我们把地图看成是由平面上的顶点和边所组成，每个国家对应于其中的一个平面区域，这样，每张地图就对应于一个平面图（即，可画在平面上使任两边都不在非顶点处相交叉的图），而每个国家对应于平面图中的一个面。在图论中四色猜想是说：每个平面图的面至多用４种色就可以“正常”着色了。例如图１１４左图中共有７个面：A，B，C，D，E，F，H。这个平面图需要用４种色，色１，２，３及４，才能有正常面着色。图１１４如果我们用一个顶点代表一个国家，并把每两个有公共边界的国家用一条边连接起来，则得到一个平面图G，如图１１４中的右图所示。可以证明（第７章）四色猜想就等价于：任何平面图G的顶点至多用４种色就可以“正常”着色了（即，使每条边两端的（不同）顶点不同色）。例如图１１４中的地图对应的平面图G中，其顶点着色用数字１，２，３，４表示。·２· 这个困扰了无数天才数学家和众多业余爱好者达一个多世纪的猜想，终于在１９７６年由Ａｐｐｅｌ和Ｈａｋｅｎ用大型计算机证实了。当时需要用手工输入１４００个图形到计算机里，再用巨型程序去计算。该证明至今未能得到彻底的检验。近来Ｒｏｂｅｒｔｓｏｎ，Ｓａｎｄｅｒｓ，Ｓｅｙｍｏｕｒ和Ｔｈｏｍａｓ提出了一个改进，“只要”６３３个图形就够了，且简化了证明方法。但是，无论如何，由于至今未能得到理论上的证明，人们仍然无法一窥四色猜想得以成立的内在机制，使证明该猜想的努力难于停息。上面三个例子每个都引出了一个图（形），它们在相当程度上代表了我们所研究问题的实质。例如在七桥问题中我们用图１１２代替图１１１，已经有了很高的抽象性，甩掉了许多与问题实质无关的水分，但顶点的位置、边的形状仍然与问题实质无关，因此在图论中把七桥问题对应的图G定义为G＝（V（G），E（G））其中V（G）＝｛A，B，C，D｝E（G）＝｛AC，AC，AB，AB，AD，BD，CD｝这样给出的图G，既没有顶点的位置，也没有边的形状，仅包含了顶点之间的连接关系，即我们所考虑的问题的实质性结构。在图论中，一个图（ｇｒａｐｈ）G定义为由有限非空顶点集合（ｖｅｒｔｅｘｓｅｔ）V（G），及··有限边集合（ｅｄｇｅｓｅｔ）E（G）组成的，记为G＝（V（G），E（G））（）其中E（G）的每个元素是V（G）中顶点的无序对，称为G的边（ｅｄｇｅ）。图的定义中，并不要求每个无序对的两个元素不同；也不要求任二无序对彼此不同。例如V（G）＝｛A，B，C，D｝（）E（G）＝｛a，b，c，d，e，f，g，h｝（）其中a＝CB，b＝CD，c＝AD，d＝CA，e＝CA，f＝CA，g＝DD，h＝DD图G显然可用图１１５给出的图形来表示。我们称图１１５中的图形为图G的几何实现（ｇｅｏｍｅｔｒｉｃｒｅａｌｉｚａｔｉｏｎ，代表ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）。显然边数大于等于１的图都有无穷多个几何实现。但是用图形给出一个图，往往比用数学式子更简洁明了，因此今后我们将对图和图的几何实现经常不加区别。我们把由顶点u和v的无序对组成的边e，记为e＝图１１５uv或vu。并称u和v为e的端点（ｅｎｄ）；称边e连接（ｊｏｉｎ）u和v。我们也称边e和顶点u（及v）相关联（ｉｎｃｉｄｅｎｔ）；顶点u（及v）和边e相关联。我们还称u与v相邻（ａｄｊａｃｅｎｔ）。类似地，如果两条不同的边有公共顶点，则也称它们相邻。例如，图１１５中边d，e，f，b及a都彼此相邻。总之，关联是顶点和边之间的关系；相邻是·３· 顶点和顶点，或边和边之间的关系。如果两条边有相同的两端点，则称它们为重边（ｍｕｌｔｉｐｌｅｅｄｇｅ）或平行边（ｐａｒａｌｌｅｌｅｄｇｅ）。如果一条边的两端点相同，就称它为环（ｌｏｏｐ）；否则称为棱（ｌｉｎｋ）。例如图１１５中d，e及f是（３重）平行边；g＝DD为环。除g与h外，该图其他边都是棱。称不包含环和重边的图为简单图（ｓｉｍｐｌｅｇｒａｐｈ）。例如图１１３的图G和T，及图１１４中的两个图都是简单图。仅有一个顶点的图称为平凡图（ｔｒｉｖｉａｌｇｒａｐｈ）。注意，它可能拥有多条环。称不包含边（即E＝Φ）的图为空图（ｅｍｐｔｙｇｒａｐｈ），即它只有一些孤立顶点（ｉｓｏｌａｔｅｄ），如图１１６所示。例１１　若一群人中，凡相识的两人都无公共朋友，凡不相识的两人都恰有两个公共朋友，则每人的朋友数相等。（注：相识者为朋友。）证明作一图G：以该群人为其顶点集，两个顶图１１６点相邻当且仅当对应的两个人相识。先考虑任二相邻顶点u与v：令A与B是G中分别和u与v相邻的所有顶点的集合。由假设条件知A与B不相交。从而A中任一顶点a都与v不相邻。于是a与v应恰有２公共朋友。但，显然，a与v已有一个公共朋友u。设a与v的另一个公共朋友为b，则b首先必须是与v相邻的，因此我们有a与b（∈B）相邻；且a不能与B中其他顶点相邻故A中任一顶点a恰只与B中一个顶点b相邻，反之亦然。从而集合A与B之间存在一一对应关系。故│A│＝│B│，由此得，任二相识的人u与v的朋友数相等（图１１７）。今假设存在两人x与y，他们的朋友数不等，则由上述知在G中他们不相邻。从而由假设条件知，他们有一公共朋友，设为w。但由上述，这又导致x，y，w三人有相同的朋友数，矛盾。／／当我们作上述例子时，我们还没有一个图论定理，连图论的术语也知之甚少，但该证明却是图论图１１７证明的一个缩影：其中几乎看不到一个数学式子，但它的确是一步步的推理，且所涉及的结论必须是（在满足给定条件的）普遍意义······下成立的，而不是仅仅在个别图上成立，甚或是“感觉”它是“大概齐”成立。但为了使证明显得很简练，我们又往往只将一些比较明显的结论直接摆出来。为此使不少初学者感到很迷惘，觉得证明过程似乎有理，又似乎是一些“感觉”和“大概齐”的堆积。他们往往不能判定自己写出来的证明是否是正确的。只有通过做大量的习题，才能逐渐掌握和适应图论证明中的方式方法，并慢慢步入正轨。它的最重要标志就·４· 是上述迷惘的消散！此外，在进行证明的过程中，使用所考虑的图的一般模型（例如图１１７），常常对问题的分析很有帮助。但绝不可过于依赖。特别是在写出证明时，应尽量不要看它，以免由于疏忽，使所选模型只代表了一个特殊情形。（虽然这种错误连一些名家偶尔也难以避免。）在图的几何实现中，有些边可能不得不在非顶点处相交叉（例如图１２５中图K３，３的任何一个几何实现都必然出现这种情形，称为非平面图）。为了将顶点和这种交叉点区别开来，我们约定用小圆点来表示顶点。···对图和图的几何实现不加区别虽然给我们带来不少方便，但也带来了不少负面影响。不少读者今后常常会误把图的几何实现当成就是图本身，导致身陷迷雾而不自知。例如，可能会产生这样的疑问：“图中顶点（的位置）怎么可以随便移动呢！？”为方便起见，我们约定用记号ν（G）ε（G）分别表示图G的顶点数及边数。今后我们常用G表示一个图，且当讨论中只涉及一个图时，可将V（G），E（G），ε（G）及ν（G）常常简记为V，E，ε及ν。对今后出现的图的其他参数，也照此办理。习题ν１１１　若G为简单图，则ε≤。２１２　同构称图G恒等（ｉｄｅｎｔｉｃａｌ）于图H，记为G＝H，当且仅当V（G）＝V（H），E（G）＝E（H）。因此可以用形状相同的几何实现表示。例如图１２１中的图G和H恒等。反之如果两个图可以用形状相同的两个几何实现来表示，它们并不一定是恒等的。例如图１２１中，图G和F并不恒等，但它们却可以有相同形状的几何实现。具有···这种性质的两个图，易见，只要把其中一个图的顶点和边的标号适当改名，就可得·到与另一个恒等的图。我们称具有这种性质的两个图同构（ｉｓｏｍｏｒｐｈｉｃ），其正式定义为：称图G同构于图F，记为GF，当且仅当在V（G）与V（F），以及E（G）与E（F）之间，各存在一一映射Ψ：V（G）→V（F）以及Φ：E（G）→E（F）·５· 且这两个映射保持关联关系，即它们满足关系：Φ（e）＝Ψ（u）Ψ（v），e＝uv∈······E（G），如图１２２所示。图１２１图１２２例如图１２３中的两个图是不同构的。假设不然，则顶点a与u，及f与z，应该是对应顶点（两个图中与它们相关联的边数为最多和最少）。这又导致c与v相对应。但在G中a与c不相邻；而在H中u与v却相邻，矛盾。图１２３同构的图显然有相同的结构，它们之间仅仅在顶点和边的名字上有所不同而已。由于我们主要关心的是图的结构性质，因此当我们画一个图时，有时会省略其标号。一个无标号图，可看成图的同构等价类的一个代表。我们给出顶点和边的标号主要是为了便于称呼它们。判定两个图是否同构，有很重要的实用价值。例如我们制作的电路板应该和设计的电路图同构。由于电路板的规模迅速增长，极需用计算机来判定其同构性。然而判定两个图是否同构，至今仍然是个尚待解决的困难问题（ｏｐｅｎｐｒｏｂｌｅｍ），即不知其是否有好算法，抑或为ＮＰｈａｒｄ问题。称一个简单图G为完全图（ｃｏｍｐｌｅｔｅｇｒａｐｈ），如果G的任二顶点都相邻。我们把n个顶点的完全图记为Kn。称V′V（G）为图G中的独立集（ｉｎｄｅｐｅｎｄｅｎｔｓｅｔ），如果V′中任二顶点都互不相邻。注意到这个定义中的“任二”顶点并未要求该二顶点是不同的。例如图１１５中，｛A，B｝，｛A｝，｛B｝都是独立集；但｛B，D｝，｛D｝却都不是！称图G为偶图（二部图，ｂｉｐａｒｔｉｔｅｇｒａｐｈ或ｂｉｇｒａｐｈ），如果存在V（G）的一个２划分（X，Y）（ｂｉｐａｒｔｉｔｉｏｎ，即V（G）＝X∪Y，且X∩Y＝），使X与Y都是独立·６· 图１２４集。我们记偶图为G＝（X，Y，E）。特别地，称（X，Y）为偶图G的２－划分。如果偶图G＝（X，Y，E）中，X和Y之间的每对顶点都相邻，则称G为完全偶图。记│X│＝m，│Y│＝n的完全偶图为Km，n，例如图１２５第②，③图。图１２５类似地可定义，完全三部图（记为Km，n，p，例如图１２５第④图），完全n－部图等。例１２　用标号法判定一个图为偶图。用红蓝两种颜色进行顶点标号如下：任取一未标号顶点v标以红色。再将v的所有相邻顶点都标以蓝色。这时称v为已扫描顶点。若尚存在一已标号未扫描顶点u，将它的所有相邻顶点，（若不出现矛盾）都标以与其相异的颜色，并称u为已扫描顶点；否则任取一未标号顶点并重复上述过程，如此反复进行下去，直到或者所有顶点都已标号，从而该图为一偶图；或者在标号过程中出现矛盾（即出现两个同色顶点相邻），该图为非偶图。这个算法的２时间复杂性显然为O（ν）。习题１２１　若GH，则ν（G）＝ν（H），ε（G）＝ε（H）。证明其逆命题不成立。１２２　证明图１２６中的前４个图都同构：它们都与第５图不同构。图１２６·７· １２３　证明图１２７中的第１，２，３图同构；而第１，４图不同构：图１２７１２４　证明两个简单图G和H同构当且仅当存在一一映射f：V（G）→V（H），使得uv∈E（G）f（u）f（v）∈E（H）。１２５　证明：（１）ε（Km，n）＝mn。２（２）对简单偶图有ε≤ν／４。１２６记Tm，n为这样的一个完全m部图：其顶点数为n，每个部分的顶点数为［n／m］或｛n／m｝个。证明：n－kk＋１（１）ε（Tm，n）＝＋（m－１），　　其中k＝［n／m］。２２（２）对任意的n顶点完全m部图G，一定有ε（G）≤ε（Tm，n），且仅当GTm，n时等式才成立。１２７　所谓k方体是这样的图：其顶点是０与１组成的有序k元组，其二顶kk－１点相邻当且仅当它们恰有一个坐标不同。证明k方体有２个顶点，k２条边，且是一偶图。c１２８　简单图G的补图（ｃｏｍｐｌｅｍｅｎｔ）G，是指和G有相同顶点集V的一个···c简单图，在G中两个顶点相邻当且仅当它们在G中不相邻。cc（１）画出Kn和Km，n。c（２）如果GG则称简单图G为自补的（ｓｅｌｆｃｏｍｐｌｅｍｅｎｔａｒｙ）。证明：①若G是自补的，则ν＝０，１（ｍｏｄ４）。②求出顶点数为４及５的所有自补图。１２９　设图G和H中：V（G）＝｛u１，u２，…，un｝，V（H）＝｛v１，v２，…，vm｝，且vivj∈E（H）dG（ui）＋dG（uj）＝奇数则H一定是个完全偶图。１２１０　若ν≥２的简单图G＝（V，E）中如下性质成立：uv，vw∈／Euw∈／E，　u，v，w∈V则G一定是个完全m部图（某个正整数m）。·８· １３　图的矩阵和顶点的度在图论里，与一个图G＝（V，E），其中V＝｛v１，v２，…，vν｝，相对应矩阵中，我们所关心的矩阵主要有关联矩阵M（G）＝［mi，j］νε及邻接矩阵A（G）＝［ai，j］νν，其中mi，j＝顶点vi与边ej的关联次数＝０，１，２ai，j＝连接顶点vi与vj的边数例如与图１３１中的图G＝（V，E）相对应的关联矩阵与邻接矩阵分别为e１e２e３e４e５e６e７１１００１０１v１１１１００００v２M（G）＝００１１００１v３０００１１２０v４v１v２v３v４０２１１v１２０１０v２A（G）＝１１０１v３１０１１v４注意到M（G）中每列的和恒为２；A（G）是对称矩阵，它的对角线元素ai，i是G中与顶点vi相关联的环的数目。由定义易见M（G）与A（G）都包含了图G的全部信息，反之由M（G）或A（G）也可以完全确定图G。正因为此，在计算机中往往用M（G）或A（G）的形式来存储图G。一般来讲，用A（G）比用M（G）更省存储空间。在数据结构中还有很多更复杂的图１３１存储结构，以便于对图进行运算。图G中顶点v的度（ｄｅｇｒｅｅ），记为dG（v）（当不引起混淆时，简记为d（v）），是G中与顶点v相关联的边的数目，其中每一环记为２。例如，图１３１的图H中d（v１）＝d（v４）＝４。易见，关联矩阵M（G）中，每行之和就是与该行相对应的顶点的度；当G为无环图时，邻接矩阵A（G）中，每行之和也是与该行相对应的顶点的度。我们把G中的最大度记为Δ（G）（简记为Δ）；最小度记为δ（G）（简记为δ）。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。度为０的顶点称为孤立点（ｉｓｏｌａｔｅｄｖｅｒｔｅｘ）。度为１的顶点称为悬挂点（ｅｎｄｖｅｒｔｅｘ），其关联边称为悬·９· 挂边。下面的握手定理说明，在一个集会中总握手次数的两倍，可以通过统计每人握手次数之总和来求出。定理１３１（ｈａｎｄｓｈａｋｉｎｇｌｅｍｍａ）　任一图中，∑d（v）＝２ε。v∈V证明注意到每条边在左式中的贡献恰为２即可。推论１３２　任一图G中，奇点的个数为偶数。证明令X与Y分别为G中的奇点集与偶点集，则∑d（v）＋∑d（v）＝∑d（v）＝２ε＝偶数，v∈Xv∈Yv∈V因此∑d（v）＝２ε－∑d（v）＝偶数，从而│X│为偶数。／／v∈Xv∈Y例１３　任一多面体中，边数为奇数的（外表）面的数目为偶数。证明作一图G，其顶点对应于多面体的面，且二顶点用一边连接，当且仅当对应的两个面有一公共边。于是边数为奇数的面对应于G的奇点。再由推论１３１即得。／／（例如图１３２中的３棱柱，共有２个边数为３的面，及３个边数为４的面。它对应的图G如右图１３２图所示。）图１３３如果一个图中每个顶点v的度都是常数k，则称G为k－正则图（ｋｒｅｇｕｌａｒｇｒａｐｈ）。例如k方体为k正则图。称一个图为正则图，如果对某个k它是k正则的。例如完全图Kn及完全偶图Kn，n为正则图。图１３３中展示了几种正则图的例子。习题０B１３１　证明：适当排列偶图G的顶点，可使A（G）的形式为。ＴB０１３２　证明：δ≤２ε／ν≤Δ（即一个图中度的平均值介于δ与Δ之间）。１３３　若k正则偶图（k＞０）的２划分为（X，Y），证明│X│＝│Y│。·１０· １３４　设V（G）＝｛v１，v２，…，vν｝，则称（d（v１），d（v２），…，d（vν））为G的度n序列。证明：非负整数序列（d１，d２，…，dn）为某一图的度序列∑di是偶数。i＝１１３５证明：任一无环图G都包含一偶生成子图H，使得dH（v）≥dG（v）／２对所有v∈V成立。１３６设平面上有n个点，其中任二点间的距离大于或等于１，证明：最多有３n对点的距离等于１。１３７　证明：在人数大于１的人群中，总有二人在该人群中有相同的朋友数。１３８　图G的边图（ｅｄｇｅｇｒａｐｈ），记为L（G），是个以E（G）为顶点集的图，且L（G）中两顶点相邻，当且仅当它们是G中两条相邻的边。证明：dG（v）（１）L（G）的顶点数为ε（G）；边数为∑。v∈V２（２）K３与K１，３有相同的边图。（事实上有：（Ｗｈｉｔｎｅｙ）设G１与G２为二非平凡简单图，则L（G１）L（G２）G１G２或G１与G２分别为K３与K１，３。）（３）L（K５）的补图同构于Ｐｅｔｅｒｓｏｎ图。（参见习题１２３中图１２７左边第一图。）１３９　称序列d＝（d１，d２，…，dn）为图序列（ｇｒａｐｈｉｃｓｅｑｕｅｎｃｅ），当且仅当存在一个简单图以d为其度序列。例如，（６，５，４，３，３，２，２）是图序列；而（７，６，５，４，３，３，２）及（６，６，５，４，３，３，１）都不是图序列。以下设d＝（d１，d２，…，dn）为非负整数的非增序列，记序列d′＝（d２－１，d３－１，…，dd＋１－１，dd＋２，…，dn），１１n（１）证明：d为图序列∑di为偶数，且i＝１kn∑di≤k（k－１）＋∑ｍｉｎ（k，di）　　k∶１≤k≤ni＝１i＝k＋１（Ｅｒｄｏｓ和Ｇａｌｌａｉ，１９６０，证明上述必要条件也是充分条件。）（２）证明：d为图序列d′为图序列。（３）当已知d＝（d１，d２，…，dn）为图序列时，利用（２）叙述一个算法来构造以d为度序列的一个简单图。１４　子图子图，特别是导出子图及边导出子图，是图论中经常用到的概念。我们称图H为图G的子图（ｓｕｂｇｒａｐｈ），记为HG，如果V（H）V（G），E（H）E（G）。反之，称G为H的母图（ｓｕｐｅｒｇｒａｐｈ）。如果H是G的子图，但H≠G就称H为G的真子图（ｐｒｏｐｅｒｓｕｂｇｒａｐｈ），记为HG；称G为H的真母图。称H为G的生成子图（ｓｐａｎｎｉｎｇｓｕｂｇｒａｐｈ）如果HG且V（H）＝V（G）。反·１１· 之称G为H的生成母图，如图１４１所示。从一个图G中去掉其所有重边及环，所得的简单生成子图称为G的基础简单图（ｕｎｄｅｒｌｙｉｎｇｓｉｍｐｌｅｇｒａｐｈ），如图１４２所示。对图G的非空（为何？）顶点子集V′V（G），G的子图如果以V′为顶点集，以··G中两端都在V′上的边全体为其边集，则该子图称为G的导出子图（ｉｎｄｕｃｅｄｓｕｂｇｒａｐｈ），记为G［V′］。以非空（为何？）边子集E′E（G）为边集，以E′中所有边的端点为顶点集的G··的子图，称为G的边导出子图（ｅｄｇｅｉｎｄｕｃｅｄｓｕｂｇｒａｐｈ），记为G［E′］。以上两种子图，其实，对应于抓取子图的两种运算。下面是抓取子图的另两种运算：G－V′是从G中去掉顶点真子集V′V（G）及与V′相关联的一切边所得的剩···余子图。易见G－V′＝G［V＼V′］　　（注：记V－V′为V＼V′）G－E′是从G中去掉边子集E′E（G）后所得的G的生成子图。注意到，G－··E′与G［E＼E′］有相同的边集，但两者不一定恒等，前者一定是生成子图，而后者不一定如此。关于这四种运算及其相互关系的例子请参看图１４１及１４３～１．４．７。上述四种运算是最基本的取子图运算，今后经常会遇到，一定要认真掌握好。此外，我们·····定义：图１４１图１４２图１４３图１４４图１４５图１４６图１４７G＋E′为往G上添加新边集E′后所得的G的母图。·１２· 为简单计，今后将G±｛e｝简记为G±e；G－｛v｝简记为G－v。设G１与G２为G的子图。如果V（G１）∩V（G２）＝，则称G１与G２为不相交的（ｄｉｓｊｏｉｎｔ）。如果E（G１）∩E（G２）＝（即没有公共边），则称G１与G２为边不重的（ｅｄｇｅｄｉｓｊｏｉｎｔ）。易见，如果G１与G２为不相交的，则它们一定是边不重的，反之如果G１与G２是边不重的，它们仍可能为相交的。G１与G２的并图（ｕｎｉｏｎ），记为G１∪G２，是G的一个子图，其顶点集V（G１）∪V（G２），其边集为E（G１）∪E（G２）。类似地，可定义G１与G２的交图（ｉｎｔｅｒｓｅｃｔｉｏｎ），记为G１∩G２。当G１与G２不相交时其并图称为G１与G２的不相交并，且可简记为G１＋G２。当G１与G２无公共边时，其并图称为G１与G２的边不重并。图１４８F∨H表示不相交图F和H的联图（ｊｏｉｎ），它是在图F＋H中，通过连接F和H中每对顶点所得图。例如，K２∨K３＝K５。例１４　n（≥４）个人的集会中，若每４人中一定有一人认识其他３人，则集会中一定有一人认识其他n－１人。证明作一图G，以全体集会中的人为其顶点集；两个顶点相邻当且仅当对应的两个人相识。若G为完全图，证完。否则，任意取定二不相邻顶点x与y，考虑子··图H＝G－｛x，y｝。令u与v为H的任二顶点。由假设条件，｛x，y，u，v｝四个顶点中一定有一个与其他··三个相邻，而x与y是不相邻的，因此u与v中至少有一个，例如u，与其他三个相邻。特别地，我们有u与v相邻。由u与v的任意性，H是个完全图。这又导致u与G中其他顶点都相邻。（图１．４．８）／／上述例子与１１节中的例子一样，都是“空手套狼”，因此，从中我们可以看清图论证明的一些行为方式。习题１４１　证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。１４２设G为一简单图；n为某固定整数：１＜n＜ν－１。证明：若ν≥４，且Gc中每个n顶点的导出子图均有相同的边数，则GKν或Kν。·１３· １５　路和连通性图G中的一条（u，v）途径（ｗａｌｋ）W＝u０e１u１e２…un－１enun其中u＝u０，v＝un，是一个有限非空序列，由顶点和边交替地组成，且其中每边ej＝uj－１uj，１≤j≤n。W的顶点和边可重复出现（甚或u＝v）。其中，u与v分别称为W的起点（ｏｒｉｇｉｎ）与终点（ｔｅｒｍｉｎｕｓ），其余顶点（有的可能是u或v），称为W的内部顶点（ｉｎｔｅｒｎａｌｖｅｒｔｅｘ）。n称为途径W的长（ｌｅｎｇｔｈ）。特别地，长为０的途径中没有边，且只有一个顶点。当不引起混淆时，特别在简单图中，W可简写为顶点序列W＝u０u１…un－１un例如图１５１的图G中，（C，B）途径W＝CaAdBcAfDgB＝CABADB　　（简写）其中C为起点，D为终点，A，B，A，D为内部顶点。图１５１　G途径W的节（ｓｅｃｔｉｏｎ）是W的一个子序列，且本身也是一个途径。例如，上例中，W的（A，D）节W１＝ABAD。－１W的逆序列unenun－１…e２u１e１u０，显然，也是一个途径，称为逆途径，记为W。例如，上例中－１W＝BgDfAcBdAaC设途径W１＝u０u１…un－１un，W２＝unun＋１…un＋k－１un＋k，则W１与W２在un处衔接起来所得的途径W＝u０u１…un－１unun＋１…un＋k－１un＋k记为W１W２。称边各不相同的途径为迹（ｔｒａｉｌ）。例如，图１５１中途径BcAaCbA是一条（B，A）迹。一条迹中，顶点仍可能重复出现。顶点各不相同的途径称为路（ｐａｔｈ）。例如，图１５１中途径BdAfD是一条（B，D）路。一条路中，边一定不会重复出现，因此路一定是迹，反之结论不一定成立。今后，我们也常将路当作一个图或子图。定理１５１　每一（uv）途径包含一（uv）路。（注：称一条途径包含另一条途径，如果后者的序列是前者的子序列。）证明如果u＝v，则结论显然成立；否则令W＝v０v１…vi…vj…vn为一（u，v）途径，其中v０＝u，vn＝v，且u≠v。若W中的顶点互不相同，则W就是（u，v）路；不然，设vi＝vj（i＜j），则W′＝v０v１…vivj＋１…vn·１４· 也是一条（u，v）途径，长度比W短。若其中仍有重复顶点出现，则对W′重复上述过程。由于W长度的有限性，上述过程必停止于一（u，v）路。／／推论１５２　G中存在（u，v）途径，当且仅当G中存在（u，v）路。／／称图G中顶点u与v为连通的（ｃｏｎｎｅｃｔｅｄ）当且仅当G中存在（u，v）路（（u，v）途径）。容易验证，两顶点间的连通关系是V上的等价关系（即满足自反性、对称性及传递性的二元关系）。它将V划分为一些等价类V１，…，Vω使每个Vi中的任二顶点u与v都连通（即存在（u，v）路）；而不同Vi与Vj之间的任二顶点都不连通。称每个导出子图G［Vi］　　i＝１，２，…，ω为G的一个分支（ｃｏｍｐｏｎｅｎｔ），称ω（G）为G的分支数（参见图１５２）。当ω（G）＝１时称G为连通的，否则为不连通的（ｄｉｓｃｏｎｎｅｃｔｅｄ）。因此连通图中任两顶点间都有一条路相连。图１５２　有３个分支的图G珚对任一非空顶点子集SV，令S＝V＼S（注意：今后对两集合A与B，常用A＼B来表示差集A－B），我们用记号珚珚［S，S］G　　（简写为［S，S］）珚表示G中两端分别在S及S中的一切边的集合（后文中将称为边割）。珚定理１５３　G连通，当且仅当对任SV（G）都有［S，S］≠。证明　（习题）／／图G中若顶点u与v连通，则G中最短（u，v）路的长，称为u与v之间的距离（ｄｉｓｔａｎｃｅ），记为dG（u，v）（其简写为d（u，v））。当G中u与v不连通时，定义dG（u，v）＝∞。易证，任一图G中，任３个顶点u，v，w之间的距离都满足三角不等式（习题１５７）d（u，v）＋d（v，w）≥d（u，w）／／例１５　简单图G中，若δ≥k，则G中有长≥k的路。证明取G中任一最长路P的起点（终点），设为u。则每个与u相邻的顶点x应都在P上（否则x与P构成比P更长的路，矛盾），因此P的顶点数≥d（u）＋１≥k＋１。／／例１６　连通图G中，任二最长路必有公共顶点。·１５· 证明反证，假设G中有二无公共顶点的最长路P与Q。令分别属于V（P）与V（Q）的顶点对中距离最近的顶点对为p与q；R为G中的最短（p，q）路。易见，路···P与R只有一个公共顶点p；路Q与R只有一个公共顶点q。顶点p与q分别将P与Q各分成两个节，从其中分别各选一最长的，设为P１与Q１，则它们和R一起构成G中的一条路，且比P长，矛盾。（图１５３）／／·例１７　G连通，且每个顶点v上d（v）＝偶数，则每个顶点v上有ω（G－v）≤d（v）／２。证明任取一顶点v。首先，v与G－v的每个分支之间至少有两边相连，假设····不然，设G－v的分支H与v之间的边数≤１。由于G连通，它们之间应恰只有一条边相连。令w为V（H）中唯一与v相邻的顶点。则由假设条件得，图H中恰只有一个奇点w，这与推论１３２矛盾。再注意到v与G－v的各分支之间总共有小于或等于d（v）条边相连（注意到：v可能与一些环相关联），得证。（图１５４）／／图１５３图１５４例１８　设一金库只有一个大门，其内部被分隔成一些小房间（把走廊、门厅等都看成房间）。各房间除了一个放有稀世大钻石的房间外，都有偶数个门（大门也是一个门）。则能撬开每个门的大盗一定可将钻石偷走。证明不计金库大门（则大门门厅也只有奇数个门），以金库的所有房间为顶点集作一图G，两顶点间用一边相连当且仅当对应的两个房间有一个门相连。则图G中恰只有与大门门厅及存放钻石的房间对应的两个顶点（设为x与y）为奇点，其余顶点都是偶点。我们的问题变成要证明任一图G中若恰只有两个奇点x与y，则G中一定存在（x，y）路。设若不然，则G不连通，且x与y在G的不同分支中。于是，G中包含x的分支，是一个只包含一个奇点的图，这与推论１３２相矛盾。／／例１９　任一ν≥３的简单、连通、非完全图G中，一定有三个顶点u，v，w，使得uv，vw∈E而uw∈／E证明由假设条件G中存在二不相邻顶点u与z，且u与z是连通的。令v与·１６· w为最短（u，z）路的第２与第３个顶点，则u，v，w即为所求。／／例１１０　ν≥２的图G中，若ε≤ν－２，则G不连通。（等价地，每个连通图G都·······有ε≥ν－１）·····证明对ν归纳。当ν＝２时，显然命题成立。假设对ν＜n（≥３）时命题都成立，而ν（G）＝n。由握手引理及ε≤ν－２易见，δ≤１。若δ＝０则命题成立，否则令u为G中度为１的顶点。由于ν（G－u）＝n－１＜n，且ε（G－u）＝ε（G）－１≤ν（G－u）－２，由归纳假设知，G－u不连通。但u在G中的度为１，因此G也不连通。／／（另一证明：当ε＝０时，显然命题成立。假设命题不成立，存在ν≥２的连通图···G满足ε≤ν－２。令G为这种图中边数为最少的。任取G中一边xy，由G的边数的最少性知，G－xy不连通，且恰有两个分支，设为G１及G２，它们的边数都少于ε（G）且都连通。因此由假设知ε（Gi）≥ν（Gi）－１，i＝１，２。从而ε（G）＝ε（G１）＋ε（G２）＋１≥ν（G）－１，矛盾。）（注：此为对ε归纳法的一种改头换面的写法）习题k１５１　证明：G中长为k的（vi，vj）途径的数目，就是A中的（i，j）元素，其中A为G的邻接矩阵。ν－１１５２　（１）证明：对简单图G有，ε＞G连通。２ν－１（２）对于ν＞１，试给出ε＝的不连通简单图。２１５３　（１）设有２n个交换台，每台至少与n个台有直通线路相连，则任二台间都可通话。（问题等价于：一个顶点数为２n的简单图G中，如果δ≥n，则G为连通图。）（２）当ν是偶数时，试给出一个不连通的（［ν／２］－１）正则简单图。c１５４　（１）G不连通G连通。c（２）证明或反证：G不连通G连通。１５５　对任意图G的任一边e，有ω（G）≤ω（G－e）≤ω（G）＋１。１５６　若图G中恰有两个奇点u与v，则G中一定有一（u，v）路。１５７　对任一图的任三个顶点u，v，w都有d（u，v）＋d（v，w）≥d（u，w）（即，满足三角不等式）。　　１５８　令u与v为连通图G的任二顶点，则G中存在一（u，v）途径W包含G的所有顶点。·１７· １６　圈一个长大于０的途径，如果起点与终点相同，就称为闭途径（ｃｌｏｓｅｄｗａｌｋ）。边····各不相同的闭途径称为闭迹（ｃｌｏｓｅｄｔｒａｉｌ）。顶点各不相同的闭迹称为圈（ｃｙｃｌｅ）。我们有时也将圈当作一个图或子图。长为k的圈称为k－圈（ｋｃｙｃｌｅ）。k为奇数或偶数的k圈分别称为奇圈（ｏｄｄｃｙｃｌｅ）或偶圈（ｅｖｅｎｃｙｃｌｅ）。１圈由一条环组成；２圈由两条平行边组成；我们还常把３圈称为三角形。例如图１６１中闭途径：CaAaC；及CbAfDiDfAaC。闭迹：CaAcBdAfDhDiDeC；及DhDiD。圈：CaAcBgDeC；及AdBcA等。定理１６１　图G为偶图，当且仅当G中不包含奇圈。证明　设G的２划分为（X，Y），由G的定义，G图１６１　G的任一圈中，X和Y的顶点一定交错出现，从而其长必为偶数。不妨设G为连通的（不然，只要证明定理对G的每个分支成立即可）。任取一顶点u，令X＝｛x∈V│d（u，x）＝偶数｝Y＝｛y∈V│d（u，y）＝奇数｝由于，易见，（X，Y）为集合V的２划分，只要再证X（和Y）都是G的独立集，即X（或Y）中任二顶点v，w都不相邻即可：令P与Q分别为最短（u，v）路与最短（u，w）路。设u′为P与Q的最后一个公共顶点；而P′与Q′分别为P的（u′，v）节与Q的（u′，w）节。则P′与Q′只有一公共顶点。又，由于P与Q的（u，u′）节的长相等，P′与Q′的长有相同的奇偶性，因此v与w不能相邻，不然－１v（P′）Q′wv将是G中的一奇圈，矛盾。／／图１６２以下例子很容易证明（习题），只要考虑其最长路即可，其结论可当命题直接·１８· 使用：例１１１　图G中δ≥２G中含圈。例１１２　简单图G，δ≥２G含长≥δ＋１的圈。习题１６１　若边e在G的一闭迹中，则e在G的一圈中。１６２　证明：（１）ε≥νG含圈。（２）ε≥ν＋４G含两个边不重的圈。１６３　证明：任一连通偶图G＝（X，Y，E）的２划分（X，Y）是唯一的。１６４　证明或反证：（１）G中有两个不同的（u，v）路，则G中包含圈。（２）G中有一闭途径，则G中包含圈。（３）G中有一长为奇数的闭途径，在则G中含一奇圈。１６５　设图G的顶点可用两种颜色进行着色，使每个顶点都至少与两个异色顶点相邻，则G中一定包含偶圈。１６６　５×５座位的教室中，不可能让每个学生都作一上下左右移动，使每个人都换了座位。１６７　简单图G，δ≥２G含长≥δ＋１的圈。２１６８　设简单图G中ε＝ν／４，则或者G含奇圈；或者GKν／２，ν／２。１６９　（１）设边a与边b共圈，边b与边c共圈，则边a与边c共圈。（２）由（１）证明E（G）可划分为一些互不相交的子集E１，E２，…，Eb，使每个G［Ei］中任二边共圈。１７　最短路问题如果在图G的每条边e上，都赋予一非负实数w（e），则称G为一赋权图（ｗｅｉｇｈｔｅｄｇｒａｐｈ）；w（e）称为边e的权（ｗｅｉｇｈｔ）。因此，w是定义在E（G）上的一个非负实函数：w：E（G）→Ｒ。例如，在通讯网中它可能是一条线路的建设费、维护费或租用费；在人际关系图中，它可能代表两人之间关系的紧密程度等等。对于赋权图G的子图H，称H中所有边的权的和w（H）＝∑w（e）为He∈E（H）的权。许多优化问题是要在赋权图中，寻找满足一定条件的子图，使它的权最小（最大）。图中距离的概念（其中每边的长为１），可以很自然地推广如下：当H为一条路P时，称w（P）为路P的长。特别地称最短（u，v）路的长为从顶点u到v的距·１９· 离，记为d（u，v）。本节我们所要考虑的问题，是对任意给定的一个赋权图G，及G中两个指定的顶点u０与v０，求出其最短（u０，v０）路。易见，只要考虑简单连通图的情形就够了。这里我们假定每边e的权w（e）都是大于０的实数。因为当一条边e＝uv的权为０时，我们可以把u和v合并成一个顶点。又，我们约定，边e∈／E（G）当且仅当w（e）＝∞。下面将要提到的Ｄｉｊｋｓｔｒａ（１９５９）算法，将求出从一指定顶点u０到G的其余所有顶点的最短路，而不仅仅是最短（u０，v０）路。珚珚对G的顶点真子集SV（G），及S＝V（G）－S，将u０∈S到S的距离定义为珚珚d（u０，S）＝ｍｉｎ｛d（u０，x）│x∈S｝珚珚设顶点v∈S使d（u０，v）＝d（u０，S），而P＝u０u１u２…ujv为最短（u０，v）路，则易见：（１）u０，u１，u２，…，uj∈S。（２）u０u１u２…uj是一最短（u０，uj）路。珚（３）d（u０，S）＝d（u０，v）＝d（u０，uj）＋w（ujv）＝ｍｉｎ｛d（u０，u）＋w（uv）｝。珚u∈S，v∈S算法的原理是逐步求出顶点序列u１，u２，u３，…使d（u０，u１）≤d（u０，u２）≤d（u０，u３）≤…记S０＝｛u０｝珚Sk＝｛u０，u１，…，uk｝，Sk＝V＼SkPk为最短（u０，uk）路，k＝１，２，…珚　　（１）求u１∈S０：使d（u０，u１）＝ｍｉｎ｛d（u０，u）＋w（uv）｝＝ｍｉｎ｛w（u０v）｝珚u∈S，v∈Sv∈S０００得S１＝S０∪｛u１｝，P１＝u０u１。（２）若已求得Sk１；d（u０，u１），…，d（u０，uk１）；及最短（u０，ui）路Pi，i＝１，２，…，珚k１（图１７１）。求uk∈Sk１，使珚d（u０，uk）＝d（u０，Sk１）＝ｍｉｎｍｉｎ｛d（u０，u）＋w（uv）｝珚u∈Sv∈Sk１k１＝ｍｉｎ｛l（v）｝珚v∈Sk１其中l（v）＝ｍｉｎ｛d（u０，u）＋w（uv）｝（）u∈Sk１即，首先对Sk１中每个v，按（）式求出l（v）。使l（v）达到最小的v就是uk，且这时有l（uk）＝d（u０，uk）。至此，得Sk＝Sk１∪｛uk｝；Pk＝Pjujuk，某j∈｛１，２，…，k１｝，uj·２０· 就是当v＝uk时使（）式右边达到最小的u∈Sk１。珚当进行下一步时，易见，对每个v∈Sk，我们无需再直接用（）式，重复通过Sk中的每个u去求l（v），只要通过uk更新（ｕｐｄａｔｅ）l（v）即可：l（v）←ｍｉｎ｛l（v），l（uk）＋w（ukv）｝下面的算法只求出从u０到其他各顶点之间的距离。若想求出从u０到其他各顶点··之间的最短路，只需按上述作一些改动即可···（图１．７．１）。图１７１Ｄｉｊｋｓｔｒａ算法（１）作为开始：l（u０）＝０，l（v）＝∞　　v≠u０；S０＝｛u０｝，k＝０　　（２）（这时已求出Sk＝｛u０，u１，…，uk｝，且对每个uj∈Sk，有l（uj）＝d（u０，uj））珚l（v）←ｍｉｎ｛l（v），l（uk）＋w（ukv）｝　　v∈Sk，再计算ｍｉｎ｛l（v）｝，设其最小值点为uk＋１，令Sk＋１＝Sk∪｛uk＋１｝　　（３）若k＝ν－１，停止；不然，令k←k＋１，并回到（２）。计算复杂性加法：ν（ν－１）／２比较：ν（ν－１）／２×２珚２v∈S：（ν－１）２总共为O（ν）。凡是时间复杂性为p（ν，ε）的算法（其中p（x，y）为一二元多项式），著名数学家ＪＥｄｍｏｎｄｓ给它取了一个名字，称为“好算法”（“ｇｏｏｄａｌｇｏｒｉｔｈｍ”）或多项式时间算法（ｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍ），以区别于指数型时间算法（ｅｘｐｏｎｅｎｔｉａｌｔｉｍｅnａｌｇｏｒｉｔｈｍ），即时间复杂性无法用输入长n的多项式作为其上界的算法，例如２，ｌｏｇn－６n等。在１０秒／步运算速度下，好算法与指数型时间算法的表现举例如下：复杂性n＝１０２０３０４０５０３n０００１秒０００８秒００２７秒００６４秒０１２５秒５n０１秒３２秒２４３秒１７分５２分n２０００１秒１０秒１７９分１２７天３５７年由上表可见，两种算法有天壤之别。上述算法中，若只关心求d（u０，v０），则算法进行到v０∈Sk时停止即可。在计算过程中，每步所得子图都是一棵树。因为每步都是在当时已经得到的子图（是树）上···增加一条边及一个顶点。因此该过程称为树生长过程（ｔｒｅｅｇｒｏｗｉｎｇｐｒｏｃｅｄｕｒｅ）。且·········２１· 在该树中的（u０，v）路，就是最短（u０，v）路。又，若要记录u０到每个顶点v的最短路，只要记录该路中u的前一个顶点（即该树中v的父亲，也就是使（）式达到最小的u）即可。图１７２展示了从u０到其余顶点的最短路的全过程，其中粗边为树边，每个顶点v上所标的数字即为当时的l（v）。图１７２习题１７１　描述一个算法以确定（１）一图的各个分支。（２）一图的围长（ｇｉｒｔｈ，即最短圈的长）。并说明你的算法好到什么程度。·２２· 第２章树在连通图中，树是最简单的，然而也是最重要的一种图。树的应用领域非常广泛，如计算机科学、生物学、晶体结构学、社会科学等。同时它也是图论的理论基础，由它自身或通过它可导出许多结果。２１　树和割边称边e为图G的割边（ｃｕｔｅｄｇｅ或ｂｒｉｄｇｅ），如果ω（G－e）＞ω（G）（即，ω（G－e）＝ω（G）＋１，参见习题１５５）。简言之，割边就是去掉后能使连通图（或不连通图的分支）变成不连通的一条边。反之，如果ω（G－e）＝ω（G），则称e为G的非割边。例如图２１１中，边bc，de及hi都是该图的割边，其他边都是该图的非割边。从图中我们发现，每条割边都不在任一圈中，而每条非割边都至少在一圈中。这结论是普遍成立的：图２１１定理２１１　e为G的非割边e在G的一圈中。（等价地，e为G的割边e不在G的任一圈中。）证明令e＝xy，则x与y在G的同一分支中。于是e为G的非割边ω（G－e）＝ω（G）x与y在G－e的同一分支中G－e中有（x，y）路G中有含e的圈。／／（另一证法：不妨设G连通（不然，只要考虑G中含e的分支即可。）　　设G的一条边e＝uv包含在G的一圈C中。考虑G中任二顶点x与y。令P为G中一（x，y）路。若e不在P上，则P仍是G－e中的一条（x，y）路；若e在P上，将P中的边e用C的不含e的（x，y）节代替，得到G－e中一条（x，y）途径，从而，由推论１５２，G－e中仍然存在一条（x，y）路。由x与y的任意性知，G－e仍然连通。因此e为G的非割边。　　设边e＝uv为G的非割边，则G－e仍然连通。令P为G－e中的一条（u，v）路，则e在G的圈P＋e中。／／）称不含圈的图为无圈图（ａｃｙｃｌｉｃｇｒａｐｈ）或林（ｆｏｒｅｓｔ）。称连通无圈图为树·２３· （ｔｒｅｅ）。树中度为１的顶点称为树叶（ｌｅａｆ）。例如，六个顶点上，总共有六棵不同构的树，如图２１２所示。图２１２定理２１２　连通图G为树，当且仅当G的每条边都是G的割边。证明注意到以下事实即可：G无圈G中每边不在任一圈中G中每边都是G的割边／／定理２１３　树中任二顶点间有唯一的路相连。证明反证，假设存在树T，其中存在二顶点u与v，其间有二不同（u，v）路P和Q相连。因P≠Q，一定存在，例如，P的一条边e＝xy，它不是Q的边。显然图P∪Q－e是连通的，从而其中包含一条（x，y）路W。于是W＋e是T中的一圈，这与T为无圈图相矛盾。／／注１　其实，在上述定理的证明中，由路的定义易见，（有相同的起点u和终点v的）两条不同的（u，v）路P及Q中，任一条的边集不会真包含另一条的边集（假设不然，例如设E（P）E（Q），则存在Q的一条边e，使E（P）E（Q－e），但Q－e中u与v不连通，因此不可能包含（u，v）路P，矛盾）。注２　以下结论一般是不成立的：图G中存在闭途径，则G中存在圈（例如，设图G就是一条边e＝xy，则xeyex就是G中的一条闭途径，但不是圈）。因此不能因为P∪Q为闭途径，而得出T中包含圈的结论。推论２１４　设G为无环图，则G是树G中任二顶点间有唯一的路相连证明　（习题）／／定理２１５　树T中ε＝ν－１。证明对ν进行归纳。当ν＝１时，T＝K１，结论成立。假设定理对小于ν个顶点的树成立，而T为ν（≥２）个顶点的树。任取T的一边uv。它是T中的一条路，由定理２１３知（或直接用定理２１２），T－uv不连通，且它恰有二分支（习题·２４· １５５），设为T１与T２。它们都是连通无圈图，因此都是树。又，它们的顶点数都小于ν。因此由归纳假设知ε（Tj）＝ν（Tj）－１　　j＝１，２所以ε（T）＝ε（T１）＋ε（T２）＋１＝ν（T１）＋ν（T２）－１＝ν（G）－１／／推论２１６　每棵非平凡树T至少有两个度为１的顶点。证明首先由于T为非平凡连通图，它的每一顶点的度大于等于１。设G中共有k个度为１顶点，由定理１３１及２１２知２ν－２＝∑d（v）＝k＋∑d（v）≥k＋２（ν－k）v∈Vd（v）≥２故有k≥２。／／例２１　证明恰只包含两个度为１顶点的树T是路。证明由定理２１３及１３１得２ν－２＝∑d（v）＝２＋∑d（v）≥２＋２（ν－２）v∈Vd（v）≥２所以∑d（v）＝２（ν－２）d（v）≥２因此连通图T中除了两个度为１的顶点外，其余的度都是２。这样的图，显然，只能···是一条路（可用对顶点数的归纳法加以证明）。／／一棵树T如果是G的生成子图，就称为G的生成树（ｓｐａｎｎｉｎｇｔｒｅｅ）。从任给的一个连通图G，可用以下两个方法，来求出其生成树T：···（１）求G的极小（ｍｉｎｉｍａｌ）连通生成子图T（即T为G的连通生成子图，但T······的任一真子图都不是G的连通生成子图）。由T的定义知，ω（T）＝１，且对T中每·······边e都有ω（T－e）＝２。从而T的每边为T的割边，故由定理２１２知T为树，且·为G的生成树。求T的具体做法如下：在保持连通性的前提下，逐步将G中可去的边去掉，直·········到不能再去掉为止。易见，这样求出的子图就是G的极小连通生成子图。又，所去······的边一定是当时（G的子图）的非割边，因此一定在G的一圈中。故每步至少破坏G的一圈。（参看图２１３中的上一排图）（２）求G的极大（ｍａｘｉｍａｌ）无圈子图T（即G的任一个子图H若为T的真母··图，则H一定含圈）。由定义，首先易见，T一定是G的生成子图（不然，往T中加·上G中不属于T的孤立顶点后仍然为无圈图，导致与T的极大性矛盾）。又，T一定是连通的。不然，由于G连通，G中一定存在一条边，设为e，其两端点在T的二不同分支中。从而T＋e仍是无圈图（因e是T＋e的割边，从而T＋e中无含e的圈），矛盾。故T为G的生成树。·２５·