离散数学课件(英文版)----Graph.ppt

《离散数学课件(英文版)----Graph.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GraphsLecture9DiscreteMathematicalStructuresCDABProblemof“CrossingRiver”Problem:Aperson(P),awolf(W),alamb(L)andacabbage(C)willcrossariverbyaboatwhichcancarryanytwoofthemonce.Wolfandlamb,or,lambandcabbage,cannotstaytogetherwithoutthepersonpresent.Reme

2、mberthatonlythepersoncanruntheboat.SevenBridgesatKönigsbergAbstractionVerticesrepresentingobjects-areasEdgesrepresentingtherelationshipbetweenobjects–connectedbyabridgeGraphandDiagramGraphGisatriple:G=〈VG,EG,〉VGandEGaresets，satisgyingVG⋂EG=,:EG{{

3、vi,vj}

4、vi,vjVG}Note:{vi,vj}={vj,vi}Agraphcanberepresentedconvenientlybysomediagram::eachelementofVGasadot,thevertex,andeachelementofEGasalinesegment,theedge,betweentwovertices.So,VGiscalledthesetofvertices,andEG,thesetofedges.RelationsinGraphRelatio

5、ndefinedfromedgesettotheCartesianproductofvertexsetIncidenceRelationdefinedonthesetofverticesAdjacencyConsideringtherelationsabove,agraphcanberepresentedbymatrix.SimpleGraphMultipleedgesandringIfisnotainjection,thatis,existei,ejEG,eiej,but(ei)=(

6、ej),thenei,ej是arecalledmultipleedges.。ForanyeiEG,if(ei)={vi,vi}={vi},theneiiscalledaring.SimplegraphAgraphwithoutringandmultipleedgesiscalledasimplegraph.DegreeofVertexDegreeofvertexdG(v)=numberofedgeincidenttovdG(v)mustbeanonnegativeinteger.Numeri

7、calcharacteristicsofthedegreeofvertexSumofdegreeofallverticesinagraphiseven.misthenumberofedgesinthegraph.Thenumberofverticeswithodddegreemustbeeven.CompleteGraphAgraphisacompletegraphifandonlyifanytwoofitsverticesareadjacent.Inthesenseofisomorphism,

8、foragivenn,thereisexactlyonecompletegraph,denotedasKn,wherenisthenumberofverticesinthegraph.InKn,foranyvertexv,d(v)=n-1.ThenumberofedgesinKnisexactlyn(n-1)/2.IfGisasimplegraph,thenthenumberofitsedgesmn(n-1)/2CompleteGraphKn(n=1,2,3,4,5)AgraphGandits

9、complementgraphhavethesamesetofvertex,andtheiredgessetconstituteapartitionoftheedgesetofthecompletegraphwiththesamevertexset.K1K2K3K5K4RegularGraphTwotypicalregulargraph:Note:inthegraphontheleft,eachvertexisabinarynumberwiththesamenumberofbits.000010