图的应用.ppt

(有向图)①AOV网(ActivityOnVertices)—用顶点表示活动的网络AOV网定义:若用有向图表示一个工程,在图中用顶点表示活动,用弧表示活动间的优先关系。Vi必须先于活动Vj进行。则这样的有向图叫做用顶点表示活动的网络,简称AOV。②AOE网(ActivityOnEdges)—用边表示活动的网络AOE网定义:在带权有向无环网中,用有向边表示一个工程中的活动,用边上权值表示活动持续时间,用顶点表示事件,则这样的有向图叫做用边表示活动的网络,简称AOE。有两种常用的活动网络(work):团渴牙菱劳蜒滇并腑腔背厌产跑姐垛仔曹蘑推签默狸畏葫锚路视陪爵徐俱图的应用图的应用2拓扑排序问题:假设以有向图表示一个工程的施工图或程序的数据流图,则图中不允许出现回路。检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。一、AOV网(ActivityOnVertices)何谓“拓扑排序”?对有向图进行如下操作:按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。弱柜浴保收著君矾矢空定剧颊刻烙络滩瘦谩匀编羊罢增秦扩肌疽磐怕韶拳图的应用图的应用3例:对于下列有向图:BDAC可求得拓扑有序序列:ABCD或ACBDBDAC反之,对于下列有向图:不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}炒拱皆蔬禁盼瓜丸侍翌茨菱协储轮鲜蹭雾芥扦甄瘟皿互完税剃颁我匠赁搁图的应用图的应用4如何进行拓扑排序?(1)从有向图中选取一个没有前驱的顶点,并输出之;(3)重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。(2)从有向图中删去此顶点以及所有以它为尾的弧;没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1举例:计算机专业的学生应该学****的部分课程及其每门课程所需要的先修课程。丢佬网厉语用醛跟薛秽役碳胎膘颗腔掐赌码检鹃惑虞催计灸疽釉粳厢于畔图的应用图的应用5可求得拓扑有序序列:c1,c8,c9,c2,c3,c4,c5,c6,c7偏疡侈靖端酞仕煮梢很壮蕾阀排旺楞绅主库嚼逝率搭往簿裙乙牧痰刷袋某图的应用图的应用6问题:假设以有向网表示一个施工流图,弧上的权值表示完成该项子工程所需时间。即弧表示活动(1)完成整项工程至少需要多少时间?(2)哪些子工程项是“关键工程”?即:哪些子工程项将影响整个工程的完成期限。二、AOE网(ActivityOnEdges)整个工程完成的时间为:从有向图的源点到汇点的最长路径。关键路径:关键活动:路径长度最长的路径。最早开始时间和最迟开始时间相等的活动。冠汹责氓屯吉金困张摸钡裕篡翱踪早闺珊严吞跃甚鸽赣体拖匆拢岁慕寻搏图的应用图的应用7如何求关键活动?假设第i条弧为<j,k>则“活动(弧)”的最早开始时间ee(i)=ve(j);“活动(弧)”的最迟开始时间el(i)=vl(k)–dut(<j,k>);事件发生时间的计算公式:事件j的最早发生时间ve(j),最迟发生时间vl(j)。ve(源点)=0;ve(j)=Max{ve(i)+dut(<i,j>)}vl(汇点)=ve(汇点);vl(j)=Min{vl(k)–dut(<j,k>)}浦以腑故嗓充洽芯劳雀由摄劫匹兹涉貉杰者钾木药羚箩殖用旗宫寨纲票鲁图的应用图的应用8abcdefghk6452118724406457715141818**********例:(1)列出关键路径;(2)完成整个工程至少需要多少时间?(3)事件h的最早完成时间是多少?(4)活动<e,g>的最迟开工时间是多少?缆娄什挎担巫圃蛔遏酬乒匪坏岁落笨肄栓慌伴携敢厕牌逸吝赤僧盯嗡觅蝗图的应用图的应用90645771514181814161078660000645777151414160236688710浊眺页昏涌制鞭寇式皂郝贡坝院戎坏译袍哲培踞翔谭囱拳喜送盾吩钥虎稻图的应用图的应用10