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

《第十一章图论及其应用初步》由会员分享，可在线阅读，更多相关《第十一章图论及其应用初步（7页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、描述一些特定的事物和这些事物之间的联系它是数学中经常采用的抽象直观思维 方法的典型代表 图 11-1 图 11-2 一提到图论的起源， 人们总要讲述早在 1736 年， 欧拉就把所谓的哥尼斯堡 7 桥问题化为图论问题， 2 使其迎刃而解的事例哥尼斯堡 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 中，节点集为 V= ABCD， ，

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

8、 中 1 G， 2 G， 3 G都是 5 K，并称 1 G， 2 G， 3 G同构，记为 5321 KGGG 1 G 2 G 3 G 图 11-6 若 V（G）=YUX，XIY=，0 YX，且 X 中和 Y 中均无邻接节点，则称 G 是二分图； 3 特别地， 若 X 中的每一个节点与 Y 中的任何一个节点相邻， 则称 G 是二分图， 记成 YX K , ， 下图 11-7 中的 1 G、 2 G均是 3 , 3 K 1 G 2 G 图 11-7 图 11-8 设( )GVv是( )GEe的端点，则称 v 与 e 相关联，与节点 v 关联的边的条数叫做该节点的度 数，记做 d(v)，容易证明 )

9、(2)( )( GEvd GVv = 由上公式可知奇次节点的总数是偶数 在无向图中前后相继连接的一串边的集合称为路在有向图中，顺向的首尾相接的一串有向边的 集合称为有向路通常用顺次的节点或边来表示路或有向路，如图 11-8 中，e e e 124 , 为一条路， 该路也可用v vv v 1235 ,来表示起点与终点为同一节点的路称为回路（或圈） 如果一个图中，任 意两个节点之间都存在一条路与之相连，称这种图为连通图 二、图的邻接矩阵和关联矩阵二、图的邻接矩阵和关联矩阵 由于一个图的节点之间的邻接关系和边与点的关联关系都是唯一确定的，为此我们引入图的邻接 矩阵和关联矩阵的概念 设图 G 有 n

10、个节点 n vvv, 21 L，令() nn ji aGA =)(，其中 = 不关联与节点若节点 关联与节点若节点 ij ij ji vv vv a , 0 , 1 则称由元素 ji a（i，j=1，2，n）构成的一个 nn 方阵)(GA为图 G 的邻接矩阵 设图 G 有 n 个节点 n vvv, 21 L和 m 条边 m eee, 21 L，令 B(G)=() mn ji b ，其中 = 不关联与节点若 关联与节点若边 ij ij ji ve ve b , 0 , 1 则称由元素 ji b（i=1，2，n；j=1，2，m）构成的一个 nm 矩阵)(GB为图 G 的关联矩阵 例1 求图 11-

11、9 所示的图 G 的邻接矩阵和关联矩阵 解：图 G 的邻接矩阵为 54321 vvvvv 4 = 11001 10111 01010 01101 11010 )( 5 4 3 2 1 v v v v v GA 图 11-9 用行表示图 G 的节点，列表示 G 的边，则图 G 的关联矩阵为 7654321 eeeeeee = 0011000 1101100 0000110 1000011 0110001 )( 5 4 3 2 1 v v v v v GB 其中，矩阵的第 1 行元素中的 1 表示有相应的边与节点 1 v关联，也就是说从矩阵的元素 1 可以看出与 节点 1 v关联的边集为 S(1)

12、= 651 ,eee， 同样第 2 行中的 1 表示与节点 2 v关联的边， 即与节点 2 v关 联的边集为 S(2)= 721 ,eee，等等一个图的关联矩阵的行刻画该图相应节点的关联集，因此， 关联矩阵的 n 行，给出了一个图的所有节点的关联集关联矩阵的列表示图的边，因为每一条边有两 个端点，所以，在关联矩阵的每一列中有两个 1，其余的元素均为零 可以证明，n 阶连通图 G 的关联矩阵的秩为 n-1 三、树与图的生成树 若一个连通图中不存在任何回路，则称为树（如图 11-10 所示） 由树的定义，直接得下列性质： （1）树中任意两节点之间至多只有一条边： （2）树中边数比节点数少 1； （

13、3）树中任意去掉一条边，就变为不连通图； （4）树中任意添加一条边，就会构成一个回路 图 11-10 图 11-11 不难看出，任意一个连通图或者就是一个树，或者去掉一些边后形成一个树一个连通图去掉一 些边后形成的树称之为该连通图的生成树一般来说，一个连通图的生成树可能不止一个 5 求一个连通图的生成树有一个简单算法，这个算法就是在一个连通图中破掉所有的回路，剩下不 含回路的连通图就是原图一个生成树， 这个算法叫做 “破圈法” 例如， 在图 11-9 的回路 732 ,eee 中去掉 2 e边，在回路 761 ,eee中去掉 7 e边，在回路 546 ,eee中去掉 4 e边，余下的边集 65

14、31 ,eeee就构成图 11-9 的一个生成树，如图 11-11 所示 也可以用下面的算法来构造连通图的生成树 在图 G 中任意取一条边 1 e，找一条不与 1 e构成回路的边 2 e，然后再找一条不与 1 e， 2 e构成回 路的边 3 e，这样继续下去，直到这种过程不能进行，这时所得到的图 G 就是一个生成树这种算法我 们称之为“避圈法” 例 2 一个树有个节点度数为 2，个节点度数为 3，个节点度数为 4，问它有几个度数为 1 的节点？ 解：我们知道一个有限图中，各点的度数总和是边数的 2 倍；而树中的边数为节点数减 1 根据这两点，可知树中各节点的度数总和=2（树中节点数-1），设度

15、数为 1 的节点有 x 个，于是 22+3+34+x=2（2+1+3+x-1） 解得 x=9 上例可推广为“一个树有 n2个节点度数为 2，n3个节点度数为 3，nk个节点度数为 k，问它有 几个度数为 1 的节点？”请同学们思考 四、独立集 覆盖与控制集 若图 G 的节点集 V 的子集 S 中的任何节点之间都不相邻，则称 S 为图 G 的独立集，节点个数最 多的独立集称为最大独立集图 G 的最大独立集中节点的个数称为图 G 的独立数 若一个图 G 的每条边都至少有一个端点在它的节点集 V 的某个子集 K 之内，则称 K 为图 G 的覆 盖图 G 中含节点最少的覆盖称为图 G 的最小覆盖图 G 的最小覆盖中节点的个数称为图 G 的覆盖 数容易看出最小覆盖与最大独立集是互补关系 若一个图 G 的每个节点或者直接属于 G 的节点集 V 的某个子集 C，或它的邻边的另一个端点属 于 C，则 C 称为图 G 的控制集含节点最少的控制集称为最小控制集图 G 的最小控制集中节点的 个数称为图 G 的控制数