电子科大张先迪李正良图论及其应用习题解答.docxVIP

《图论及其应用》习题课教材 杨春编 电子科技大学应用数学学院 内容提要 本书主要对张先迪等编的研究生《胎论及其应用》教 材的习题进行解答。该书可作为研究生图论教学的参考教材 。 言前现实生活中，许多问题 都可归结为一个山点和线组成的图形的问题。例如，山点代表车站，线代表铁路线的铁路网络盟 点代表路口，线代表街迫的城市交通图； 点代表忤逆接头， 线代表符迫的自来水供水系统； 点代 表电路的结点，线代表结点间的电气元件的电网络图； 点 代衣网络的结点，线代农通讯线的通讯网络、计殍机网络等等。图论正是研究这 些山点和线组成的“图形” 问题 的一门学科。 言 前 图论起源T 18 世纪， 其第一篇论文是山欧拉 ( Euler, 1707一1782 ) 千 1736 年所亢成。 这篇论文解决了一个当时还没有解决的著名问题一哥尼斯堡 ( Konjgsberg ) 七桥问题（见第四京）。这篇论文也使欧拉成为f 附论和拓 扑学的创始人。阳论诞生后，特 别是近三十年来发展十分迅速， 府用也十分广泛。其应用已涉及物理学｀化学、运纷学、计算机科学、信息论、控制论、阿络理论、社会科学、以及竹理科学等诸多领域 。山T图论与计算机科学紧密相联系， 近若干年来，在计符机科学、计算机网络的迅猛发展下，更拓展了招论的应用发展牛间。在计炸机的许多领域内， 它都占有一J-,们之地。OO论在矩阵论、群论等具它一些数学分支中，也 有其前胜的应用。 张先迪等编的《OO论及其峦用》 一书和选了内容广泛、难度各易的习题， 其中的大多数习题都是对图论的进一步学习是应当掌握的。本书依序将该书的重要内容摘要列出，井将全部习题给出了详细解答。本书所涉及到的术语、符号与该书一致。 有些习题存在多种解法， 在一般估况下， 只 给出一种解法供参考。 山千编者水平有限及编写时的的匆忙， 书中难免出现一些缺点和错误，恳诮同行专家及读者提市空贵怒见和建议， 以使本书得以不断改进和完忤。 编者 2004. 7 目 录 第一菜 图的基本概念 l. l 图和简单图 子图与拍的运算 路与图的连通性 最短路及其纾法 图的代数表示及其特征 L.6 极 OO 1.7 交阳与团钳习题 I 第二芘 树 树的概念与性质 树的中心与形心 生成树 最小生成树习题 2 第三芫 图的连通度 割边、割点和块 连通度 应用 图的宽距离和宽百径习题 3 第四齐 欧拉图与哈密尔顿图 欧拉图 高效率计莽机岐轮的设计 中国邮路问题 哈密尔顿图 度极大非哈密尔顿招 旅行售货员问题 超哈密尔顿图 E 招和 H 的联系 无限附中的 欧拉，哈密尔顿问题习题 4 第五菜 匹配与因子分觥 匹配 偶图的 匹配 与器 癌 Tune 定理与亢 美匹配 因子分解 最优匹配与匈牙利殍法 匹配在矩阵理论中的应用习题 5 第六章 平面图 平面团 一些特殊平面图及平面招的对偶图 平面图的判定及涉及半面性的不变杂 平面性饵法习题 6 第七慈 图的若色 图的边心色 顶点春色 与色数有关的几类图 完美图 若色的 计数 ， 色多项式习题 2 Lise 3行色 企若色 着色的应用习题 7 第八:et Ramsey 定理 独立共和稷盖 Ramsey 定理 )义Ramsey 数 应用习题 8 笫一章图的基本概念 §1. 1 图和简单图 定义 1 一个图G 定义为一个有序对( V, E) , 记为 G = (V, ￡), 其中 ( 1 ) V 是一个非空朵合，称 为顶点负或边北 ， 其元素称为顶点或点 ； E 是由 V 中的点组成的无序点对构成的共合， 称为边共， 其元素称为边， 且同一点对在 E 中可出现多次。 图 G 的顶点共也记为 V(G), 边某也记为E(G) 。顶点栠和边媒都有限的图称为有限图。只有一个顶点而无边的图称为平凡图。具他所有的图都称为非平凡图。边婓为空的 伤称为 空图。附 G 的顶点数（或阶数）和边数可分别用符号n(G) 和 m(G) 表示。连接两个相同顶点的边 的条数， 叫做边的重数。谊数大于 I 的边称为重边。端点狱合为一点的边称为环。既没有环也没有币边的图称为简单图。其他所有的图都称为复合图。 边记为II V, 也可记 UV 为 e, 即e = UV。 此时称u 和 v 是 e 的端点， 并 称 u 和 v 相邻， 11 ( 或 v)与 e 相关联。沾两条边有一个共同的端点，则称这两条边相邻 。若用小圆点代表点， 连线代表边，则 可将一个招用“ 招形 ”来表 示。 定义2 设有两个图G1 ;::; (Vi.E1) 和 G2 :::; CV2, ￡2), 若存共顶点染合之间存在双射， 即存 在一－对 应的 关系， 使得边之间有如下的关系： 设从臼 生 ， V1 臼 I分， Ui, V1 E V