第十一章图论及其应用初步new

《第十一章图论及其应用初步new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章图论及其应用初步[学习目的]1.了解图论中的一些与概念与基本性质；2.掌握图论中解决实际问题的一些基本思想方法（最短路、最小生成树、欧拉回路、中国邮递员问题、网络流理论及其算法等．图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博奕问题、棋盘上马的行走路线问题等．这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题．1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随

2、着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱．我们所学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后对工程技术有关学科的学习研究时，可以把图论的基本知识、方法作为工具．§11．1图论的基本概念[学习目标]1.会正确表述关于图的一些基本概念（如图、连通图、路、回路（圈）、树、

3、生成树、关联矩阵、邻接矩阵、独立集、覆盖集和控制集等）；2.会用图论的方法描述一些简单的实际问题．一、图的概念通常人们认为，前面我们所学过的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支．首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．它是数

4、学中经常采用的抽象直观思维方法的典型代表．图11-1图11-2一提到图论的起源，人们总要讲述早在1736年，欧拉就把所谓的哥尼斯堡7桥问题化为图论问题，1使其迎刃而解的事例．哥尼斯堡7桥问题是这样的：哥尼斯堡是一座城市，位于名叫普莱格尔的河上，河中有两个岛屿A与D．为了沟通城市交通，岛与岛及岛与岸之间架设了7座桥，如图11-1所示．现在的问题是，要从任何一地出发游历全城，是否能在每座桥只允许通过一次的前提下，最后又返回到原出发地？实际上，任何这样的尝试都没有成功．后来欧拉创造了一种图论的方法证明了哥尼斯堡7桥问题不可能有解．

5、方法如下：先将每块陆地用点来表示，分别为点A、B、C、D，将连接陆地之间的7座桥用连接相应点之间的线条来表示，就形成了一个图11-2．所谓哥尼斯堡7桥问题就变为：在图11-2中，从任意一点出发，能否用笔画过每条边一次且仅能画一次，最后又重新回到原出发点？由于每通过一个点时，必须经过两条边，即从一条边进入又从另一条边离开该点．因此如果7桥问题有解，则图11-2中与每个点相连的边必然都是偶数条，而图11-2中与每个点相连的边都是奇数条，因而哥尼斯堡7桥问题不可能有解．人们确信，这是最早利用图论分析和解决问题的范例之一．当然，图论

6、的发展，还是因为它在科学技术、经济运营中的大量应用而引起的，例如，电路理论中的基尔霍夫电流定理和电压定理只与电路的结构性质有关，因此任何一个具体的电路都可以抽象为一个“图”，如电路图11-3通常用图11-4表示其结构．图11-3图11-4图11-5直观地讲，画n个点，把其中的一些点用曲线或直线段连接起来，不考虑点的位置与连线的长短，这样所形成的点与线的关系结构就是一个图．也就是说，由点集合V和点与点之间的连线的集合E所组成的集合对（V，E）称为图，用G（V，E）来表示．V中的元素称为节点，E中的元素称为边．如图11-2中，节

7、点集为V={}ABCD，，，，边集合为E={eeeeeee,,,,,,}．节点集V与边集1234567合E均为有限的图称为有限图（本章只考虑有限图）．若各边都加上方向，则称为有向图，如图11-5所示．各边都没有方向的图成为无向图；有的边有方向，而有的边没有方向的图称为混合图．一般地说，连接两个节点的边可能不止一条，如图11-2中的边e1和e2都连接A与B，这样的边叫多重边．连接同一节点的边称为自圈．如无特别声明，本章所讨论的图均为没有自圈和多重边的所谓的简单图．两节点间有边相连时称此二节点相邻，每对节点都相邻的图称为完全图，

8、记成K或K(n=V)，例如nV图11-6中G，G，G都是K，并称G，G，G同构，记为G≅G≅G≅K．12351231235GGG123图11-6若V（G）=YUX，XIY=Φ，X⋅Y≠0，且X中和Y中均无邻接节点，则称G是二分图；2特别地，若X中的每一个节点与Y中的任何一个节点相邻，则称G