第十一章图论和其应用初步.pdf

第十一章 图论及其应用初步 [学习目的] 1. 了解图论中的一些与概念与基本性质； 2. 掌握图论中解决实际问题的一些基本思想方法（最短路、最小生成树、欧拉回路、中国邮递 员问题、网络流理论及其算法等． 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛 流传的一些游戏难题，如迷宫问题、博奕问题、棋盘上马的行走路线问题等． 这些古老的难题，当时 吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世 界）数学难题． 1847 年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在 解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来 越大的作用．在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及 经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱．我们所 学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后对工程技术有关学 科的学习研究时，可以把图论的基本知识、方法作为工具． §11．1 图论的基本概念 [学习目标] 1. 会正确表述关于图的一些基本概念（如图、连通图、路、回路（圈）、树、生成树、关联矩 阵、邻接矩阵、独立集、覆盖集和控制集等）； 2. 会用图论的方法描述一些简单的实际问题． 一、图 的 概 念 通常人们认为，前面我们所学过的微积分是属于连续数学，而本章所要讨论的图论是离散数学的 重要分支． 首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体 的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对 象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构， 图论中的“图”则描述一些特定的事物和这些事物之间的联系．它是数学中经常采用的抽象直观思维 方法的典型代表． 图 11-1 图 11-2 一提到图论的起源，人们总要讲述早在 1736 年，欧拉就把所谓的哥尼斯堡 7 桥问题化为图论问题， 1 使其迎刃而解的事例．哥尼斯堡 7 桥问题是这样的：哥尼斯堡是一座城市，位于名叫普莱格尔的河上， 河中有两个岛屿 A 与 D ．为了沟通城市交通，岛与岛及岛与岸之间架设了7 座桥，如图 11-1 所示．现 在的问题是，要从任何一地出发游历全城，是否能在每座桥只允许通过一次的前提下，最后又返回到 原出发地？实际上，任何这样的尝试都没有成功．后来欧拉创造了一种图论的方法证明了哥尼斯堡 7 桥问题不可能有解．方法如下：先将每块陆地用点来表示，分别为点 A 、B 、C、D ，将连接陆地之间 的 7 座桥用连接相应点之间的线条来表示，就形成了一个图 11-2．所谓哥尼斯堡7 桥问题就变为：在 图 11-2 中，从任意一点出发，能否用笔画过每条边一次且仅能画一次，最后又重新回到原出发点？ 由于每通过一个点时，必须经过两条边，即从一条边进入又从另一条边离开该点．因此如果7 桥 问题有解，则图 11-2 中与每个点相连的边必然都是偶数条，而图 11-2 中与每个点相连的边都是奇数 条，因而哥尼斯堡 7 桥问题不可能有解．人们确信，这是最早利用图论分析和解决问题的范例之一．当 然，图论的发展，还是因为它在科学技术、经济运营中的大量应用而引起的，例如，电路理论中的基 尔霍夫电流定理和电压定理只与电路的结构性质有关，因此任何一个具体的电路都可以抽象为一个 “图”，如电路图 11-3 通常用图 11-4 表示其结构． 图11-3 图11-4 图11-5 直观地讲，画 n 个点，把其中的一些点用曲线或直线段连接起来，不考虑点的位置与连线的长短， 这样所形成的点与线的关系结构就是一个图．也就是说，由点集合 V 和点与点之间的连线的集合 E 所 组成的集合对（V ，E ）称为图，用G （V ，E