【精品数据结构】graphs

《【精品数据结构】graphs》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter12GraphsMaintopicsDefinitionofgraphsandsometerminologyThreecommongraphrepresentationsSomealgorithms12.1DefinitionandterminologiesDefinitionofgraphs:Graph=(V,E)V:nonemptyfiniteverticesetE:edgesetUndirectedpraph:Ifthetupledenotinganedgeisunordered,then(v1,v2)and(v2,v1

2、)arethesameedge.12.1DefinitionandterminologiesDirectedgraph:Ifthetupledenotinganedgeisordered,then(v1,v2)and(v2,v1)aredifferentedges.12.1DefinitionandterminologiesExample:V2V4V3V1V(G1)={V1,V2,V3,V4}E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}V1V2V(G2)={V1,V2,,V3

3、}E(G2)={,,}V312.1DefinitionandterminologiesWewillnotdiscussgraphsofthefollowingtypes12.1Definitionandterminologies2.CompletegraphInanundirectedgraphwithnnodes,thenumberofedges<=n*(n-1)/2.If“=“issatisfied,thenitiscalledacompleteundirectgraph.V2V4V3V112.

4、1DefinitionandterminologiesInadirectedgraphwithnnodes,thenumberofedges<=n*(n-1).If“=“issatisfied,thenitiscalledacompletedirectedgraph.12.1Definitionandterminologies3.degreediofvertexi,TD(v):isthenumberofedgesincidentonvertexi.Inadirectedgraph:in-degreeofvertexiisthenumbero

5、fedgesincidenttoi,ID(v).out-degreeofvertexiisthenumberofedgesfromthei,OD(v).12.1DefinitionandterminologiesTD(v)=ID(v)+OD(v)Generally,iftherearenverticesandeedgesinagraph,thene=(TD(vi))/2v1v2v3ID(v2)=1OD(v2)=2TD(v2)=3i=1n12.1Definitionandterminologies4.SubgraphGraphG=(V,E)

6、,G’=(V’,E’),ifV’V,E’E,andtheverticesincidentontheedgesinE’areinV’,thenG’isthesubgraphofG.Forexample:134211331412.1DefinitionandterminologiesAnotherexample:V2V4V3V1V2V3V1V112.1Definitionandterminologies5.path.AsequenceofverticesP=i1,i2,……ikisani1toikpathinthegraphofdigrap

7、hG=(V,E)ifftheedge(ij,ij+1)isinEforeveryj,1<=j

8、7.Connectedgraph&connectedcomponentInaundirectedgraph,ifthereisapathfromvertexv1tov2,then