第四篇图论优秀PPT.ppt

《第四篇图论优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四篇图论优秀PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四篇图论第一页，本课件共有28页 第八章图论原理 8.1 图的基本概念 8.2 通路、回路与连通性 8.3 欧拉图 8.4 汉密尔顿图 8.5 图的矩阵表示法 第九章 常用图 9.1 树 9.2 平面图 9.3 两步图 第二页，本课件共有28页第八章 图论原理 8.1 图论基本概念一、图 远在18世纪就出现图论问题，如著名的哥尼斯堡桥问题。二、图的基本概念：图可由两部分组成：一部分是一些点，称其为结点；另一部分是连接这些点的线，称其为边。第三页，本课件共有28页定义1：图G是由非空结点集合V=v1,v2,vn以及边集合E=l1,l2,lm所组成。其中每条边可用一个结点对表示之，这样的一个图G

2、可用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，试将此事实用图的方第四页，本课件共有28页法表示之。利用图中边的有向和无向可将图分成两种类型：有向图和无向图。图G=V，E与G=V，E间如果有V V及E E，则称G是G的子图，如果进一步有E E，则称G是G的真子图。图G=V，E与G=V，E间如果有V=V，E E，则称G是G的生成子图。一个具有n个结点、m个边所组成的图第五页，本课件共

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的补图。第六页，本课件共有28页三、图的同构：四、图中结点的次数：定义3：在有向图中的结点v，以v为起点的边的条数叫v的引出次数，以v为终点的边的条数叫v的引入次数，v的引入次数与引出次数之和称为v的次数或全次数，记以：deg(v)；在无向图中

4、，结点v的次数或全次数是与v相关联的边的条数，也用deg(v)表示之。定理1：图G=V，E是一个（n，m）图，其中V=v1,v2,vn，此时有：第七页，本课件共有28页五、多重图和带权图：一个结点对间有多条边，这种边称为多重边。包含多重边的图称为多重图，而不含多重边的图则叫简单图。有时，在一个图中边的旁侧可附加一些数字以刻划此边的某些数量特性，叫做边的权，而此边叫有权边，具有有权边的图叫有权图，无有权边的图叫无权图。第八页，本课件共有28页8.2 通路、回路与连通性一、通路与回路：1.通路：设有有向图G=V，E，考虑G中边的序列:这个序列由 开始至 结束，其中间每条边的终点是下一条边的起点。此

5、边的序列可简写成：，在此序列中可以允许多次出现相同的结点与边第九页，本课件共有28页在此序列中除 及 外，中间每个结点均与其前后结点相邻接，这种边的序列叫图的通路。而 与 分别叫通路的起始结点与终止结点，通路中边的数目叫通路的长度。有向图中各边全不相同的通路叫简单通路，各点全不相同的通路叫基本通路。2.回路：图中一条通路如果其起始结点与终止结点相同则称此通路为回路。图中各第十页，本课件共有28页边全不相同的回路叫简单回路，各点全不相同的叫基本回路。定理1：一个有向（n,m）图中任何基本通路长度均小于或等于n-1，而任何基本回路长度均小于或等于n。3.可达性：定义1：从有向图的结点vi到另一结点

6、vj 间如果存在一条通路，则称从vi到vj是可达的。两结点间长度最短的通路叫短程线。而短程线的长度则称为从vi到vj间的距第十一页，本课件共有28页离，可用d(vi,vj)表示之。二、连通性：定义2：一个无向图G，如果它的任何两结点间均是可达的，则称图G为连通图；否则称为非连通图。定义3：一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图。定义4：一个有向连通图G如果其任何两结点间均是互相可达的则称图G是强连通的；如果其任何两结点间至少存在第十二页，本课件共有28页一向是可达的则称图G是单向连通的；如果忽略边的方向后其无向图是连通的，则称图G是弱连通的

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

8、回路称为哈密尔顿回路。具有这种回路的图叫哈密尔顿图。定义2：通过图G中每结点一次的通路（非回路）称为哈密尔顿通路。第十六页，本课件共有28页8.5 图的矩阵表示法一、有向图的邻接矩阵：1.定义：设有一个有向图G=V，E，其中：V=v1,v2,vn，E=l1,l2,lm，这时构成一矩阵：A=此矩阵称为图G的邻接矩阵。第十七页，本课件共有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)，试求此图的邻接矩阵。二、可达性矩阵：其中，给出了从 到 的所有长度为1至n的通路数目之

9、和，若 =0，则表示从 到 是不可达的，若 0，则表示从 到 是可达的。第十八页，本课件共有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)(v3,v1),(v4,v1)第十九页，本课件共有28页如果一个矩阵的元素均为0或1，矩阵运算中加法与乘法均对应于布尔加与布尔乘，此种

10、矩阵运算称为布尔矩阵运算，有：三、无向图的矩阵表示法：四、多重图及有权图的矩阵表示法：五、矩阵与图的连通性：对于有向图的强连通性。有向图G为强连通的充要条件是图的可达性矩阵P除对角线元素外所有元素均为1。对于单向连通性。有向图G为单向第二十页，本课件共有28页连通的充要条件是图G的可达性矩阵P及其转置矩阵经运算 ，P中除对角线元素外均为1。对于弱连通性。有向图为弱连通的充要条件是图G的邻接矩阵A及其转置矩阵经运算 ，A的可达性矩阵中除对角线元素外所有元素均为1。第二十一页，本课件共有28页第九章 常用图 9.1 树一、树及其基本性质：定义1：树是不包含回路的连通图。定理1：在(n,m)树中必有

11、m=n-1。定理2：具有两个结点以上的树必至少有两片叶子。定理3：图G是树的充要条件是图G的每对结点间只有一条通路。二、有向树：第二十二页，本课件共有28页三、二元树：定义5：一n个结点的外向树如满足：deg(vi)m，(i=1,2,n)，则称此外向树为m元树。四、生成树：由一个连通图G寻找它的生成树的过程是：在G中寻找基本回路，找到后在此回路中删除一边，并继续寻找，直至G中无基本回路出现为止。故由G求得生成树必须删除的边数为m-(n-1)=m-n+1，一个连通图G的生成第二十三页，本课件共有28页树不是唯一的。例1：求一带权连通图的最短树的方法克鲁斯卡尔算法。例2：设有5个城市v1,v2,v

12、3,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)=12试求出连接5个城市的且造价最低的铁路网。第二十四页，本课件共有28页例3：世界上六大城市之间的航线距离表如下（以100英里为1个单位），试求出连接此六个城市的最短距离的航线网。第二十五页，本课件共有28页9.2 平面图一、平面图的基本概念：定义6：一个图不管它的图形的几何形状如何改变，它们的边之间总有交叉现象出现，则称此图为非平面图，否则称为平面图。二、平面图的区域：定理4：设图G是一个（n,m）连通平面图，它的区域数为r，则此时有：n-m+r=2第二十六页，本课件共有28页 定理5：设图G是一个(n,m)连通平面图，且图G中无环，其边数大于1，则必有：m3n-6。第二十七页，本课件共有28页9.3 两步图定义7：设无向图G=V，E有两个V的子集V1，V2，它们具有满足：V1V2=V，V1V2=。图G的每一边e均有e=(vi,vj)，其中：viV1，vj V2，此时称图G为两步图。定理7：图G是一个两步图的充要条件是G的所有回路的长度为偶数。第二十八页，本课件共有28页