下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数学建模-图论

数学建模-图论.ppt

数学建模-图论

学者
2013-08-28 0人阅读 举报 0 0 暂无简介

简介:本文档为《数学建模-图论ppt》,可适用于高等教育领域

数学建模数学建模图论方法专题专题板块系列专题板块系列图论方法专题图论方法专题二部图的匹配四网络流图论的基本概念哥尼斯堡七桥示意图问题:七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点?图论的基本概念图论的基本概念七桥问题模拟图:欧拉指出:如果每块陆地所连接的桥都是偶数座则从任一陆地出发必能通过每座桥恰好一次而回到出发地。图论的基本概念图论的基本概念问题:哈密顿圈(环球旅行游戏)十二面体的个顶点代表世界上个城市能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?图论的基本概念图论的基本概念问题:四色问题对任何一张地图进行着色两个共同边界的国家染不同的颜色则只需要四种颜色就够了。德·摩尔根致哈密顿的信(年月日)   我的一位学生今天请我解释一个我过去不知道现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色使任何具有公共边界的部分颜色不同那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子(图)。……图论的基本概念图论的基本概念问题(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序这些工序相互约束,只有在某些工序完成之后,一个工序才能开始即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个?图论的基本概念图论的基本概念定义一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点②E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边图论的基本概念图论的基本概念如果V={v,v,…,vn}是有限非空点集,则称G为有限图或n阶图如果E的每一条边都是无向边,则称G为无向图如果E的每一条边都是有向边,则称G为有向图否则,称G为混合图记E={e,e,…,em}(ek=vivj)图论的基本概念图论的基本概念对于一个图G=(V,E),人们常用图形来表示它,称其为图解凡是有向边,在图解上都用箭头标明其方向称点vi,vj为边vivj的端点有边联结的两个点称为相邻顶点,有一个公共端点的边称为相邻边边和它的端点称为互相关联有向图中的关联又分出关联和入关联。图论的基本概念图论的基本概念常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数与顶点v出关联的边的数目称为出度记作d(v),与顶点v入关联的边的数目称为入度记作d(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合图论的基本概念任意两顶点都相临的简单图称为完全图有n个顶点的完全图记为Kn。图论的基本概念几个基本定理:图论的基本概念图论的基本概念用图论思想求解以下各题例、一摆渡人欲将一只狼一头羊一篮菜从河西渡过河到河东由于船小一次只能带一物过河并且狼与羊羊与菜不能独处给出渡河方法。图论的基本概念图论的基本概念解:用四维向量表示(人狼羊菜)的在西岸状态(在西岸则分量取否则取)共=种状态由题设状态(,,,),(,,,),(,,,)是不允许的从而对应状态(,,,)(,,,),(,,,)也是不允许的图论的基本概念图论的基本概念人在河西:(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)人在河东:以十个向量作为顶点将可能互相转移的状态连线则得个顶点的偶图。问题:如何从状态(,,,)转移到(,,,)?方法:从(,,,)开始沿关联边到达没有到达的相邻顶点到(,,,)终止得到有向图即是。图论的基本概念图论的基本概念例、考虑中国象棋的如下问题:()下过奇数盘棋的人数是偶数个。()马有多少种跳法?()马跳出后又跳回起点证明马跳了偶数步。()红方的马能不能在自己一方的棋盘上不重复的跳遍每一点最后跳回起点?图论的基本概念图论的基本概念例、证明:在任意人的集会上总有人互相认识或总有人互相不认识。解:以顶点表示人以边表示认识得个顶点的简单图G。问题:人互相认识即G包含K为子图人互相不认识即G包含(,)图为子图。图论的基本概念图论的基本概念图论的基本概念图论的基本概念定义若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F)定义设G=(V,E)是一个图,v,v,…,vk∈V,且“≤i≤k,vi-vi∈E,则称vv…vk是G的一条通路图论的基本概念如果通路中没有相同的顶点,则称此通路为路径,简称路始点和终点相同的路称为圈或回路图论的基本概念定义顶点u与v称为连通的如果存在uv通路任二顶点都连通的图称为连通图否则称为不连通图。极大连通子图称为连通支。图论的基本概念定义连通而无圈的图称为树,常用T表示树树中最长路的长称为树的高。树的度为的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图如果G的基础图是树则称G是有向树也简称树。图的矩阵表示⑴邻接矩阵A=(aij)n×n,例:写出右图的邻接矩阵:解:图的矩阵表示图的矩阵表示⑵权矩阵A=(aij)n×n例:写出右图的权矩阵:解:图的矩阵表示图的矩阵表示⑶关联矩阵A=(aij)n×m 有向图:无向图:图的矩阵表示图的矩阵表示例:写出右图与其基本图的关联矩阵解:分别为:图的矩阵表示最短路定义设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记F(P)=,则称F(P)为路径P(u,v)的权或长度(距离)定义若P(u,v)是G中连接u,v的路径,且对任意在G中连接u,v的路径P(u,v)都有F(P)≤F(P),则称P(u,v)是G中连接u,v的最短路最短路最短路重要性质:若vv…vm是G中从v到vm的最短路,则对≤k≤m,vv…vk必为G中从v到vk的最短路即:最短路是一条路且最短路的任一段也是最短路。最短路最短路例对下面的有向图求顶点v到其余顶点的最短路。最短路最短路Dijkstra算法:求某一顶点到其余顶点的最短路最短路最短路例:求下列任意两点的最短路和距离。最短路最短路Floyd算法:求任意两顶点的最短路设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号①赋初值对所有i,j,dij=aij,rij=jk=转向②②更新dij,rij对所有i,j,若dikdkj<dij,则令dij=dikdkj,rij=k,转向③③终止判断若k=n终止否则令k=k,转向②最短路线可由rij得到最短路最短路求非负赋权图G中某一点到其它各点最短路一般用Dijkstra标号算法Dijkstra标号算法只适用于全部权为非负情况。求非负赋权图上任意两点间的最短路一般用Floyd算法Floyd算法可以适用于有负权的情况还能判断是否有负回路。这两种算法均适用于有向赋权图最短路最小生成树由树的定义不难知道,任意一个连通的(p,q)图G适当去掉qp条边后,都可以变成树,这棵树称为图G的生成树设T是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树最小生成树最小生成树例:如下图G求最小生成树:Kruskal算法:从最小边开始按最小权加边有圈去掉。最小生成树最小生成树例(设备更新问题)某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费若购买一台新设备,要付购买费试制定一个年更新计划,使总支出最少已知设备在每年年初的购买费分别为,,,,使用不同时间设备所需的维修费分别为,,,,最小生成树最小生成树解设bi表示设备在第i年年初的购买费,ci表示设备使用i年后的维修费,V={v,v,…,v},点vi表示第i年年初购进一台新设备,虚设一个点v表示第年年底E={vivj|≤i<j≤}求v到v的最短路问题最小生成树最小生成树由实际问题可知,设备使用三年后应当更新,因此删除该图中v到v,v到v,v到v的连线又设备使用一年后就更新则不划算,因此再删除该图中vv,vv,vv,vv,vv五条连线后得到从上图中容易得到v到v只有两条路:vvv和vvv而这两条路都是v到v的最短路最小生成树最小生成树例多阶段存储问题某公司根据市场情况预计某商品今后六个月的需要量进货单价与存储单价如下若当月订购当月所需商品不附加存储费问如何进货使总费用最小。最小生成树二部图的匹配及其应用称G=(X,Y,E)为二部图如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图若F:E→R,则称G=(X,Y,E,F)为二部赋权图定义设X,Y都是非空有限顶点集,且X∩Y=Φ,二部图的匹配及其应用二部图的匹配及其应用定义若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点定义设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配如果G中没有另外的匹配M,使|M|>|M|,则称M是最大匹配每个完美匹配都是最大匹配,反之不一定成立二部图的匹配及其应用二部图的匹配及其应用例:判断下图的匹配最大匹配非完美匹配完美匹配二部图的匹配及其应用二部图的匹配及其应用定义设M是图G的的一个匹配,其边在EM和M中交错出现的路,称为G的一条M–交错路起点和终点都不是M的饱和点的M–交错路,称为M–增广路定理G的一个匹配M是最大匹配的充要条件是G不包含M–增广路二部图的匹配及其应用二部图的匹配及其应用定理设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S ,有|N(S)|≥|S|其中,N(S)={v|u∈S,v与u相邻}②G存在完美匹配的充要条件是对任意S或S有|N(S)|≥|S|二部图的匹配及其应用二部图的匹配及其应用工作安排问题之一给n个工作人员x,x,…,xn安排n项工作y,y,…,ynn个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作比如x能做y,y工作,x能做y,y,y工作等这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作?二部图的匹配及其应用二部图的匹配及其应用我们构造一个二部图G=(X,Y,E),这里X={x,x,…,xn},Y={y,y,…,yn},并且当且仅当工作人员xi胜任工作yj时,xi与yj才相邻于是,问题转化为求二部图的一个完美匹配因为|X|=|Y|,所以完美匹配即为最大匹配二部图的匹配及其应用二部图的匹配及其应用例:求下图完美匹配Hungarian算法:二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:解①取初始匹配M={xy,xy,xy}②给X中M的两个非饱和点x,x都给以标号和标记*(如下图所示)**二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:③去掉x的标记*,将与x邻接的两个点y,y都给以标号因为y,y都是M的两个饱和点,所以将它们在M中邻接的两个点x,x都给以相应的标号和标记*****二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:***④去掉x的标记*,将与x邻接且尚未给标号的三个点y,y,y都给以标号二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:**⑤因为y是M的非饱和点,逆向返回,直到x为为止于是得到M的增广路xyxy,记P={xy,yx,xy}取M=M⊕P={xy,xy,xy,xy},则M是比M多一边的匹配二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:*⑥再给X中M的非饱和点x给以标号和标记*,然后去掉x的标记*,将与x邻接的两个点y,y都给以标号二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:因为y,y都是M的两个饱和点,所以将它们在M中邻接的两个点x,x都给以相应的标号和标记***二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:**⑦去掉x的标记*,因为与x邻接的两个点y,y都有标号,所以去掉x的标记*而与x邻接的两个点y,y也都有标号,此时X中所有有标号的点都已去掉了标记*(如下图所示),因此M是G的最大匹配没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用例:求下图的最大匹配。匈亚利算法:注意到S={x,x,x}时N(S)={y,y,}所以没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用定义设G=(X,Y,E,F)为完备的二部赋权图,若L:X∪Y→R满足:对任意x∈X,y∈Y,L(x)L(y)≥F(xy),则称L为G的一个可行点标记,记相应的生成子图为GL=(X,Y,EL,F),这里EL={xy∈E|L(x)L(y)=F(xy)}定理设L是完备的二部赋权图G=(X,Y,E,F)的可行点标记,若M*是GL的完美匹配,则M*是G的最佳匹配(权数最大的匹配)二部图的匹配及其应用二部图的匹配及其应用工作安排问题之二给n个工作人员x,x,…,xn安排n项工作y,y,…,yn如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高二部图的匹配及其应用二部图的匹配及其应用我们构造一个二部赋权图G=(X,Y,E,F),这里X={x,x,…,xn},Y={y,y,…,yn},F(xiyj)为工作人员xi胜任工作yj时的工作效率则问题转化为:求二部赋权图G的最佳匹配在求G的最佳匹配时,总可以假设G为完备二部赋权图若xi与yj不相邻,可令F(xiyj)=同样地,还可虚设点x或y,使|X|=|Y|如此就将G转化为完备二部赋权图,而且不会影响结果二部图的匹配及其应用二部图的匹配及其应用例:求赋权矩阵为的完备二部赋权图G=(X,Y,E,F)的最佳匹配。可行顶点标号法:矩阵覆盖法:分枝定界法:二部图的匹配及其应用二部图的匹配及其应用矩阵覆盖法:STEP:求等价分配矩阵。STEP:求独立零元画上框。(非同列同行的零)STEP:最优判别:达到n个独立零元。停。STEP:求覆盖线:)封锁没有画框零元的行封锁就打√)在封锁行中未画框零元的列也封锁)在封锁列中画框零元的行也封锁)未封锁行与封锁列画上覆盖线。STEP:调节分配矩阵:在未覆盖元中选取最大元k未覆盖行加∣k∣覆盖列减∣k∣。转STEP二部图的匹配及其应用网络流问题定义设G=(V,E)为有向图,在V中指定一点称为发点(记为vs),和另一点称为收点(记为vt),其余点叫做中间点对每一条边vivj∈E,对应一个非负实数Cij,称为它的容量这样的G称为容量网络,简称网络,记作G=(V,E,C)G中任一边vivj有流量fij,称集合f={fij}为网络G上的一个流网络流问题网络流问题定义满足下述条件的流f称为可行流:①(容量限制条件)对每一边vivj,有≤fij≤Cij②(平衡条件)对于中间点vk有∑fik=∑fkj,即中间点vk的输入量=输出量如果f是可行流,则对收、发点vt、vs有∑fsi=∑fjt=Wf,即从vs点发出的物质总量=vt点输入的量Wf称为网络流f的总流量网络流问题最大流问题一个可行流f={fij},当fij=Cij时,则称流f对边vivj是饱和的当fij<Cij时,则称流f对边是非饱和的把fij=的边称为零流边,fij>的边称为非零流边若μ为网络中从vs到vt的一条链(有向图中的路),定义链的方向是从vs到vt,边的方向与链的方向相同称为前向边,前向边的全体记为μ边的方向与链的方向相反称为后向边,后向边的全体记为μ¯最大流问题最大流问题定义设f是一个可行流,μ是从vs到vt一条链如果满足①当vivj∈μ时,≤fij<Cij,即μ中的每一条边都非饱和边②当vivj∈μ¯时,<fij≤Cij,即μ¯中的每一条边都非零边则称μ为从vs到vt的关于f的可增广链最大流问题最大流问题定义容量网络G=(V,E,C),若点集V被剖分为两个非空集合S,Sc=VS,vs,vt分属于S,Sc则把边集(S,Sc)={vivj|vivj∈E,vi∈S,vj∈Sc}称为G的割集若把一割集的边从网络中去掉,则从vs到vt便不在相通,所以割集是从vs到vt的必经之路割集(S,Sc)中所有边的容量之和,称为这个割集的容量,记为C(S,Sc)最大流问题最大流问题定理设f为网络G=(V,E,C)的任一可行流,(S,Sc)是剖分vs,vt的任一割集,则有Wf≤C(S,Sc)若有可行流f和割集(S,Sc),使得Wf=C(S,Sc),则f一定是G的最大流,而(S,Sc)必定是G中所有割集中容量小的一个,即最小割集例:给出网络的割。最大流问题最大流问题定理(最大流最小割定理)任一个网络中G中,从vs到vt的最大流的流量等于分割vs,vt的最小割的容量推论可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)可增广链最大流问题最大流问题实际问题中,一个网络会出现下面两种情况:⑴发点和收点都不止一个解决的方法是再虚设一个发点vs和一个收点vt,发点vs到所有原发点边的容量都设为无穷大,所有原收点到收点vt边的容量都设为无穷大⑵网络中除了边有容量外,点也有容量解决的方法是将所有有容量的点分成两个点,如点v有容量Cv,将点v分成两个点v'和v",令C(v'v")=Cv最大流问题最大流问题例:求网络的最大流。探索:单向调整法:双向调整法:FordFulkerson算法最大流问题最大流问题例:图表明一个网络及初始可行流,每条边上的有序数表示(Cij,fij)求这个网络的最大流标号算法:最大流问题最小费用流问题一般提法:已知网络G=(V,E,C),每条边vivj∈E除了已给容量Cij外,还给出了单位流量的费用bij(≥)所谓最小费用流问题就是求一个总流量已知的可行流f={fij}使得总费用最小当要求f为最大流时,此问题即为最小费用最大流问题最小费用流问题最小费用流问题例:求下列网络的最小费用流。负回路算法:迭加算法:最小费用流问题PT图定义:一个工程由若干相互独立的活动组成每个活动称为工序我们用顶点表示工序如果工序i完成之后工序j才能启动,则图中有一条有向边(i,j),其权wi表示工序i所需的时间。这样得到的赋权有向图G=(V,E)称为PT图。PT图必定不存在有向回路。在PT图中当起点与终点不唯一时可增加两个虚拟结点v和vn作为新的起点与终点v和vn表示虚工序与v连接的边的权为与vn连接的边的权为原终点工序所需时间。PT图PT图例一项工程由道工序组成,所需时间(单位:天)及先行工序如下表所示(P)工序序号ABCDEFGHIJKLM所需时间先行工序AABC,DDDDG,HGH,EJK试问这项工程至少需要多少天才能完成那些工程不能延误那些工程可以延误最多可延误多少天PT图PT图工序序号ABCDEFGHIJKLM所需时间先行工序AABC,DDDDG,HGH,EJK先作出该工程的PT图ABCDEFGHKNIJLM虚拟结点PT图PT图这项工程至少需要多少天才能完成就是要求A到N的最长路,此路径称为关键路径那些工程不能延误那些工程可以延误最多可延误多少天关键路径上的那些工程不能延误PT图PT图定理若有向图G中不存在有向回路,则可以将G的结点重新编号为u,u,…,un,使得对任意的边uiuj∈E(G),都有i<j关键路径最长路算法各工序最早启动时间算法步骤:①对结点重新编号为u,u,…,un②赋初值(u)=③依次更新(uj),j=,,…,n(uj)=max{(ui)(ui,uj)|uiuj∈E(G)}④结束PT图PT图此例不必重新编号只要按字母顺序即可(A)=,(B)=(C)=,(D)=,(E)=max{,}=,(F)=(G)=(H)=(D)=,(I)=max{(G),(H)}=,(J)=(G)=,(K)=max{(E),(H)}=,(L)=(J)=,(M)=(K)=,(N)=max{(F),(I),(L),(M)}=最早启动时间:PT图PT图这项工程至少需要天才能完成关键路径(最长路径):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延误各工序允许延误时间t(uj)等于各工序最晚启动时间(uj)减去各工序最早启动时间(uj)即t(uj)=(uj)(uj)PT图PT图最晚启动时间算法步骤(已知结点重新编号):①赋初值(un)=(un)②更新(uj),j=n,n,…,(uj)=min{(ui)(ui,uj)|uiuj∈E(G)}③结束根据工序uj允许延误时间t(uj)是否为,可判断该工序是否在关键路径上PT图PT图(N)=,(M)==,(L)==,(K)=(M)=,(J)=(L)=,(I)==,(H)=min{(K),(I)}=,(G)=min{(J),(I)}=,(F)==,(E)=(K)=,(D)=min{(E),(F),(G),(H)}=,(C)=(E)=,(B)=(D)=,(A)=最晚启动时间:PT图PT图各工序允许延误时间如下:t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=,t(C)=,t(F)=,t(G)=,t(I)=,t(J)=,t(L)=PT图PERT图定义:一个工程由若干相互独立的活动组成每个活动称为工序相邻两个工序在时间上的分界点称为事项它表示紧前工序的结束和紧后工序的开始我们用顶点表示事项用有向边表示工序。边的起点称为该工序的开工事项终点称为完工事项用一个顶点表示整个工程计划的开始称为起点事项用另一个顶点表示整个工程计划的结束称为终点事项。这样得到的赋权有向图G=(V,E)称为PERT图。PERT图PERT图图中不能有有向圈与平行边。可引入权为零的虚工序表示工序的衔接关系。()可引入起点事项和终点事项与相应的虚工序。()A,B完成后C才能开始()工序B在工序A部分完工后即可开工(分解为几个子工序)PERT图PERT图事项vk的最早启动时间:表示在整个工程开始后在以vk为完工事项的所有工序如期完成的条件下事项vk的最早执行时间。事项vk的最迟启动时间:表示在不误总工期的条件下以vk为开工事项所有工序如期开工事项vk的最迟执行时间PERT图PERT图事项最早最迟时间递推公式:PERT图PERT图例:已知工序工序时间与紧前工序如表画出工程网络图并求事项的最早时间与最迟时间。PERT图PERT图STEP:给工序分级,逐步去掉紧前工序后没有紧前工序的作为级STEP:按工序级别从左到右排列按工序顺序画网络图STEP:从左到右对事项进行编号PERT图PERT图PERT图PERT图工序的最早开始时间:工序的最早结束时间:工序的最迟开始时间:工序的最迟结束时间:PERT图PERT图工序允许延误时间:总时差:是在不误总工期的条件下工序的开工时间可以推迟的最长时间。局部时差:是在不误所有紧后工序的最早开工时间条件下工序的开工时间可以推迟的最长时间。PERT图PERT图关键路径:从起点事项到终点事项的最长路。关键路径可能不止一条。PERT图PERT图例:求出上题的一些基本参数并确定关键路径。PERT图PERT图工序的最早开始时间:工序的最早结束时间:工序的最迟开始时间:工序的最迟结束时间:总时差:局部时差:事项最早最迟时间:PERT图系统监控问题①若E=Ø,停否则取u∈V,使d(u)=max{d(v)|v∈V}例:假设v,v,…,v是个哨所,监视着条路段(如图所示),为节省人力,问至少需要在几个哨所派人站岗,就可以监视全部路段启发式算法:②令K=K∪{u},G=G{u},转向①系统监控问题系统监控问题例:假设下图代表一指挥系统,顶点v,v,…,v表示被指挥的单位,边表示可以直接下达命令的通信线路欲在某些单位建立指挥站,以便可以通过指挥站直接给各单位下达命令,问至少需要建立几个指挥站启发式算法:①若V=f,停否则取u∈V,使d(u)=max{d(v)|v∈V}②令D=D∪{u},G=G{u,N(u)},转向①系统监控问题着色问题例给相邻顶点着上不同的颜色要求颜色数目最小定理:色数≤maxd(v)近似算法:着色问题wwwshumocn

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/97

数学建模-图论

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利