图论第一章课后习题解答.pdfVIP

《图论及其应用》习题课教材 杨春编 电子科技大学应用数学学院 内容提要 本书主要对张先迪等编的研究生《图论及其应用》教材的习题进行解答。 该书可作为研究生图论教学的参考教材。 前 言 现实生活中，许多问题都可归结为一个由点和线组成的图形的问题。例如，由点代表车 站，线代表铁路线的铁路网络图；点代表路口，线代表街道的城市交通图；点代表管道接头， 线代表管道的自来水供水系统；点代表电路的结点，线代表结点间的电气元件的电网络图； 点代表网络的结点，线代表通讯线的通讯网络、计算机网络等等。图论正是研究这些由点和 线组成的“图形”问题的一门学科。 图论起源于 18 世纪，其第一篇论文是由欧拉（Euler ，1707—1782）于 1736 年所完成。 这篇论文解决了一个当时还没有解决的著名问题—哥尼斯堡（K?nigsberg ）七桥问题（见第 四章）。这篇论文也使欧拉成为了图论和拓扑学的创始人。图论诞生后，特别是近三十年来 发展十分迅速，应用也十分广泛。其应用已涉及物理学、化学、运筹学、计算机科学、信息 论、控制论、网络理论、社会科学、以及管理科学等诸多领域。由于图论与计算机科学紧密 相联系，近若干年来，在计算机科学、计算机网络的迅猛发展下，更拓展了图论的应用发展 空间。在计算机的许多领域内，它都占有一席之地。图论在矩阵论、群论等其它一些数学分 支中，也有其重要的应用。 张先迪等编的《图论及其应用》一书精选了内容广泛、难度各易的习题，其中的大多数 习题都是对图论的进一步学习是应当掌握的。本书依序将该书的重要内容摘要列出，并将全 部习题给出了详细解答。本书所涉及到的术语、符号与该书一致。 有些习题存在多种解法，在一般情况下，只给出一种解法供参考。 由于编者水平有限及编写时间的匆忙，书中难免出现一些缺点和错误，恳请同行专家及 读者提出宝贵意见和建议，以使本书得以不断改进和完善。 编 者 2004 ．7 目 录 第一章 图的基本概念 1.1 图和简单图 1.2 子图与图的运算 1.3 路与图的连通性 1.4 最短路及其算法 1.5 图的代数表示及其特征 1.6 极图 1.7 交图与团图 习题 1 第二章 树 2.1 树的概念与性质 2.2 树的中心与形心 2.3 生成树 2.4 最小生成树 习题 2 第三章 图的连通度 3.1 割边、割点和块 3.2 连通度 3.3 应用 3.4 图的宽距离和宽直径 习题 3 第四章 欧拉图与哈密尔顿图 4.1 欧拉图 4.2 高效率计算机鼓轮的设计 4.3 中国邮路问题 4.4 哈密尔顿图 4.5 度极大非哈密尔顿图 4.6 旅行售货员问题 4.7 超哈密尔顿图 4.8 E 图和H 图的联系 4.9 无限图中的欧拉,哈密尔顿问题 习题4 第五章 匹配与因子分解 5.1 匹配 5.2 偶图的匹配与覆盖