第四篇图论精品课件

1、第四篇图论第1页，共28页，2022年，5月20日，3点28分，星期二 第八章图论原理 8.1 图的基本概念 8.2 通路、回路与连通性 8.3 欧拉图 8.4 汉密尔顿图 8.5 图的矩阵表示法 第九章 常用图 9.1 树 9.2 平面图 9.3 两步图 第2页，共28页，2022年，5月20日，3点28分，星期二第八章 图论原理 8.1 图论基本概念一、图 远在18世纪就出现图论问题，如著名的哥尼斯堡桥问题。二、图的基本概念： 图可由两部分组成：一部分是一些点，称其为结点；另一部分是连接这些点的线，称其为边。第3页，共28页，2022年，5月20日，3点28分，星期二定义1：图G是由非空结

2、点集合V=v1,v2,vn以及边集合E=l1,l2,lm所组成。其中每条边可用一个结点对表示之，这样的一个图G可用G=V，E表示。例1：有四个城市：v1,v2,v3,v4，其中v1与v2间；v1与v4间；v2与v3间有直达长话线路相连，试将此事实用图的方法表示之。例2：有四个程序p1,p2,p3,p4，它们间有一些调用关系：p1能调用p2；p2能调用p3；p2能调用p4，试将此事实用图的方第4页，共28页，2022年，5月20日，3点28分，星期二法表示之。 利用图中边的有向和无向可将图分成两种类型：有向图和无向图。 图G=V，E与G=V，E间如果有V V及E E，则称G是G的子图，如果进一步

3、有E E，则称G是G的真子图。 图G=V，E与G=V，E间如果有V=V，E E，则称G是G的生成子图。 一个具有n个结点、m个边所组成的图第5页，共28页，2022年，5月20日，3点28分，星期二称为(n,m)图。如果图G是一个(n,0)图则称此图为零图。特别地，G是一个(1,0)图则称为平凡图。 一(n,m)图G如果其n个结点（n2）中的每个点均与其余n-1个结点邻接，则这样的图称为完全图。在完全图中：m=n(n-1)/2。 可由完全图引出一个图的补图的概念：设有一图G=V，E，对图 G=V，E如果有G=V，EE是完全图且EE=，则称G是G的补图。第6页，共28页，2022年，5月20日，

4、3点28分，星期二三、图的同构：四、图中结点的次数： 定义3：在有向图中的结点v，以v为起点的边的条数叫v的引出次数，以v为终点的边的条数叫v的引入次数，v的引入次数与引出次数之和称为v的次数或全次数，记以：deg(v) ；在无向图中，结点v的次数或全次数是与v相关联的边的条数，也用deg(v)表示之。 定理1：图G=V，E是一个（n，m）图，其中V=v1,v2, ,vn，此时有：第7页，共28页，2022年，5月20日，3点28分，星期二五、多重图和带权图： 一个结点对间有多条边，这种边称为多重边。包含多重边的图称为多重图，而不含多重边的图则叫简单图。 有时，在一个图中边的旁侧可附加一些数字

5、以刻划此边的某些数量特性，叫做边的权，而此边叫有权边，具有有权边的图叫有权图，无有权边的图叫无权图。第8页，共28页，2022年，5月20日，3点28分，星期二8.2 通路、回路与连通性一、通路与回路： 1.通路： 设有有向图G=V，E，考虑G中边的序列:这个序列由 开始至 结束，其中间每条边的终点是下一条边的起点。此边的序列可简写成： ，在此序列中可以允许多次出现相同的结点与边第9页，共28页，2022年，5月20日，3点28分，星期二在此序列中除 及 外，中间每个结点均与其前后结点相邻接，这种边的序列叫图的通路。而 与 分别叫通路的起始结点与终止结点，通路中边的数目叫通路的长度。 有向图中

6、各边全不相同的通路叫简单通路，各点全不相同的通路叫基本通路。 2.回路： 图中一条通路如果其起始结点与终止结点相同则称此通路为回路。图中各第10页，共28页，2022年，5月20日，3点28分，星期二边全不相同的回路叫简单回路，各点全不相同的叫基本回路。 定理1：一个有向（n,m）图中任何基本通路长度均小于或等于n-1，而任何基本回路长度均小于或等于n。 3.可达性：定义1：从有向图的结点vi到另一结点vj 间如果存在一条通路，则称从vi到vj是可达的。 两结点间长度最短的通路叫短程线。而短程线的长度则称为从vi到vj间的距第11页，共28页，2022年，5月20日，3点28分，星期二离，可用

7、d(vi,vj)表示之。二、连通性： 定义2：一个无向图G，如果它的任何两结点间均是可达的，则称图G为连通图；否则称为非连通图。 定义3：一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图。 定义4：一个有向连通图G如果其任何两结点间均是互相可达的则称图G是强连通的；如果其任何两结点间至少存在第12页，共28页，2022年，5月20日，3点28分，星期二一向是可达的则称图G是单向连通的；如果忽略边的方向后其无向图是连通的，则称图G是弱连通的。第13页，共28页，2022年，5月20日，3点28分，星期二8.3 欧 拉 图 定义1：图G的一个回路，若它通

8、过G中的每条边一次，这样的回路称为欧拉回路，具有这种回路的图叫欧拉图。 定理1：无向连通图G是欧拉图的充分必要条件是G的每个结点均具有偶次数。 定义2：通过图G中每条边一次的通路（非回路）称为欧拉通路。第14页，共28页，2022年，5月20日，3点28分，星期二定理2 vi与vj间存在欧拉通路的充分必要条件是G中vi与vj的次数均为奇数而其他结点的次数为偶数。 第15页，共28页，2022年，5月20日，3点28分，星期二8.4 哈密尔顿图 所谓哈密尔顿回路，起源于一种游戏，它是由英国数学家哈密尔顿于1859年提出，这种游戏叫周游世界游戏。 定义1：图G的一个回路若它通过G中每个点一次，这样

9、的回路称为哈密尔顿回路。具有这种回路的图叫哈密尔顿图。 定义2：通过图G中每结点一次的通路（非回路）称为哈密尔顿通路。第16页，共28页，2022年，5月20日，3点28分，星期二8.5 图的矩阵表示法一、有向图的邻接矩阵： 1.定义： 设有一个有向图G=V，E，其中：V=v1,v2, ,vn，E=l1,l2, ,lm，这时构成一矩阵：A=此矩阵称为图G的邻接矩阵。第17页，共28页，2022年，5月20日，3点28分，星期二 2.特征： 例1：设一图G=V，E中，V=v1,v2,v3,v4,v5，E=(v1,v2),(v2,v1),(v2,v2),(v3,v2),(v4,v5),(v5,v4

10、)，试求此图的邻接矩阵。二、可达性矩阵： 其中， 给出了从 到 的所有长度为1至n的通路数目之和，若 =0，则表示从 到 是不可达的，若 0，则表示从 到 是可达的。第18页，共28页，2022年，5月20日，3点28分，星期二 讨论可达性时，我们感兴趣的仅仅是从 到 是否有通路相联，而并不关心通路的数量。故可对 进行适当的改造，得P= 其中当 =0时令 =0，当 0时令 =1。矩阵P反映了图G的各结点间的可达性，故叫G的可达性矩阵或通路矩阵。例2：求图G=V，E的可达性矩阵，其中：V=v1,v2,v3,v4，E=(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4)

11、(v3,v1),(v4,v1)第19页，共28页，2022年，5月20日，3点28分，星期二如果一个矩阵的元素均为0或1，矩阵运算中加法与乘法均对应于布尔加与布尔乘，此种矩阵运算称为布尔矩阵运算，有：三、无向图的矩阵表示法：四、多重图及有权图的矩阵表示法：五、矩阵与图的连通性： 对于有向图的强连通性。有向图G为强连通的充要条件是图的可达性矩阵P除对角线元素外所有元素均为1。 对于单向连通性。有向图G为单向第20页，共28页，2022年，5月20日，3点28分，星期二连通的充要条件是图G的可达性矩阵P及其转置矩阵经运算 ，P中除对角线元素外均为1。 对于弱连通性。有向图为弱连通的充要条件是图G的

12、邻接矩阵A及其转置矩阵经运算 ，A的可达性矩阵中除对角线元素外所有元素均为1。第21页，共28页，2022年，5月20日，3点28分，星期二第九章 常用图 9.1 树一、树及其基本性质： 定义1：树是不包含回路的连通图。 定理1：在(n,m)树中必有m=n-1。 定理2：具有两个结点以上的树必至少有两片叶子。 定理3：图G是树的充要条件是图G的每对结点间只有一条通路。二、有向树：第22页，共28页，2022年，5月20日，3点28分，星期二三、二元树： 定义5：一n个结点的外向树如满足：deg(vi)m，(i=1,2,n)，则称此外向树为m元树。四、生成树： 由一个连通图G寻找它的生成树的过程

13、是：在G中寻找基本回路，找到后在此回路中删除一边，并继续寻找，直至G中无基本回路出现为止。 故由G求得生成树必须删除的边数为m-(n-1)=m-n+1，一个连通图G的生成第23页，共28页，2022年，5月20日，3点28分，星期二树不是唯一的。例1： 求一带权连通图的最短树的方法克鲁斯卡尔算法。例2：设有5个城市v1,v2,v3,v4,v5，任意两城市之间铁路造价如下：（以百万元为单位） (v1,v2)=4,(v1,v3)=7,(v1,v4)=16 (v1,v5)=10,(v2,v3)=13, (v2,v4)=8 (v2,v5)=17,(v3,v4)=3, (v3,v5)=10 (v4,v5

14、)=12试求出连接5个城市的且造价最低的铁路网。第24页，共28页，2022年，5月20日，3点28分，星期二例3：世界上六大城市之间的航线距离表如下（以100英里为1个单位），试求出连接此六个城市的最短距离的航线网。第25页，共28页，2022年，5月20日，3点28分，星期二9.2 平面图一、平面图的基本概念： 定义6：一个图不管它的图形的几何形状如何改变，它们的边之间总有交叉现象出现，则称此图为非平面图，否则称为平面图。二、平面图的区域： 定理4：设图G是一个（n,m）连通平面图，它的区域数为r，则此时有：n-m+r=2第26页，共28页，2022年，5月20日，3点28分，星期二 定理5：设图G是一个(n,m)连