资源描述:
《离散数学课件(英文版)----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,vjVG}Note:{vi,vj}={vj,vi}Agraphcanberepresentedconvenientlybysomediagram::eachelementofVGasadot,thevertex,andeachelementofEGasalinesegment,theedge,betweentwovertices.So,VGiscalledthesetofvertices,andEG,thesetofedges.RelationsinGraphRelatio
5、ndefinedfromedgesettotheCartesianproductofvertexsetIncidenceRelationdefinedonthesetofverticesAdjacencyConsideringtherelationsabove,agraphcanberepresentedbymatrix.SimpleGraphMultipleedgesandringIfisnotainjection,thatis,existei,ejEG,eiej,but(ei)=(
6、ej),thenei,ej是arecalledmultipleedges.。ForanyeiEG,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,thenthenumberofitsedgesmn(n-1)/2CompleteGraphKn(n=1,2,3,4,5)AgraphGandits
9、complementgraphhavethesamesetofvertex,andtheiredgessetconstituteapartitionoftheedgesetofthecompletegraphwiththesamevertexset.K1K2K3K5K4RegularGraphTwotypicalregulargraph:Note:inthegraphontheleft,eachvertexisabinarynumberwiththesamenumberofbits.000010