ppt课件-顾刚43529-00顾刚-大学计算机基础课件ch8-6

第7章图论基础与应用PARTB,可视化计算,图算法的应用,最小生成树-与网络建设成本Dijkstra算法-寻找网络中的最短路径独立集-四色定理支配集-商业网点的布局,假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?,网络建设成本与最小生成树,对于n个顶点的连通网可以建立许多不同的生成树，每一生成树都可以是一个网络现在，我们要选择这样一棵生成树，也就是使总的耗费最少这个问题就是构造连通网的最小生成树(MinimumSpanningTree,MST)的问题。一棵生成树的代价就是树上各边的代价之和,最小生成树,最小生成树(MST)性质：假设G=(V，E)是一个连通图，U是顶点集V的一个非空子集。若(u，v)是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边(u，v)的最小生成树,最小生成树,最小生成树算法,Prim算法：假设G=(V，E)是连通图，TE是N上最小生成树中边的集合算法从U=u0(u0V)，TE=开始，重复执行下述操作：在所有uU，vV-U的边(u，v)E中找一条代价最小的边(u0，v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,TE)为图G的最小生成树,最小生成树算法：Prim算法例子,(c),(b),(a),(d)(e)(f)Prim算法构造最小生成树的过程,Prim算法思想：任意时刻的中间结果都是一棵树从一个点开始，每次都花最少的代价，用一条边把一个不在树里的点加进来算法复杂度：每次选边的复杂度为O(logm)，所以时间复杂度为O(m+nlogm),最小生成树算法：Prim算法,用RAPTOR实现Prim算法,Prim子程序,用RAPTOR实现Prim算法,init子图,用RAPTOR实现Prim算法,Fun1子图,用RAPTOR实现Prim算法,Fun2子图,Prim算法的计算结果,网络中的最短路径,如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同对网络而言，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度,寻找网络中的最短路径-Dijkstra算法,SingleSource/AllDestinations,Dijkstra算法基本思路,设置一个集合S，存放已求出最短路径的顶点，V-S是尚未确定最短路径的顶点集合每个顶点对应一个距离值，集合S中顶点的距离值是从顶点v1到该顶点的最短路径长度；集合V-S中顶点的距离值是从顶点v1到该顶点的只包括集合S中顶点为中间顶点的最短路径长度,初始状态,集合S中只有顶点v1，顶点v1对应的距离值为0；集合V-S中顶点vi的距离值为边(v1,vi)(i=2,n)的权；如果v1和vi间无边直接相连，则vi的距离值为,处理原则,（1）在集合V-S中选择距离值最小的顶点vmin加入集合S；（2）对集合V-S中各顶点的距离值进行修正：如果加入顶点vmin为中间顶点后，使v1到vi的距离值比原来的距离值更小，则修改vi的距离值；（3）重复（1）、（2）操作，直到从v1出发可以到达的所有顶点都在集合S中为止。,Dijkstra算法,Dijkstra算法,Init子图,Dijkstra算法,Path子图,Dijkstra算法,choose子程序,Dijkstra算法,Input_output子图,Dijkstra算法的结果输出,四色定理-独立集,图的着色,两类着色问题问题：1给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。2给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题,地图的抽象,顶点着色基本概念,独立集：对图G=(V,E)，设S是V的一个子集，若中任意两个顶点在G中均不相邻，则称S为G的一个独立集。最大独立集：如果G不包含适合|S|S|的独立集S，则称S为G的最大独立集。极大覆盖：设K是G的一个独立集，并且对于V-K的任一顶点v，K+v都不是G的独立集，则称K是G的一个极大覆盖。极小覆盖：极大独立集的补集称为极小覆盖。V的子集K是G的极小覆盖当且仅当：对于每个顶点v或者v属于K，或者v的所有邻点属于K（但两者不同时成立）。,顶点着色基本概念,K可着色：G的一个k顶点着色是指k种颜色1,2,k对于G各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的G的色数X（G）是指G为k可着色的k的最小值，若X（G）=k，则称G是k色的,求顶色数的算法设计,由“每个同色顶点集合中的两两顶点不相邻”可以看出，同色顶点集实际上是一个独立集用第1种颜色上色时，为了尽可能扩大颜色1的顶点个数，逼近所用颜色数最少的目的事实上就是找出图G的一个极大独立集并给它涂上颜色1。用第2种颜色上色时，同样选择另一个极大独立集涂色，.当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。,算法步骤,Step1：求G图的所有极大独立集Step2：求出一切若干极大独立集的和含所有顶点的子集；Step3：从中挑选所用极大独立集个数最小值，即为X（G）,WelchPowell着色法,I将图G中的结点按度数的递减顺序进行排列(这种排列可能不是唯一的，因为有些结点的度数相同)；II用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色；III用第二种颜色对尚未着色的结点重复II，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。,WelchPowell着色法,给定图G，用WelchPowell法对图G着色,WelchPowell着色法,1、将图G中的结点按度数的递减顺序排列：2、用第一种颜色对A5着第一种颜色，并对与A5不邻接的结点A1也着第一种颜色。3、对结点A3及与A3不邻接的结点A4、A8着第二种颜色。4、对结点A7及与A7不邻接的结点A2、A6着第三种颜色。因此，图G是三色的；但图G不可能是二色的，因为A1,A2,A3相互邻接，故必须着三种颜色。所以x(G)=3。,地图着色,Main子图,地图着色,Color_seq子图,地图着色,Countedges子图,地图着色,setColor子图,地图着色,Lookformaxedges子程序,地图着色结果,商业网点的布局,一个小城，要设置水井，假设所有人都住在顶点所在的位置问题：如何配置，使得居民只要走过一条街，就可以到达水井，并且水井的数量最小,课堂提问,所有的居民住在街口走最多一个街道的距离至少要几辆售货车,可抽象的概念,图：无向图边：表示街道节点：表示路口问题：求最少的冰激凌车的配置,生活中的同类问题,安置邮筒消防站城市中配置教育资源在一个国家配置航空、铁路枢纽这些问题容易求解吗？如何解？,开始时的思考：,考虑所有的放置冰激凌销售车的可能情况，然后检验哪种是最好的在这城镇的26个街角中，如果放置一台销售车有26种放置方法很容易检验这26种放置方法很明显没有一种满足要求（明显不够）,开始时的思考-：,如果有两辆销售车那么有26个地方可以放置第一辆车这样一来，除掉放置第一辆车的地方，还有25个地方来放置第二辆（不会在一个地方放两辆车）将有26*25种可能性要检验事实上，只需要检验其中的一半（325）因为这两辆车中的哪一辆放置在一个地方是无关紧要的,开始时的思考-：,三辆车可能的情况？262524/6=2600四辆车可能的情况？26252423/24=14950总共的实验次数？226，也就是67108864（六千七百万）1秒钟检验一个方案大约需要777天,最小支配集问题,冰激凌销售车问题正式地被称为“最小支配集”问题支配集（Dominationset）可描述如下：给定无向图G=V,E，其中V是大小为n的点集，E是边集那么V的一个子集S称为支配集当且仅当对于V-S中任何一个点v，都有S中的某个定点u,使得(u,v)E这时称点u支配点v，并把S中的点称为支配点支配集的判定问题就是判定图G中是否有大小不大于正整数k（k=n）的支配集其优化问题就是求出规模最小的支配集,使用RAPTOR求解支配集问题程,1、建立邻接矩阵2、选择算法3、进行计算和分析4、进行比较,基本解法,对有N个结点的旅行城镇问题，给N个路口编号，1,N,最初的求解方法,蛮力法（brutr-force）、穷举法检验所有的可能性，找出满足条件的解理论计算时间36个交叉点2000年46个交叉点2百万年,贪心算法,把第一辆销售车放在连接最多街道数目的交叉点处第二辆放在下一个类似的交叉点处如此类推但是，这不能保证一定得到一个冰激凌销售车放置方案的最小集,基