下载此文档

大叶大学.ppt


文档分类:幼儿/小学教育 | 页数:约30页 举报非法文档有奖
1/30
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/30 下载此文档
文档列表 文档介绍
GraphTheory Chapter4 PathsandDistance inGraphs大葉大學 資訊工程系 :puter:AmessagemustbesentfromaprocessorP1 toaprocessorP2intheminimumpossible ?10processors兩點連線表示 彼此可溝通每條邊所需的 溝通時間相同FindshortestP1-:ForanontrivialgraphGandapairu,vofverticesofG,thedistancedG(u,v)(ord(u,v)ifthegraphGisclearfromcontext)betweenuandvisthelengthofashortestu--vpath,thenwedefine d(u,v)=∞.G1:vuG2:yxd(x,y)=∞d(u,v)=24Definition:ThedistancefunctiononagraphGisametric,thatis,itmapsV(G)V(G)tothesetofnonnegativeintegersandsatisfiesthefollowingfundamentalproperties:(接下頁):(i)d(u,v)0,andd(u,v)=0iffu=v;(ii)d(u,v)=d(v,u)forallu,vV(G);(iii)d(u,v)d(u,w)+d(w,v)forallu,v,wV(G)(thetriangleinequality).Pf:[(i)and(ii),seeproblem1.](iii),weproceedasfollows:Letu,v,–wpathandQashortestw––vwalk,sayW,havinglengthd(u,w)+d(w,v).SinceWcontainsau–vpath(),itfollowsthatd(u,v)d(u,w)+d(w,v).6Definition:ForadirectedgraphD,the(directed)distancedD(u,v)(ord(u,v))fromvertexutovertexvofDisthelengthofashortestdirectedu-vpathifsuchapathexists,andis∞:zwxvuyd(u,v)=∞d(u,z)=(Moore’sBreadth-FirstSearchAlgorithm)Foreveryvertexwu,letl(w)←∞.Further,letl(u)←,thendeleteavertexxfromQ; otherwise,stop,sincethereisnou-(y)=∞,assignPARENT(y)←x,letl(y)←l(x)+(v)=∞,thenreturnStep2;otherwise,←l(v)anduk←0,thenuk-1←PARENT(uk);←k-,u1,…,uk,whichisashortestu–vpath.(Forgivenuv,findd(u,v)andashortestu-vpath.)l(v)即是d(u,v)u,letl(u)←.Further,letl(u)←,=,thenoutputthepairsv,l(v)forallve

大叶大学 来自淘豆网www.taodocs.com转载请标明出处.