图论模型基础幻灯片.ppt

《图论模型基础幻灯片.ppt》由会员分享，可在线阅读，更多相关《图论模型基础幻灯片.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论模型基础图论模型基础图论模型基础图论模型基础第1页，共78页，编辑于2022年，星期五1.图论的基本概念图论的基本概念1)图的概念图的概念2)赋权图与子图赋权图与子图3)图的矩阵表示图的矩阵表示4)图的顶点度图的顶点度5)路和连通路和连通第2页，共78页，编辑于2022年，星期五1)图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中:其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|,用用来表示；来表示；图

2、的边的数目图的边的数目|E(G)|用用 来表示来表示.也用也用来表示边来表示边是非空有限集，称为是非空有限集，称为顶顶点集点集，1)2)E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对表示图，表示图，简记简记 用用第3页，共78页，编辑于2022年，星期五 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图.只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图.第4页，共78页，编辑于2022年，星期五 定义若若图图G中的边均为有序偶对中的边均为有序偶

3、对,称称G为为有向有向边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称图图.称边称边为为有向边有向边或或弧弧,称称是从是从连接连接，称，称 为为e的的尾尾，称，称 为为e的的头头.若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称为为e的的端点端点.既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图.第5页，共78页，编辑于2022年，星期五 常用术语常用术语1)边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点

4、 点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环，端点不相同的边称为端点不相同的边称为连杆连杆.4)若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 第6页，共78页，编辑于2022年，星期五 常用术语常用术语6)任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图.记为记为Kv.7)若若 ，且且X 中任意两顶点不中任意两顶点不，相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则

5、称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)8)图图 叫做叫做星星.二部图二部图第7页，共78页，编辑于2022年，星期五2)2)赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图.定义定义 设设 和和 是两个图是两个图.1)若若 ,称称 是是 的一个的一个子图子图,记记 2)若若 ，则称，则称 是是 的的生成子图

6、生成子图.3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 为为 的的由由 导出的子图导出的子图，记为，记为 .4)若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图，记为，记为 .第8页，共78页，编辑于2022年，星期五 3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 4)若若 ，且，

7、且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图，记为，记为 .为为 的的由由 导出的子图导出的子图，记为，记为 .第9页，共78页，编辑于2022年，星期五3)3)图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1)对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中：(以下均假设图为简单图以下均假设图为简单图).第10页，共78页，编辑于2022年，星期五2)对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中：第11页，共78页，编辑于2022年，星期五其中：其中：3)对有向赋权

8、图对有向赋权图 ,其邻接矩阵其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义.第12页，共78页，编辑于2022年，星期五关联矩阵关联矩阵 1)对无向图对无向图 ，其关联矩阵，其关联矩阵 ,其中：其中：第13页，共78页，编辑于2022年，星期五2)对有向图对有向图 ，其关联矩阵，其关联矩阵 ,其中：其中：第14页，共78页，编辑于2022年，星期五4)图的顶点度图的顶点度定义定义 1)在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数

9、的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2)在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d-(v).称称d(v)=d+(v)+d-(v)为顶点为顶点v的的 度度或或次数次数定理定理的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点第15页，共78页，编辑于2022年，星期五5)路和连通路和连通 定义定义1)无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列

10、一个有限非空序列 ，它的项交替，它的项交替 地为顶点和边，使得对地为顶点和边，使得对 ，的端点是的端点是 和和 ,称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径.整整数数k称为称为W的的长长.顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点,而而 称为称为W的的内部顶点内部顶点.2)若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链.3)若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径.一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路记为记为第16页，共78页，编

11、辑于2022年，星期五 定义定义 1)途径途径 中由相继项构成子序列中由相继项构成子序列 称为途径称为途径W的的节节.2)起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径.3)起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck.4)若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通.5)若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,v)路的长；若没路的长；若没没有路连接没有路

12、连接u和和v，则定义为无穷大，则定义为无穷大.第17页，共78页，编辑于2022年，星期五 6)图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 7)对于有向图对于有向图G，若，若 ，且，且 有有 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈.头头 和尾和尾 ，则称，则称W为为有向途径有向途径.例例 在右图中：在右图中：途径或链：途径或链：迹或简单链：迹或简单链：路或路径：路或路径：圈或回路：圈或回路：第18页，共78页，编辑于2022年，星期五2最短路问题及算法最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题

13、，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.第19页，共78页，编辑于2022年，星期五 2)在赋权图在赋权图G中，从顶点中，从顶点u

14、到顶点到顶点v的具有最小权的具有最小权定义定义 1)若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各边的权和边的权和 为为H的的权权.类似地，若类似地，若称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3)把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v).第20页，共78页，编辑于2022年，星期五1)赋权图中从给定点到其余顶点的最短路赋权图中从给定点到其余顶点

15、的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负若负若 ，则规定，则规定 最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路第21页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停

16、止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第22页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第23页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且

17、.2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第24页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第

18、25页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第26页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达

19、到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第27页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第28页，共78页，编辑于2022年，星期五Dijkstra算

20、法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第29页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为

21、 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第30页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第31页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶

22、点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).第32页，共78页，编辑于2022年，星期五Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用

23、 i+1 代代替替i，并转，并转2).第33页，共78页，编辑于2022年，星期五第34页，共78页，编辑于2022年，星期五定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为z(v),即即z(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径.例例5的标号过程也的标号过程也可按如下方式进行：可按如下方式进行：首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵因因G是无向图，故是无向图，故W是对称阵是对称阵第35页，共78页，编辑于2022年，星期五第36页

24、，共78页，编辑于2022年，星期五第37页，共78页，编辑于2022年，星期五Dijkstra算法：算法：求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均均非负边上的权均均非负.对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v)，z(v)），其中），其中:l(v)：表从顶点表从顶点u0到到v的一条路的权的一条路的权 z(v)：v的先驱点，用以确定最短路的路线的先驱点，用以确定最短路的路线.l(v)为从顶点为从顶点u0到到v的最短路的权的最短路的权算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每

25、一步改进这两个标记，使最终S：具有永久标号的顶点集：具有永久标号的顶点集.输入输入:G的带权邻接矩阵的带权邻接矩阵 w(u,v)备用备用-将求最短路与最短路径结合起来将求最短路与最短路径结合起来:第38页，共78页，编辑于2022年，星期五算法步骤：算法步骤：l(v)u0vl(u)uw(u,v)第39页，共78页，编辑于2022年，星期五首先写出带权邻接矩阵首先写出带权邻接矩阵例例 求下图从顶点求下图从顶点u0到其到其余顶点的最短路余顶点的最短路因因G是无向图，故是无向图，故W是是对称阵对称阵第40页，共78页，编辑于2022年，星期五第41页，共78页，编辑于2022年，星期五见见Matla

26、b程序程序-Dijkstra.doc第42页，共78页，编辑于2022年，星期五2)求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本思想算法的基本思想（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法.Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.举例说明举例说明第43页，共78页，编辑于2022年，星期五算法的基本思想算法的基本思想第44页，共78页，编辑于2022年，星期五（I）求距离矩阵的方法）求距离矩阵的方法.第45页，共78页，编辑于2022年，星期五（

27、II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R 第46页，共78页，编辑于2022年，星期五（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：第47页，共78页，编辑于2022年，星期五（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.第48页，共78页，编辑于2022年，星期五例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径.第49页，共78页，编辑于2022年，星期五插入点插入点 v1，得：得：矩阵中带

28、矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.第50页，共78页，编辑于2022年，星期五插入点插入点 v2，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.第51页，共78页，编辑于2022年，星期五插入点插入点 v3，得：得：第52页，共78页，编辑于2022年，星期五插入点插入点 v4，得：得：插入点插入点 v5，得：得：第53页，共78页，编辑于2022年，星期五插入点插入点 v6，得：得：第54页，共78页，编辑于2022年，星期五故从故从v5到到v2的最短路为的最短路为8 由由v6向向v5追溯追溯:由

29、由v6向向v2追溯追溯:所以从到的最短路径为：所以从到的最短路径为：见见Matlab程序程序-Floyd.doc第55页，共78页，编辑于2022年，星期五3最小生成树及算法最小生成树及算法1)树的定义与树的特征树的定义与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝.树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.平凡树平凡树第56页，共78页，编辑于2022年，星期五定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1)G是树（是树（G无圈

30、且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边；条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.第57页，共78页，编辑于2022年，星期五2）图的生成树）图的生成树定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树.图图G中不在生成树的边叫做中不在生成树的边叫做弦弦

31、.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性必要性是显然的是显然的.第58页，共78页，编辑于2022年，星期五第59页，共78页，编辑于2022年，星期五（II）找图中生成树的方法）找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法 第60页，共78页，编辑于2022年，星期五A 避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方法成树的方法.这种方法就是在已给的图这种方法就是在已给的图G

32、中，每步选出一条边使中，每步选出一条边使它与已选边不构成圈，直到选够它与已选边不构成圈，直到选够n-1条边为止条边为止.这种方这种方法可称为法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生成树的方在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：法可分为两种：深探法深探法和和广探法广探法.第61页，共78页，编辑于2022年，星期五a)深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号

33、端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图10012345678910111213第62页，共78页，编辑于2022年，星期五13a)深探法深探法图100123456789101112步骤如下：步骤如下：若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退

34、到标号为i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 第63页，共78页，编辑于2022年，星期五3b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)

35、令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图10第64页，共78页，编辑于2022年，星期五3b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标

36、号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.第65页，共78页，编辑于2022年，星期五B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破破圈法圈法”.这种方法就是在图这种方法就是在图

37、G中任取一个圈，任意舍弃一中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图条边，将这个圈破掉，重复这个步骤直到图G中没有圈为中没有圈为止止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.第66页，共78页，编辑于2022年，星期五B 破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的.第67页，共78页，编辑于2022年，星期五3)最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法.第68页

38、，共78页，编辑于2022年，星期五A Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.第69页，共78页，编辑于2022年，星期五例例10用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值

39、权值最小的边有最小的边有 任取一条任取一条 在在 中选取权值中选取权值最小的边最小的边 中权值最小边有中权值最小边有 ,从中选从中选任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取 中选取中选取 .但但 与与 都都第70页，共78页，编辑于2022年，星期五B破圈法算法算法2 步骤如下：步骤如下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈.去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦

40、，直到全部弦检查完毕为止部弦检查完毕为止.例例11用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树.加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部的弦均已试过全部的弦均已试过,得得最小树最小树.第71页，共78页，编辑于2022年，星期五4.旅行售货员问题旅行售货员问题 定义定义设设G=(V,E)是

41、连通无向图，包含图是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的的哈密尔顿路哈密尔顿路(Hamilton路路或或H路路).包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈).含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图).第72页，共78页，编辑于2022年，星期五旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题.一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇之间的距离后，应怎样计划给定各城镇之间的

42、距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？而总距离最小？它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优圈最优圈.但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解只能找一种求出相

43、当好（不一定最优）的解.第73页，共78页，编辑于2022年，星期五一个可行的办法一个可行的办法:是先求一个是先求一个H圈圈,然后适当然后适当修改修改,以得到具有较小权的另以得到具有较小权的另一个一个H圈圈.第74页，共78页，编辑于2022年，星期五定义 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C的一个的一个改进改进.二边逐次修正法二边逐次修正法:在接连进行一系列修改之后在接连进行一系列修改之后,最后得一个圈最后得一个圈,不能不能再用此方法改进了，这个最后的圈可能不是最优的再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它

44、是比较好的，为了得到更高的精度，这个程序可以重复几次，每次都以不同的圈开始程序可以重复几次，每次都以不同的圈开始.这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.第75页，共78页，编辑于2022年，星期五例例对下图对下图16的的K6,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈.较优较优H圈圈:其权为其权为W(C3)=192第76页，共78页，编辑于2022年，星期五 分析分析:找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，圈的一个下界，方法如下方法如下：

45、设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v,C-v是是G-v的路，也的路，也G-v是的生成树是的生成树.如果如果T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联的边中权最小的两条关联的边中权最小的两条边边,则则w(T)+w(e1)+w(e2)将是将是w(C)的一个下界的一个下界.取取v=v3,得得G-v3的一的一最小生成树最小生成树(实线实线),其其权权w(T)=122,与与v3关联关联的权最小的两条边为的权最小的两条边为w(T)+w(v1v3)+w(v2v3)=178.故最优故最优H圈的权圈的权v1v3和和v2v3,故故w(C)应满足应满足178 w(C)192.第77页，共78页，编辑于2022年，星期五再见再见第78页，共78页，编辑于2022年，星期五