futher mathematics topic 10 directed graphs

《futher mathematics topic 10 directed graphs》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Topic10Directedgraphsandnetwork有向图，有向网络10.1KickoffwithCAS10.2Criticalpathanalysis关键路径分析10.3Criticalpathanalysiswithbackwardscanningandcrashing10.4Networkflow网络流10.5Assignmentproblemsandbipartitegraphs分配问题和二部图10.6Review10.2CriticalpathanalysisActivitych

2、arts活动图表immediatepredecessor直接前趋directedgraph有向图forwardscanning正向扫描earlieststarttime最早的开始时间criticalpaths关键路径floattime浮动时间lateststarttime最迟开始时间ConsiderFrieda’smorningschedule,wheresheneedstoeathercookedbreakfast,downloadheremailandreadheremail.Thefirsttw

3、otaskstake6minutesand1minuterespectively,whilethelasttakes2minutes.Friedaneedstocompleteallthesetasksin7minutes.Howmightsheaccomplishthis?activityBistheimmediatepredecessorofactivityC.TimeActivityActivity1stminuteDownloademail2ndminuteEatbreakfast3rdmin

4、uteEatbreakfast4thminuteEatbreakfast5thminuteEatbreakfastReademail6thminuteEatbreakfastReademail7thminuteEatbreakfastBecauseoftheimplieddirection,thesenetworksarecalleddirectedgraphsordirectednetworks.(Theedgesinadirectedgraphrepresentaone-waypathbetwee

5、nthenodes,ascomparedwithundirectedgraphswheretheedgesrepresentatwo-waypathbetweenthenodes.)Theearlieststarttime(EST)istheearliestthatanyactivitycanbestartedafterallprioractivitieshavebeencompleted.Obviously,theESTforthefirstactivityis0.Theearlieststartt

6、imeofactivityX(ESTX)isrecordedinthetriangleprecedingtheedgeExample1重点讲解UseforwardscanningtodeterminetheearliestcompletiontimeforFrieda’sinitialthreetasks.LetusnowextendFrieda’sactivitycharttoamorecomplexsetofactivitiesforhermorningroutineExample2Usingal

7、ltheactivitieslistedinFrieda’smorningroutine,findtheearliestcompletiontimeandhenceidentifythosetasksthatmaybedelayedwithoutextendingthecompletiontime.CriticalpathsThepaththroughthenetworkwhichfollowsthoseactivitiesthatcannotbedelayedwithoutcausingtheent

8、ireprojecttobedelayediscalledthecriticalpath.FloattimeandlateststarttimeFloattime(浮动时间）isthedifferenceintimebetweenthosepathsthatcannotbedelayedandthosethatcan.FloattimeandlateststarttimeThelateststarttime(最晚开始时间）forsuchactivitie