第8讲 最短路问题

图论图论起源于18世纪对哥尼斯堡七桥问题的研究，哥尼斯堡是18世纪属于东普鲁士的一座城市，它位于普列格尔河畔，河中有两个岛A,B,把市区分成了四块陆地A,B,C,D。该城的市民热衷于一个游戏，从四块陆地的某一处出发通过每座桥恰好一次，再回到出发地。图论的基本概念一、图的概念1、图的定义2、顶点的次数

3、子图二、图的矩阵表示1、关联矩阵2、邻接矩阵定义有序三元组G=(V,E,)称为一个图.图的定义定义定义顶点的次数例在一次聚会中，认识奇数个人的人数一定是偶数。偶点与奇点：如果某个顶点相连的边的条数为偶数，则称这个顶点为偶点，否则称为奇点。子图关联矩阵注：假设图为简单图邻接矩阵注：假设图为简单图七桥问题变为：从图中任一点出发，找出一条通过每条边有且只有一次，最后回到出发点的回路。通常称这样的回路为欧拉回路。直观来看：对于某个顶点，有一个进来的边就有一个出去的边，同样，有一条出去的边，必然有一条进来的边。对于七桥问题，该图四个顶点都是奇点，问题无解。考虑问题有解的条件？人，狼、羊、菜问题有一农夫带着一只狼、一头羊和一萝白菜想从A岸撑船到B岸，现在有一条船，而船只能容纳农夫和另外一样，人不在的情况下，狼会吃羊，羊吃白菜，怎样才能把这几样东西运到对岸。问题转化为求一条从顶点(1,1,1,1)到顶点(0,0,0,0)的路。若要求摆渡次数最少，可以对各边赋权值为1，转化为求最短路。消防设施的安置有一个小区，有七条街道，街道一共有五个交叉路口，如图，现在要在某些路口安置消防设施，要求每条街道至少有一个路口设置有消防设施，则在哪些路口安置设施最为节省？这个问题是覆盖问题，覆盖的定义如下，若图G的每条边至少有一个端点在顶点集V的一个子集K中，则K称为G的覆盖。含顶点最少的覆盖为最小覆盖。可以用关联矩阵求得。得到最小覆盖（B,C,D）,(A,C,E),(B,D,E)化学制品的存放某实验室现有化学制品7种，其中部分是不相容的，应该相互隔离在不同的房间里，以免发生危险。这7中化学制品的相容性如下，则至少准备多少间独立的房间才能保证安全？ABCDEFGA不不B不不不C不不不D不不E不F不G问题转化为图上相邻的两个顶点代表的化学制品必不能放在同一个房间。设想用红，蓝，黄色等标记，则相当于所有相邻的顶点的颜色不能相同，如何用最少的颜色将顶点染色。顶点染色问题就是在顶点集中找出不包含相邻顶点的子集，并要求这种子集内顶点数目尽量多。称不包含相邻顶点的子集S为独立集，若S中添加任何一个顶点都会使其不再是独立子集，则称S为极大独立集。步骤：1.求出各顶点的相邻的点，并用逻辑表达式表示出来，如A＋BD得到B+ACEG，C+ACEF，D+ACEG，E+BCDF，F+CEG，G+BDF（2）将各逻辑表达式合并得：（A＋BD）（B+ACEG）（C+ACEF）（D+ACEG）（E+BCDF）（F+CEG）（G+BDF）（3）得到所有极大独立集（B,D,F）（A,F）（A,C,G）（A,E,G）取一个最大独立集，染第一种颜色。直到着色结束。最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路基本概念固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路．算法步骤：u1u2u3u4u5u6u7u8每对顶点之间的最短路1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（三）算法步骤算法的基本思想算法原理——求距离矩阵的方法算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．算法步骤v1v29v4v2v574223一、可化为最短路问题的多阶段决策问题二、选址问题1、中心问题2、重心问题可化为最短路问题的多阶段决策问题

选址问题--中心问题S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。

选址问题--重心问题最优匹配算法设有六个人和六项工作的最优指派问题，其效益矩阵如下:问题是求一种工作分配，使每个工人完成一项任务，而且效益最大。工人1234561201516547217153312863912181630134128112719145-7102110326---61113设G(V,E)是一个二部图，设M是E的一个子图，如果M中的所有边没有公共的顶点，则称M是二部图G(V,E)的一个匹配。如果它关联的边是匹配M的一条边，则称顶点是饱和的。如果M的所有顶点都是饱和的，称M为G的完美匹配。如何求一个具有最大权的完美匹配假定：图G是加权二部图，两个顶点集合为V1,V2，并且V1,V2均有n个顶点。对于每个顶点对，边存在。在介绍最优匹配算法之前，先介绍概念－－可扩充路定义设M是G的一个匹配，G的M交错路是指其边在E-M和M中交错出现的路。M可扩充路是指其起点和终点都是M非饱和的M交错路。蓝线是匹配M的边，黑线不属于M，因此路径是一条可扩充路，去掉边，得到另一个图。可行顶点标号定义设G是加权二部图，其中W是加权矩阵，设L(v)是顶点v的标号，对于所有的边，有，则称L是可行顶点标号，记称具有边集的G的生成子图为对应可行顶点标号L的相等子图，记为G(L)。对于任何加权二部图G，它的可行顶点标号是存在的，只需令设S是图G的顶点集，称与S的顶点相邻的所有顶点组成的集合为邻集，记为工人1234561201516547217153312863912181630134128112719145-9971021