《可视化计算》第7章图论基础与应用(B).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章 图论基础与应用,PART B,可视化计算,1,图算法的应用,最小生成树,-,与网络建设成本,Dijkstra,算法,-,寻找网络中的最短路径,独立集,-,四色定理,支配集,-,商业网点的布局,2,假设要在,n,个城市之间建立通信联络网，则连通,n,个城市只需要,n-1,条线路。这时，自然会考虑这样一个问题，,如何在最节省经费的前提下建立这个通信网,在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。,n,个城市之间，最多可能设置,n(n-1)/2,条线路，,那么，如何在这些可能的线路中选择,n-1,条，以使总的耗费最少呢,?,网络建设成本与最小生成树,3,对于,n,个顶点的连通网可以建立许多不同的生成树，每一生成树都可以是一个网络,现在，我们要选择这样一棵生成树，也就是使总的耗费最少,这个问题就是,构造连通网的最小生成树,(Minimum Spanning Tree,MST),的问题。,一棵生成树的代价就是树上各边的代价之和,最小生成树,4,最小生成树,(MST),性质：,假设,G=(V,，,E),是一个连通图，,U,是顶点集,V,的一个非空子集。,若,(u,，,v),是一条具有最小权值的边，其中,u U,，,vV-U,，则必存在一棵包含边,(u,，,v),的最小生成树,最小生成树,5,最小生成树算法,Prim,算法：,假设,G=(V,，,E),是连通图，,TE,是,N,上最小生成树中边的集合,算法从,U=u,0,(u,0,V),，,TE=,开始，重复执行下述操作：,在所有,uU,，,v V-U,的边,(u,，,v)E,中找一条代价最小的边,(u,0,，,v,0,),并入集合,TE,，同时,v,0,并入,U,，直至,U=V,为止。,此时,TE,中必有,n-1,条边，则,T=(V,TE),为图,G,的最小生成树,6,最小生成树算法：,Prim,算法例子,v6,v5,v3,v2,v4,v1,v6,v5,v3,v4,v2,v1,(c),(b),(a),5,v6,v5,v3,v4,v2,v1,6,5,1,5,3,6,6,4,2,v6,v5,v3,v4,v2,v1,v6,v5,v3,v2,v4,v1,v6,v5,v3,v2,v4,v1,(d)(e)(f),Prim,算法构造最小生成树的过程,7,Prim,算法思想：,任意时刻的中间结果都是一棵树,从一个点开始，每次都花最少的代价，用一条边把一个不在树里的点加进来,算法复杂度：每次选边的复杂度为,O(logm),，所以时间复杂度为,O(m+nlogm),最小生成树算法：,Prim,算法,8,用,RAPTOR,实现,Prim,算法,Prim,子程序,9,用,RAPTOR,实现,Prim,算法,init,子图,10,用,RAPTOR,实现,Prim,算法,Fun1,子图,11,用,RAPTOR,实现,Prim,算法,Fun2,子图,12,Prim,算法的计算结果,v6,v5,v3,v2,v4,v1,5,v6,v5,v3,v4,v2,v1,6,5,1,5,3,6,6,4,2,13,网络中的最短路径,如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径,从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同,对网络而言，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的,最短路径,，其路径长度称为,最短路径长度,14,寻找网络中的最短路径,-,Dijkstra,算法,Single Source/All Destinations,15,Dijkstra,算法基本思路,设置一个集合,S,，存放已求出最短路径的顶点，,V-S,是尚未确定最短路径的顶点集合,每个顶点对应一个,距离值,，集合,S,中顶点的距离值是从顶点,v,1,到该顶点的最短路径长度；,集合,V-S,中顶点的距离值是从顶点,v,1,到该顶点的只包括集合,S,中顶点为中间顶点的最短路径长度,16,初始状态,集合,S,中只有顶点,v,1,，顶点,v,1,对应的距离值为,0,；,集合,V-S,中顶点,v,i,的距离值为边,(v,1,vi)(i=2,n),的权；,如果,v,1,和,v,i,间无边直接相连，则,v,i,的距离值为,17,处理原则,（,1,）在集合,V-S,中选择距离值最小的顶点,v,min,加入集合,S,；,（,2,）对集合,V-S,中各顶点的距离值进行修正：如果加入顶点,v,min,为中间顶点后，使,v,1,到,v,i,的距离值比原来的距离值更小，则修改,v,i,的距离值；,（,3,）重复（,1,）、（,2,）操作，直到从,v,1,出发可以到达的所有顶点都在集合,S,中为止。,18,Dijkstra,算法,19,Dijkstra,算法,Init,子图,20,Dijkstra,算法,Path,子图,21,Dijkstra,算法,choose,子程序22,Dijkstra,算法,Input_output,子图,23,Dijkstra,算法的结果输出,24,四色定理,-,独立集,25,图的着色,两类着色问题问题：,1,给定无环图,G=(V,E),，用,m,种颜色为图中的每条,边着色,，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。,2,给定无向图,G=(V,E),，用,m,种颜色为图中的每个,顶点着色,，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题,26,地图的抽象,27,顶点着色基本概念,独立集：,对图,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,（但两者不同时成立）。,28,顶点着色基本概念,K,可着色,：,G,的一个,k,顶点着色是指,k,种颜色,1,2,k,对于,G,各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的,G,的色数,X,（,G,）是指,G,为,k,可着色的,k,的最小值，若,X,（,G,）,=k,，则称,G,是,k,色的,29,求顶色数的算法设计,由“每个同色顶点集合中的两两顶点不相邻”可以看出，,同色顶点集实际上是一个独立集,用第,1,种颜色上色时，为了尽可能扩大颜色,1,的顶点个数，逼近所用颜色数最少的目的,事实上就是找出图,G,的一个极大独立集并给它涂上颜色,1,。,用第,2,种颜色上色时，同样选择另一个极大独立集涂色，,.,当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。,30,算法步骤,Step1,：求,G图的所有极大独立集,Step2,：求出一切若干极大独立集的和含所有顶点的子集；,Step3,：从中挑选所用极大独立集个数最小值，即为,X,（,G,）,31,Welch Powell,着色法,I,将图,G,中的结点按度数的递减顺序进行排列,(,这种排列可能不是唯一的，因为有些结点的度数相同,),；,II,用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色；,III,用第二种颜色对尚未着色的结点重复,II,，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。,32,Welch Powell,着色法,给定图,G,，用,Welch Powell,法对图,G,着色,33,Welch Powell,着色法,1,、将图,G,中的结点按度数的递减顺序排列：,2,、用第一种颜色对,A5,着第一种颜色，并对与,A5,不邻接的结点,A1,也着第一种颜色。,3,、对结点,A3,及与,A3,不邻接的结点,A4,、,A8,着第二种颜色。,4,、对结点,A7,及与,A7,不邻接的结点,A2,、,A6,着第三种颜色。,因此，图,G,是三色的；,但图,G,不可能是二色的，因为,A1,A2,A3,相互邻接，故必须着三种颜色。所以,x(G)=3,。,34,地图着色,Main,子图,35,地图着色,Color_seq,子图,36,地图着色,Countedges,子图,37,地图着色,setColor,子图,38,地图着色,Lookformaxedges,子程序,39,地图着色结果,40,商业网点的布局,一个小城，要设置水井，假设所有人都,住在顶点所在的位置,问题：,如何配置，使得居民只要走过一条街，就可以到达水井，并且水井的数量最小,41,课堂提问,所有的居民住在,街口,走最多一个街道的距离,至少要几辆售货车,42,可抽象的概念,图：无向图,边：表示街道,节点：表示路口,问题：求最少的冰激凌车的配置,43,生活中的同类问题,安置邮筒,消防站,城市中配置教育资源,在一个国家配置航空、铁路枢纽,这些问题容易求解吗？,如何解？,44,开始时的思考：,考虑,所有的,放置冰激凌销售车的可能情况，然后检验哪种是最好的,在这城镇的,26,个街角中，如果放置一台销售车,有,26,种放置方法,很容易检验这,26,种放置方法,很明显没有一种满足要求（明显不够）,45,开始时的思考,-,：,如果有两辆销售车,那么有,26,个地方可以放置第一辆车,这样一来，除掉放置第一辆车的地方，还有,25,个地方来放置第二辆（不会在一个地方放两辆车）,将有,26*25,种可能性要检验,事实上，只需要检验其中的一半（,325,）,因为这两辆车中的哪一辆放置在一个地方是无关紧要的,46,开始时的思考,-,：,三辆车可能的情况？,262524/6=2600,四辆车可能的情况？,26252423/24=14950,总共的实验次数？,2,26,，也就是,67 108 864,（六千七百万）,1,秒钟检验一个方案,大约需要,777,天,47,最小支配集问题,冰激凌销售车问题正式地被称为,“,最小支配集,”,问题,支配集（,Domination set,）可描述如下：,给定无向图,G=V,E,，,其中,V,是大小为,n,的点集，,E,是边集,那么,V,的一个子集,S,称为,支配集,当且仅当对于,V-S,中任何一个点,v,，都有,S,中的某个定点,u,使得,(u,v)E,这时称,点,u,支配点,v,，并把,S,中的点称为,支配点,支配集的判定问题就是判定图,G,中是否有大小不大于正整数,k,（,k=n,）的支配集,其优化问题就是求出规模最小的支配集,48,使用,RAPTOR,求解支配集问题程,1,、建立邻接矩阵,2,、选择算法,3,、进行计算和分析,4,、进行比较,49,基本解法,对有,N,个结点的旅行城镇问题，,给,N,个路口编号，,1,N,50,最初的求解方法,蛮力法（,brutr-force,）、穷举法,检验所有的可能性，找出满足条件的解,理论计算时间,36,个交叉点,2000,年,46,个交叉点,2,百万年,51,贪心算法,把第一辆销售车放在连接最多街道数目的交叉点处,第二辆放在下一个类似的交叉点处,如此类推,但是，这不能保证一定得到一个冰激凌销售车放置方案的最小集,52,基本数据结构,邻接矩阵,/,临接表,已经通过前面的例子输入,RAPTOR,各位可以试用建议的办法和自己创建算法进行计算,53,小结与回顾,图论属于数学中相对年轻的学科分支，在社会学、交通管理、电信领域获得广泛应用图论学科所具有的特点包括：,图论蕴含了丰富的思想、简洁的图案和巧妙的证明；,涉及的问题多而广泛，问题表面简单朴素而本质深刻；,问题求解的方法非常灵活，可以充分发挥人和计算机的计算能力，使用科学手段解决难解的问题,54,