Home technology picture

picture



Definition

Therearemainlythefollowingtwodefinitions.

Thedefinitionofatwo-tuple

ThegraphGisanorderedtwo-tuple(V,E),whereViscalledtheVerticesSetandEistheedgeset(Edgesset),EandVdonotintersect.TheycanalsobewrittenasV(G)andE(G).Amongthem,theelementsofthetopsetarecalledvertices,andtheelementsoftheedgesetarecallededges.

TheelementsofEarealltwo-tuples,representedby(x,y),wherex,y∈V.

Definitionoftriples

GraphGreferstoatriple(V,E,I),whereViscalledthetopset,Eiscalledtheedgeset,andEandVdoesnotintersect;Iiscalledanassociationfunction,andImapseachelementinEto.Ifeismappedto(u,v),thentheedgeeissaidtoconnecttheverticesu,v,andu,varecalledtheendpointsofe,andu,vareadjacenttoeatthistime.Atthesametime,iftwoedgesiandjhaveacommonvertexu,theniandjaresaidtobeadjacenttou.

Classification

DirectedGraphs,UndirectedGraphs

Ifyouspecifyadirectionforeachedgeofthegraph,thentheresultinggraphiscalledadirectedgraph.Inadirectedgraph,theedgesassociatedwithanodearedividedintooutgoingedgesandincomingedges.Conversely,agraphwhoseedgeshavenodirectioniscalledanundirectedgraph.

Singlegraph

Agraphifthereisonlyoneedgebetweenanytwovertices(inadirectedgraph,thereisonlyoneedgeineachdirectionbetweentwovertices);theedgesetdoesnotcontainTheringiscalledasinglegraph.

Basicterms

Order:ThesizeofthepointsetVinthegraphGiscalledtheorderofthegraphG.

Sub-Graph:WhenthegraphG'=(V',E')whereV'iscontainedinVandE'iscontainedinE,thenG'iscalledgraphG=(V,E)subgraph.Eachgraphisasubgraphofitself.

SpanningSub-Graph:referstothesub-graphG'ofGthatsatisfiestheconditionV(G')=V(G).

InducedSubgraph:Takethenon-emptysubsetV1ofthevertexsetVofthegraphGasthevertexset,andusealltheedgeswithbothendsinV1astheedgesetofthesubgraphofG,ItiscalledthederivedsubgraphderivedfromV1;thenon-emptysubsetE1oftheedgesetEofthegraphGistheedgeset,andalltheverticesassociatedwiththeedgesinE1arethesubgraphsofthevertexsetG,whichiscalledthederivedsubgraphderivedfromE1picture.

Degree:Thedegreeofavertexreferstothenumberofedgesassociatedwiththevertex,andthedegreeofvertexvisdenotedasd(v).

In-degreeandOut-degree:Fordirectedgraphs,thedegreeofavertexcanbesubdividedintoin-degreeandout-degree.Thein-degreeofavertexreferstothenumberofedgeswithitastheendpointamongtheedgesassociatedwithit;theout-degreeisarelativeconcept,whichreferstothenumberofedgeswiththevertexasthestartingpoint.

Loop:Ifthetwoverticesofanedgearethesamevertex,thenthissideiscalledaloop.

Path:Apathfromutovreferstoasequencev0,e1,v1,e2,v2,...ek,vk,wheretheverticesofeiareviandvi-1,Kiscalledthelengthofthepath.Ifitsstartingandendingverticesarethesame,thepathis"closed",otherwise,itiscalled"open".Apathiscalledasimplepath,ifallverticesinthepatharenotequalexceptthatthestartandendverticescanoverlap.

Trace:IftheedgesinthepathP(u,v)aredifferent,thepathiscalledatracefromutov.

Track:IftheverticesinthepathP(u,v)aredifferent,thepathiscalledatrackfromutov.

Aclosedtrackiscalledacircuit,andaclosedtrackiscalledacycle.

(Anotherdefinitionis:walkcorrespondstotheabovepath,pathcorrespondstotheabovetrack.Trailcorrespondstotrace.)

Bridge:Ifoneedgeisremoved,itwillSothattheentiregraphisdisconnected,theedgeiscalledabridge.

Thestoragerepresentationofgraphs

Array(adjacencymatrix)storagerepresentation(directedorundirected)

Adjacencytablestoragerepresentation

Thestoragerepresentationofthecross-linkedlistofadirectedgraph

Thestoragerepresentationofadjacencymultipletablesofanundirectedgraph

Iftwopointsarenotadjacentinanunweightedgraph,thecorrespondingpositionoftheadjacencymatrixis​​0,Fortheweightedgraph(net),thecorrespondingpositionis∞.Theadjacencymatrixrepresentationofagraphisunique,buttheadjacencylistrepresentationisnotunique.Intheadjacencylist,asinglylinkedlistisestablishedforeachvertexinthegraph(andnumberedintheorderofestablishment),andthenodeinthei-thsinglylinkedlistrepresentstheedgeattachedtothevertexvi(foradirectedgraph,thevertexviisTailarc).Eachnodeiscomposedoftwodomains:adjvex,whichisusedtoindicatethepositionofthepointadjacenttoviin​​thegraph,andnextarc,whichisusedtopointtothenextedgeattachedtovertexvi.Node.Iftheadjacencytableisusedtostoretheinformationofthenetwork(weightedgraph),youalsoneedtoaddadomain(info)tostoretheweightinthenode.Thenumberofnodesinthesinglylinkedlistofeachvertexistheout-degreeofthevertex(thetotalnumberofedgesconnectedtothevertex).Regardlessofwhetheritisastoragegraphoranetwork,itisnecessarytosetupaheadernodebeforeeachsinglylinkedlist.Thefirstfielddataoftheseheadernodesisusedtostorethenumberiofthenodevi,andthesecondfieldfirstarcisusedforPointtothefirstnodeinthelinkedlist.

Intheabovetwographstructures,oneisadirectedgraph,thatis,eachsidehasadirection,andtheotherisanundirectedgraph,thatis,eachsidehasnodirection.

Inadirectedgraph,theedgesareusuallycalledarcs,theendcontainingthearrowiscalledthearchead,andtheotherendiscalledthearctail,whichmeansthatthereisanedgefromvertexvitovertexvj.

Iftherearenverticesinadirectedgraph,thereareatmostn(n-1)arcs,andwecalladirectedgraphwithn(n-1)arcsadirectedcompletepicture.Thenumberofarcswithvertexvasthearctailiscalledtheoutdegreeofvertexv,andthenumberofarcswithvertexvasthearcheadiscalledtheindegreeofvertexv.Inanundirectedgraph,theedgeisdenotedas(vi,vj),whichimpliestheexistenceof<vi,vj>andtwoarcs.Iftherearenverticesintheundirectedgraph,thereareatmostn(n-1)/2arcs,andwecalltheundirectedgraphwithn(n-1)/2arcstheundirectedcompletegraph.Thenumberofedgesrelatedtovertexviscalledthedegreeofvertexv.

Pathlengthreferstothenumberofedgesorarcsonthepath.

Ifthefirstvertexisthesameasthelastvertex,thenthispathisaloop.

Iftheverticesinthepathdonotappearrepeatedly,thepathiscalledasimplepath.

Inanundirectedgraph,ifthereisapathfromvertexvitovertexvj,thenviandvjaresaidtobeconnected.Ifanytwoverticesinthegraphareconnected,thegraphiscalledaconnectedgraph,otherwise,themaximalconnectedsubgraphiscalledaconnectedcomponent.

Inadirectedgraph,ifforeachpairofverticesviandvj,therearepathsfromvitovjandfromvjtovi,thenthegraphiscalledastronglyconnectedgraph;otherwise,theThemaximallyconnectedsubgraphsarecalledstronglyconnectedcomponents.

Basicoperationsofgraphs

(1)CreateagraphstructureCreateGraph(G)

(2)RetrieveagivenvertexLocateVex(G,elem)

(3)GetavertexinthegraphGetVex(G,v)

(4)AssignPutVex(G,v,value)tothevertexinthegraph

(5)ReturntothefirstadjacentpointFirstAdjVex(G,v)

(6)ReturntothenextadjacentpointNextAdjVex(G,v,w)

(7)InsertAvertexInsertVex(G,v)

(8)DeleteavertexDeleteVex(G,v)

(9)InsertanedgeInsertEdge(G,v,w)

p>

(10)DeleteanedgeDeleteEdge(G,v,w)

(11)TraversegraphTraverse(G,v)

Spanningtree

Thespanningtreeandforestofthegraph

showsthespanningtreeofanundirectedconnectedgraph,andtheverticesrepresentedbythedoubleloopsaretherootnodesofthespanningtree.

MinimumSpanningTree

Inagraph,eachedgeorarccanhaveavalueassociatedwithit,whichwecallweight.Theseweightscanhavecertainmeanings,suchasthedistancefromonevertextoanother,thetimeittakes,thecostoftheroute,andsoon.Thiskindofweightedgraphisoftencalledanet.

Thespanningtreeofagraphornetisnotunique.Differentspanningtreescanbegeneratedfromdifferentvertices,butaspanningtreewithnnodesmusthaven-1edges

Let'scalculatethesumoftheweightsofthetwospanningtreesabove.Thetotalweightofthefirstspanningtreeis:16+11+5+6+18=56;theweightofthesecondspanningtreeis:16+19+33+18+6=92.Usuallywecallthespanningtreewiththesmallestsumofweightsastheminimumspanningtree.

Themethodofconstructingtheminimumspanningtree:Initiallythespanningtreeisempty,thatis,thereisnonodeandoneedge.Firstselectavertexastherootofthespanningtree,andthenneveramongtheedgesinthespanningtreeeachtimeChooseanedgewiththesmallestpossibleweight.Inordertoensurethattheedgeaddedtothespanningtreedoesnotcausealoop,oneofthetwoverticesadjacenttotheedgemustalreadybeinthespanningtree,andtheothermustnotbeinthespanningtree.Therearenvertices(thenetworkconsideredhereisaconnectedundirectedgraph),thentheminimumspanningtreeofthisnetworkcanbeobtainedbyselectingn-1edgesaccordingtothiscondition.Thedetailedprocesscanbedescribedas:setting2sets,theelementsintheUsetarenodesinthespanningtree,andtheelementsintheV-Usetaretheverticesnotinthespanningtree.Firstselectavertexastherootnodeofthespanningtree,andputitintotheUset,thenfindanedgewiththesmallestweightamongtheedgesintheVUsetattheendvertexintheUsetandtheotherendvertexintheVUset.ThisedgeandthevertexnotintheUsetareaddedtothespanningtree,thatis,theedgeisoutput,andthenitsverticesareaddedtotheUset,andthisoperationisrepeatedn-1times.

Nextweconsiderhowtoimplementthealgorithmofthisoperationprocess.

Analysis:(1)Ithastwomainoperations:selectinganedgeaccordingtoconditionsandaddingverticestotheUset;(2)EachvertexinthenetworkiseitherintheUsetorintheUset.VUcollection.Inordertoimprovethetimeandspaceefficiencyofthealgorithm,wewilldesignanauxiliaryarrayclosedgeforthisalgorithmtorecordtheedgewiththesmallestweightfromthesetUtothesetV-U.ForeachvertexbelongingtotheVUset,thereisacorrespondingcomponentclosedge[i-1]intheauxiliaryarray,whichincludestwofields,onefieldisusedtorepresenttheedgeformedbythevertexandsomeverticesintheVUsetTheweightoftheedgewiththesmallestweightis0ifthevertexenterstheUset;theotherfieldrepresentsthevertexindexintheVUsetcorrespondingtotheedgewiththesmallestweight.Thetypedefinitionisasfollows:

#defineMAX_NUM10struct{intadjvex;floatlowcist;}closedge[MAX_NUM];

Theexecutionprocessoftheentirealgorithmcanbedescribedas:

{initializethecontentsoftheclosedgearray;selectavertexkastherootnodeofthespanningtree,andaddittotheUset;repeatthefollowingoperationsn-1times:lselectanedgethatmeetsthecondition;lOutputthetwoendpointsofthisedge;lModifythevertexinformationintheVUset,thatis,theedgewiththesmallestweightintheUset.}

Assumingthatthenetisgivenintheformofanadjacencymatrix,thecompletealgorithmis:

voidMini_SpanTree(GraphG,intk,intn){//Gistheadjacencymatrixofthenet,Kisthesequencenumberoftherootnodeofthespanningtree,nisthenumberofverticesofthenetworkfor(j=0;j

storagestructure

adjacencymatrix:

YesAdirectedgraphAdjacencyMatrix

Adirectedgraphwithnverticescanberepresentedbyann′nsquarematrix.Suppose.Thenameofthematrixis​​M,thenwhenitisanarcinthedirectedgraph,M[i,j]=1;otherwiseM[i,j]=0.Theoutdegreeofthei-thvertexistheoutdegreeofthei-thvertexinthematrixThenumberof"1"inrowi;thein-degreeisthenumberof"1"inthei-thcolumn,andthenumberofarcsofthedirectedgraphisequaltothenumberof"1"inthematrix.

Theadjacencymatrixoftheundirectedgraph

Theundirectedgraphwithnverticescanalsoberepresentedbyann′nsquarematrix.AssumethatthematrixThenameisM,when(vi,vj)isanedgeintheundirectedgraph,M[i,j]=M[j,i]=1;otherwise,M[i,j]=M[j,j]=0.Thedegreeofthei-thvertexisthenumberof"1"sinthei-throwofthematrixorthenumberof"1"sinthei-thcolumn.Thenumberofedgesinthegraphisequaltothenumberof"1"sinthematrixHalfofthenumber,thisisbecauseeachedgeisdescribedtwiceinthematrix.

IntheClanguage,thetypedefinitionthatimplementstheadjacencymatrixnotationisasfollows:

#defineMAX_VERTEX_NUM20typedefstructgraph{Elemtypeelem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intn;}Graph;

Adjacencytable

Thestructureoftheedgenodeis:

adjvexisthesubscriptofthevertextowhichtheedgeorarcisattachedinthearray,nextisthepointertothenextedgeorarcnode

elemisthevertexcontent,firstedgeisPointertothefirstedgeorarcnode.

InClanguage,thetypedefinitiontorealizetheadjacencylistnotationisasfollows:

#defineMAX_VERTEX_NUM30//MaxNumberofverticestypedefstructEdgeLinklist{//edgenodeintadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//vertexnodeElemtypeelem;EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];

Theimplementationofthealgorithmforcreatingadjacencylistsofdirectedgraphsandundirectedgraphs:

(1)Createadjacencylistsofdirectedgraphs

voidCreate_adj(AdjListadj,intn){for(i=0;iadgvex=j-1;s->next=adj[i-1].firstedge;//ClosethenewarcThepointisinsertedintothecorrespondingpositionadj[i-1].firstegde=s;scanf(&i,&j);//Enterthenextarc}}

(2)CreateanundirectedgraphAdjacencylist

voidCreate_adj(AdjListadj,intn){for(i=0;iadgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2;scanf(&i,&j);}}

Graphtraversal

Therearetwocommongraphtraversalmethods:depth-firsttraversalandbreadthPrioritytraversal,thesetwotraversalmethodsareapplicabletobothdirectedandundirectedgraphs.

Depth-firsttraversal

Theideaof​​depth-firsttraversalissimilartothefirst-ordertraversaloftrees.Thetraversalprocesscanbedescribedas:startingfromacertainvertexvinthegraph,visitingthevertex,andthenproceedingfromtheunvisitedneighboringpointsofvtocontinuethedepth-firsttraversaloftheremainingverticesinthegraphuntilalltheverticesinthegraphhavepathswithvAllconnectedverticeshavebeenvisiteduntiltheend.

Implementationofdepth-firsttraversalalgorithm:

Inordertodistinguishwhetherverticeshavebeenvisitedinthealgorithm,aone-dimensionalarrayvisited[0..n-1](nIsthenumberofverticesinthegraph),usedtosetthevisitflag,itsinitialvaluevisited(0≤i≤n-1)is"0",indicatingthatthevertexwiththesubscriptvalueiintheadjacencylisthasnotbeenvisited,oncetheThevertexisvisited,setvisitedto"1".

intvisited[0..n-1]={0,0,...0};

voidDFS(AdjListadj,intv)

{//visthesubscriptvalueintheadjacencylistofthestartingpointofthetraversal,anditssubscriptstartsfrom0

visited[v]=1;visited(adj[v].elem);

for(w=adj[v].firstedge;w;w=w->next)

if(!visited[w->adjvex])DFS(adj,w->adjvex);

}

Forundirectedgraphs,thisalgorithmcantraversetoalltheverticesintheconnectedcomponentwherethevvertexislocated,andthevvertexisnotthesameAllverticesintheconnectedcomponentscannotbetraversed;andfordirectedgraphs,allverticesthatcanbereachedbythestartingvertexvcanbetraversed.Ifyouwanttotraversealltheverticesinthegraph,youneedtoaddthedetectionoftheaccessstateofeachvertexonthebasisoftheabove-mentioneddepth-firsttraversalalgorithm:

intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);}

Therecursivealgorithmisasfollows:

Booleanvisited[MAX_VERTEX_NUM];//VisitflagarrayStatus(*VisitFunc)(intv);//VisitFuncisthevisitfunction,whichiscalledforeachvertexofthegraphFunctionvoidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//VisitflagarrayInitializefor(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//callDFSforverticesthathavenotbeenvisited)voidDFS(GraphG,intv){//Depth-firsttraversalgraphrecursivelystartingfromthev-thvertexGvisited[v]=TRUE;VisitFunc(v);//Visitthev-thvertexfor(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//FirstAdjVexreturnsthefirstadjacentvertexofv,ifthevertexdoesnothaveanadjacentvertexinG,itreturnsempty(0),//IfwisanadjacentvertexofvVertex,NextAdjVexreturnsthenextadjacentvertexofv(relativetow).//Ifwisthelastadjacentpointofv,returnnull(0).if(!visited[w])DFS(G,w);//CallDFSonv'sunvisitedadjacentvertexw)

Breadth-firsttraversal

ThebreadthofthegraphTheprioritytraversalmethodisdescribedas:startingfromacertainvertexvinthegraph,aftervisitingthevertexv,sequentiallyvisitalltheneighboringpointsofvthathavenotbeenvisited,andthenvisittheneighboringpointsofeachneighboringpoint,andtheorderofaccessshouldbeTheneighboringpointsoftheverticesthatarevisitedfirstarealsovisitedfirst,untilallverticesinthegrapharevisited.Thefollowingistheprocessofbreadth-firsttraversalofanundirectedgraph.

Belowwediscussseveralissuesthatneedtobeconsideredtoimplementthebreadth-firsttraversalalgorithm:

(1)Inthebreadth-firsttraversal,thevertexthatisrequiredtobevisitedfirsthasitsneighborsalsoPriorityaccess,therefore,theaccesssequenceofeachvertexmustberecorded,sothattheneighboringpointsofeachvertexcanbeaccessedinthisorderlater.Aqueuestructureshouldbeusedtorecordtheaccessorderofvertices,andtheoperationalcharacteristicsofthequeuestructurecanbeusedtoenqueueeachverticesvisited,andthendequeueinturn,andvisittheirneighboringpoints;

(2)Inthebreadth-firsttraversalprocess,thesameasthedepth-firsttraversal,inordertoavoidrepeatedvisitstoavertex,aone-dimensionalarrayvisited[0..n-1](nisthenumberofverticesinthegraph)needstobecreatedforRecordwhethereachvertexhasbeenvisited.

intvisited[0..n-1]={0,0,...0};

voidBFS(AdjListadj,intv)

{//visthesubscriptofthestartingpointofthetraversalintheadjacencylist,thesubscriptintheadjacencyliststartsfrom0

InitQueue(Q);//Qisthequeue

visited[v]=1;visite(adj[v].elem);EnQueue(Q,v);

while(!QueueEmpty(Q)){

DeQueue(Q,v);

for(w=adj[v].firstedge;w;w=w->next)

if(!visited[w->adjvex]){

visited[w->adjvex]=1;

visite(adj[w->adjvex].elem);

EnQueue(Q,w->adjvex);}

}

}

Thenon-recursivealgorithmisasfollows:

Booleanvisited[MAX_VERTEX_NUM];//VisitflagarrayStatus(*VisitFunc)(intv);//VisitFuncisthevisitfunction,whichiscalledforeachvertexofthegraphvoidBFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum,++v)visited[v]=FALSE;initQueue(Q);//EmptytheauxiliaryqueueQfor(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(v);EnQueue(Q,v);//vEnqueuewhile(!QueueEmpty(Q)){DeQueue(Q,u);//Theheadoftheteamisdequeuedandsettoufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//wistheadjacentvertexofuthathasnotyetbeenvisitedVisited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);))))

Topologicalsorting

Topologicalsortingisanimportantoperationofdirectedgraphs.InagivendirectedgraphG,ifthevertexsequencevi1,vi2,...,vinmeetsthefollowingconditions:ifthereisapathfromvertexvitovertexvjinthedirectedgraphG,thenvertexvimustbeinthesequenceBeforethevertexvj,thissequenceiscalledatopologicalsequence.Theprocessoffindingthetopologicalsequenceofadirectedgraphiscalledtopologicalsorting.

Example:Partofthecoursesthatcomputermajorsshouldstudyandtheprerequisitecoursesforeachcourse.

Methodoftopologicalsorting:

(1)Selectavertexwithanin-degreeof0fromthegraphandoutputit;

(2)FromthegraphDeletethevertexandallarcswiththevertexasthearctail;

Repeatthesetwostepsuntilallverticesareoutput,andtheoutputsequenceisthetopologyofthisacyclicdirectedgraphsequence.Carefulreadersmayfindthat:ateachmoment,theremaybemultipleverticeswith0indegree.Note:Thec1~c9columnsinthetableindicatetheindegreeofeachvertex.

Nextwediscusshowtoimplementtopologicalsortingalgorithms.Assumethatthedirectedgraphisstoredintheformofanadjacencylist.

Thebasicprocessofthealgorithmimplementationisgivenbelow:

{Putallverticeswithanin-degreeof0intothestack;

RepeatthefollowingwhenthestackisnotemptyOperation:

Exitvertexkfromthestack;

(1)Outputtheinformationofkvertices;

(2)AllverticesadjacenttokThedegreeofentryissubtractedby1.

}

#defineMAX_VERTEX_NUM30//MaximumnumberofverticestypedefstructEdgeLinklist{//edgenodeintadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//VertexnodeElemtypeelem;intindegree;//RecordtheindegreeofthevertexEdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];

Thefollowingisthecompletealgorithmoftopologicalsorting.

StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next)(adj.indegree-=1;if(adj.indegree==0)Push(s,i);}

Importantgraph

Tree

Planargraph

Connectedgraph

p>

Stronglyconnectedgraph

Directedacyclicgraph

AOVnet

AOEnet

Completegraph:eachForagraphwithedgesconnectedbetweendifferentvertices,denoteitasKn.

Bipartitegraph:topset,andeachedgehasavertexinXandanothervertexinY.

Completebipartitegraph:InbipartitegraphG,ifanytwoverticesinXandYareconnectedbyedges.If,thenthegraphGisdenotedasKm,n.

Regulargraph:Ifthedegreesofallverticesinthegraphareequal,thegraphiscalledaregulargraph

Binarygraph

Basicconcepts

Agraphisanorderedpair,Visanodeset,andEisanedgeset.When½V½and½E½arefinite,itiscalledafinitegraph;otherwise,itiscalledaninfinitegraph.

Undirectededges,andAnedgeassociatedwithanunorderednode(v,u);adirectededge,anedgeassociatedwithanorderednode.

Undirectedgraph,eachedgeisanundirectededgegraph,DenotedasG=;eachedgeisagraphwithdirectededges,denotedasD=.

Amixedgraph,whichhasbothdirectededgesandundirectededges.

Atrivialgraph,agraphwithonlyonenode;azerograph,agraphwithanemptysetofedges,thatis,agraphwithonlynodes.

Selfloops(rings),relatedtothesamenodeTheedge.

Undirectedparalleledge,connectingmorethanoneundirectededgeofthesametwonodes;directedparalleledge,connectingmorethanoneanddirectionbetweentwonodesThesamedirectededge.

Simplegraph,withoutparalleledgesandself-loops.

IntheundirectedgraphG=,itisrelatedtothenodev(ÎV)Thenumberofedgesisthedegreeofthenodedeg(v)ord(v).Inadirectedgraph,thesumoftheout-degreeandin-degreeofthenodevisthedegree.

InadirectedgraphInD=,thenumberofedgeswithv(ÎV)asthestartingpointistheoutdegreedeg+(v);thenumberofedgeswithv(ÎV)astheendpointisthein-degreedeg-(v)..

Maximumdegree,D(G)=max{d(v)½vÎV};minimumdegree,d(G)=min{d(v)½vÎV}

WithnnodesandEachpairofnodeshasanedge-connectedundirectedsimplegraph,andanundirectedcompletegraphKn.Atthistimethereis;therearennodesandtherearetwooppositelyconnectededgesbetweeneachpairofnodes.AdirectedsimplegraphThepictureisadirectedcompletegraph.Atthistime,thereare

supposeG=,V,Esub-setV¢,E¢constituteagraphG¢=isasubgraphofgraphG;ifG¢ÍGAndG¢¹G,(V¢ÌVorE¢ÌE),G¢isthepropersubgraphofG.

Generateasubgraph,setG=,ifE¢ÍE,thenthegraphisthegeneratorGraph.Thatis,thesubgraphwiththesamenodeastheoriginalgraphG,inordertogeneratethesubgraph.

Complementgraph`G=,setG=,takeVasthesetofnodes,sothatGbecomesacompletegraph.TheaddededgeisthegraphofedgesetE¢,whichisthecomplementarygraphG¢,.ofgraphG,whichisthecompletegraph,whereEÇE¢=Æ.

Theisomorphismofthegraph,letG1=andG2=,thereisabijectivef:V1®V2,"(vi,vj)ÎE1,ifandonlyif(f(vi),f(vj))ÎE2,and(vi,vj)and(f(vi),fThemultiplicityof(vj))isthesame.ThenG1≌G2.

Sufficientconditionforisomorphism:establishthecorrespondingrelationshipbetweentwographs.Thisrelationshipisabijectivefunction.

IsomorphismNecessaryconditions:①NumberofnodesSame;②Thenumberofsidesisthesame;③Thenumberofnodeswiththesamedegreeisthesame.

Booleanvisited[MAX_VERTEX_NUM];//VisitflagarrayStatus(*VisitFunc)(intv);//VisitFuncisthevisitfunction,CallthefunctionforeachvertexofthegraphvoidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v=0;w=NextAdjVex(G,v,w))//FirstAdjVexreturnsthefirstadjacentvertexofv.IfthevertexhasnoadjacentvertexinG,itreturnsnull(0).//Ifwistheadjacentvertexofv,NextAdjVexreturnsv(relativetow)Anadjacentvertex.//Ifwisthelastadjacentpointofv,returnnull(0).if(!visited[w])DFS(G,w);//CallDFSontheadjacentvertexwofvthathasnotyetbeenvisited}
Booleanvisited[MAX_VERTEX_NUM];//VisittheflagarrayStatus(*VisitFunc)(intv);//VisitFuncisthevisitfunction,whichiscalledforeachvertexofthegraphvoidBFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//wistheadjacentvertexofuthathasnotbeenvisitedVisited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);}}}}
This article is from the network, does not represent the position of this station. Please indicate the origin of reprint
TOP