Directedgraphsaregraphsinwhichtheedgesareone-Way.Suchgraphsarefrequentlymoreusefulinvarious

Directed Graphs

1 INTRODUCTION

Directedgraphsaregraphsinwhichtheedgesareone-way.Suchgraphsarefrequentlymoreusefulinvarious dynamicsystemssuchasdigitalcomputersorflowsystems.However,thisaddedfeaturemakesitmoredifficult todeterminecertainpropertiesofthegraph.Thatis,processingsuchgraphsmaybesimilartotravelinginacity with manyone-waystreets.

Thischaptergivesthebasicdefinitions andproperties ofdirectedgraphs.Manyofthedefinitions willbe similartothoseintheprecedingchapteron(non-directed)graphs.However,forpedagogicalreasons,thischapter will bemainlyindependentfromtheprecedingchapter.

2 DIRECTEDGRAPHS

AdirectedgraphGordigraph(orsimplygraph)consistsoftwothings: (i) AsetVwhoseelementsarecalledvertices,nodes,orpoints.

(ii) AsetEoforderedpairs(u, v)ofverticescalledarcs ordirectededgesorsimplyedges.

WewillwriteG(V,E)whenwewanttoemphasizethetwopartsofG.WewillalsowriteV(G)andE(G) to denote,respectively,thesetofverticesandthesetofedgesofagraphG.(Ifitisnotexplicitlystated,thecontext usually determineswhetherornotagraphGisadirectedgraph.)

Supposee=(u,v)isadirectededgeinadigraphG.Thenthefollowingterminologyisused: (a) ebegins atuandendsatv.

(b) uistheoriginorinitialpointofe,andvisthedestinationorterminalpointofe.

(c) visasuccessorofu.

(d) uisadjacenttov,andvisadjacentfromu. If u=v,theneiscalledaloop.

Thesetofallsuccessorsofavertexuisimportant;itisdenotedandformallydefinedby succ(u)={v∈V|thereexistsanedge(u,v)∈E}

Itiscalledthesuccessorlistoradjacencylistofu.

ApictureofadirectedgraphGisarepresentationofGintheplane.Thatis,eachvertexuofGisrepresented bya dot(orsmallcircle),andeach(directed)edgee=(u,v)is representedbyanarrowordirectedcurvefrom

theinitialpointuofetotheterminalpointv.OneusuallypresentsadigraphGbyitspictureratherthanexplicitly listing itsverticesandedges.

Iftheedgesand/orverticesofadirectedgraphGarelabeledwithsometypeofdata,thenGiscalled a labeleddirectedgraph.

Adirectedgraph(V,E)issaidtobefiniteifitssetVofverticesanditssetEofedgesarefinite.

EXAMPLE 1

(a) ConsiderthedirectedgraphGpicturedinFig. 1(a).Itconsistsoffourvertices,A,B,C,D,thatis,

V(G)={A,B,C,D}andthesevenfollowingedges:

E(G) ={e1,e2,...,e7}={(A,D),(B,A),(B,A),(D,B),(B,C),(D,C),(B,B)}

Theedgese2 ande3 aresaidtobeparallelsincetheybothbeginatBandendatA.Theedgee7 isaloop

sinceitbeginsandendsatB.

Fig. 1

(b) Supposethreeboys,A,B,C,arethrowinga balltoeachothersuchthatAalwaysthrowstheballtoB, but BandCarejustaslikelytothrowtheballtoAastheyaretoeach other.This dynamicsystemispictured inFig. 1(b)whereedgesare labeledwiththe respectiveprobabilities,thatis,Athrowsthe ballto Bwith probability1,BthrowstheballtoAandCeachwithprobability1/2,andCthrowstheballtoAandBeach with probability1/2.

Subgraphs

LetG=G(V,E)beadirectedgraph,andletV beasubsetofthesetVofverticesofG.Suppose E is asubsetofEsuchthattheendpointsoftheedgesinE belongtoV .ThenH(V ,E)isadirected graph,and itiscalled asubgraphofG.Inparticular,ifE containsalltheedges inEwhose endpointsbelong toV ,then

H(V ,E)iscalledthesubgraphofGgeneratedordeterminedbyV .Forexample,forthegraphG=G(V,E)

inFig. 1(a),H(V ,E)isthesubgraphofGdeterminebythevertexsetV where

V ={B,C,D}and E =(e4, e5, e6, e7)={(D,B),(B,C),(D,C),(B,B)}

3 BASICDEFINITIONS

This section discusses the questions of degrees of vertices, paths, and connectivity in a directed graph.

Degrees

SupposeGisadirectedgraph.Theoutdegreeof avertexvof G,writtenoutdeg(v),isthe numberof edges beginningatv,andtheindegreeofv,writtenindeg(v),isthenumberofedgesendingatv.Sinceeachedgebegins and endsatavertexweimmediatelyobtainthefollowingtheorem.

Theorem 1: The sum oftheoutdegreesoftheverticesofadigraphGequalsthesum oftheindegreesofthe vertices, whichequalsthenumberofedgesinG.

Avertexvwithzeroindegreeiscalledasource,andavertexvwithzerooutdegreeiscalledasink.

EXAMPLE 2 ConsiderthegraphGinFig. 1(a).Wehave:

outdeg(A)=1,outdeg(B)=4,outdeg(C)=0,outdeg(D)=2,

indeg(A)=2,indeg(B)=2,indeg(C)=2,indeg(D)=1.

Asexpected,thesumoftheoutdegreesequalsthesumoftheindegrees,whichequalsthenumber7ofedges. The vertexCisasinksincenoedgebeginsatC.Thegraphhasnosources.

Paths

LetGbeadirectedgraph.Theconceptsofpath,simplepath,trail,andcyclecarryoverfromnondirected graphstothedirectedgraphGexceptthatthedirectionsoftheedgesmust agree with thedirectionofthepath. Specifically:

(i) A(directed)pathPinGisanalternatingsequenceofverticesanddirectededges,say,

P = v0, e1, v1, e2, v2,...,en, vn

suchthateachedgeeibeginsatvi−1andendsatvi.Ifthereisnoambiguity,wedenotePbyitssequence of verticesoritssequenceofedges.

(ii) ThelengthofthepathPisn,itsnumberofedges.

(iii) Asimplepathisapathwithdistinctvertices.Atrailisapathwithdistinctedges. (iv) Aclosedpathhasthesamefirstandlastvertices.

(v) AspanningpathcontainsalltheverticesofG.

(vi) Acycle(orcircuit)isaclosedpathwithdistinctvertices(exceptthefirstandlast).

(vii) Asemipathisthesameasapathexcepttheedgeei maybeginatvi−1orvi andendattheothervertex.

Semitrailsandsemisimplepathsareanalogouslydefined.

Avertexvisreachablefromavertexuifthereisapathfromutov.Ifvisreachablefromu,then(byeliminating redundant edges)theremustbeasimplepathfromutov.

EXAMPLE 3 ConsiderthegraphGinFig. 1(a).

(a) ThesequenceP1 =(D,C,B,A)isasemipathbutnotapathsince(C,B)isnotanedge;thatis,thedirection of e5 =(C,B)doesnotagreewiththedirectionofP1.

(b) The sequenceP2 =(D,B,A)isapath fromDtoAsince(D, B)and (B,A)areedges.ThusAisreachable from D.

Connectivity

TherearethreetypesofconnectivityinadirectedgraphG:

(i) Gisstronglyconnectedorstrongif,foranypairofverticesuandvinG,thereisapathfromutov

andapathfromvtou,thatis,eachisreachablefromtheother.

(ii) Gisunilaterally connectedorunilateralif,foranypairofvertices uandvinG,thereisapathfrom

utovorapathfromvtou,thatis,oneofthemisreachablefromtheother.

(iii) GisweaklyconnectedorweakifthereisasemipathbetweenanypairofverticesuandvinG.

LetG bethe(nondirected)graphobtainedfromadirectedgraphGbyallowingalledgesinGtobenondirected. Clearly, GisweaklyconnectedifandonlyifthegraphG isconnected.

Observethatstronglyconnectedimpliesunilaterallyconnectedwhichimpliesweaklyconnected. Wesay thatGisstrictlyunilateralifitisunilateralbutnotstrong,andwesaythatGisstrictlyweakifitisweakbutnot unilateral.

Connectivitycanbecharacterizedintermsofspanningpathsasfollows:

Theorem 2: LetGbeafinitedirectedgraph.Then:

(i) GisstrongifandonlyifGhasaclosedspanningpath. (ii) GisunilateralifandonlyifGhasaspanningpath.

(iii) GisweakifandonlyifGhasaspanningsemipath.

EXAMPLE 4 ConsiderthegraphGinFig. 1(a).Itisweakly connectedsincetheunderlyingnondirected graphisconnected.ThereisnopathfromCtoanyothervertex,thatis,Cisasink,soGisnotstronglyconnected.

However,P=(B,A,D,C)isaspanningpath,soGisunilaterallyconnected.

Graphswithsourcesandsinksappearinmanyapplications(suchasflowdiagramsandnetworks).Asufficient condition forsuchverticestoexistfollows.

Theorem 3: SupposeafinitedirectedgraphGiscycle-free,thatis,containsno(directed)cycles.ThenG

containsasourceandasink.

Proof:LetP=(v0 ,v1,...,vn )beasimple pathofmaximumlength, which exists sinceGisfinite.Thenthe lastvertexvn isasink;otherwiseanedge(vn, u)willeitherextendPorformacycleifu=vi,forsomei.

Similarly,thefirstvertexv0 isasource.

5 SEQUENTIALREPRESENTATIONOFDIRECTEDGRAPHS

Therearetwo mainwaysofmaintainingadirectedgraphGinthememoryofacomputer.One way,called thesequential representationofG,isbymeansofitsadjacency matrix A.Theotherway,calledthelinked representationofG,isbymeansoflinkedlistsofneighbors.Thissectioncoversthefirstrepresentation.The linked representationwillbecoveredinSection 7.

SupposeagraphGhasmvertices(nodes)andnedges.WesayGisdenseifm=O(n2)andsparseif

m=O(n)orevenifm=O(nlogn).ThematrixrepresentationofGisusuallyusedwhenGisdense,and

linkedlistsareusuallyusedwhenGissparse.Regardless ofthewayonemaintainsagraphGinmemory,the

graphGisnormallyinputintothecomputerbyitsformaldefinition,thatis,asacollectionofverticesanda collection ofedges(pairsofvertices).

Remark: Inordertoavoidspecialcasesofourresults,weassume,unlessotherwisestated,thatm1wherem

isthenumberofverticesinourgraphG.Therefore,GisnotconnectedifGhasnoedges.

DigraphsandRelations,AdjacencyMatrix

LetG(V,E)beasimpledirectedgraph,thatis,agraphwithoutparalleledges.ThenEissimplyasubset ofV×V,andhenceEisarelationonV.Conversely,ifRisarelationonasetV,thenG(V,R)isasimple

directedgraph.Thusthe conceptsof relationson aset andsimpledirectedgraphsare oneandthe same.In fact, in Chapter2,wealreadyintroducedthedirectedgraphcorrespondingtoarelationonaset.

SupposeGisasimpledirectedgraphwithmvertices,andsupposetheverticesofGhavebeenorderedand are calledv1,v2,…,vm.ThentheadjacencymatrixA=[aij]ofGisthem×mmatrixdefinedasfollows:

1 ifthereisanedge(vi,vj)

aij =

0 otherwise

Sucha matrixA, whichcontainsentriesofonly0 or1, is calleda bitmatrixora Booleanmatrix.(Althoughthe adjacency matrixofanundirectedgraphissymmetric,thisisnottruehereforadirectedgraph.)

Theadjacencymatrix AofthegraphGdoesdependontheorderingoftheverticesofG.However,the matricesresultingfromtwodifferentorderingsarecloselyrelatedinthatonecanbeobtainedfromtheotherby simplyinterchangingrowsandcolumns.Unlessotherwisestated,weassumethattheverticesofourmatrixhave a fixedordering.

Remark: TheadjacencymatrixA=[aij]maybeextendedtodirectedgraphswithparalleledgesbysetting:

aij =thenumberofedgesbeginningatvi andendingatvj

Thenthe entriesofAwillbe nonnegativeintegers.Conversely,everym×mmatrixAwithnonnegativeinteger

entriesuniquelydefinesadirectedgraphwithmvertices.

EXAMPLE 6 LetGbethedirectedgraphinFig. 4(a)withverticesv1,v2,v3,v4.Thentheadjacencymatrix

AofGappearsinFig. 4(b).Notethatthenumberof1’sinAisequaltothenumber(eight)ofedges.

Fig. 4

ConsiderthepowersA,A2, A3,…oftheadjacencymatrixA=[aij]ofagraphG.Let

aK(i,j)=theijentryinthematrixAK

Notethata1(i,j)=aij givesthenumberofpathsoflength1fromvertexvi tovertexvj.Onecanshowthat a2(i,j)givesthenumberofpathsoflength2fromvi tovj.Infact,weproveinProblem 17thefollowing general result.

Proposition 4: LetAbetheadjacencymatrixofagraphG.ThenaK(i,j),theijentryinthematrixAK ,gives the numberofpathsoflengthKfromvi tovj.

EXAMPLE 7 ConsideragainthegraphGand itsadjacencymatrixAappearinginFig. 4.The powersA2,

A3, andA4 ofAfollow:

⎡ 10⎤⎡ 1

2⎤⎡ 21⎤

A2 =⎢ 2

2⎥,A3 =⎢ 3

3⎥,A4 =⎢ 55⎥

⎢⎥⎢⎥⎢⎥

⎣⎦⎣⎦⎣⎦

1 0 0 2

2 0 2 1

3 0 1 4

Observethata2 (4,1)=1,sothereisapathoflength2fromv4 tov1.Also,a3(2,3)=2,sotherearetwopaths of length3fromv2 tov3;anda4(2,4)=5,sotherearefivepathsoflength4fromv2 tov4.

Remark: LetAbetheadjacencymatrixofagraphG,andletBr bethematrixdefinedby:

Br =A+A2 +A3 +···+Ar

ThentheijentryofthematrixBr givesthenumberofpathsoflengthrorlessfromvertexvi tovertexvj.

PathMatrix

LetG =G(V,E)beasimpledirectedgraphwithmverticesv1,v2,.. .,vm.Thepathmatrixorreachability matrix ofGisthem-squarematrixP=[pij]definedasfollows:

1 ifthereisapathfromtovi tovj

pij =

0 otherwise

(ThepathmatrixPmaybeviewedasthetransitiveclosureoftherelationEonV.)

Supposenow that thereisapath fromvertexvi tovertexvj inagraphGwithmvertices.Thentheremust bea simplepathfromvi tovj whenvi =vj, ortheremustbea cyclefromvi tovj whenvi =vj. SinceGhasmvertices,suchasimplepath musthavelengthm−1orless, orsuchacyclemusthavelengthmorless.This

meansthatthereisanonzeroijentryinthematrixBm (definedabove)where AistheadjacencymatrixofG. Accordingly, thepathmatrixPandBm havethesamenonzeroentries.Westatethisresultformally.

Proposition 5: LetAbetheadjacencymatrixofagraphGwithmvertices.ThenthepathmatrixPandBm

havethesamenonzeroentrieswhere

Bm =A+A2 +A3 +···+Am

RecallthatadirectedgraphGissaidtobestronglyconnectedif,foranypairofverticesuandvinG,there isa pathfromu tovandfromvtou.Accordingly,G is stronglyconnectedif andonlyif thepathmatrixP ofG has nozeroentries.ThisfacttogetherwithProposition 5givesthefollowingresult.

Proposition 6: LetAbetheadjacencymatrixofagraphGwithmvertices.ThenGisstronglyconnectedif and onlyifBm hasnozeroentrieswhere

Bm =A+A2 +A3 +···+Am

EXAMPLE 8 ConsiderthegraphGanditsadjacencymatrixAappearinginFig. 4.HereGhasm=4 vertices.Adding thematrixAandmatricesA2,A3,A4 inExample 7,weobtainthefollowingmatrixB4 and also path(reachability)matrixPbyreplacingthenonzeroentriesinB4 by1:

⎡ 40 3 4 ⎤

11 0 7 11

⎡ 1 0 1 1⎤

1 0 1 1

B4 =⎢

⎥and P=⎢⎥

⎢ 70 4 7 ⎥

⎣⎦

70 4 7

⎢ 1 0 1 1⎥

⎣⎦

1 0 1 1

ExaminingthematrixB4 orP, weseezeroentries;henceG is notstronglyconnected.Inparticular,weseethat the vertexv2 isnotreachablefromanyoftheothervertices.

Remark: TheadjacencymatrixAandthepathmatrixPofagraphGmaybeviewedaslogical(Boolean)

matriceswhere0represents“false”and1represents“true.”Thusthelogicaloperationsof∧(AND)and

∨(OR)maybeappliedtotheentriesofAandPwheretheseoperations,usedinthenextsection,aredefined

inFig. 5.

Fig. 5

TransitiveClosureandthePathMatrix

LetRbe arelationon afinitesetVwithmelements.As notedabove,the relationRmaybe identifiedwith thesimpledirectedgraphG=G(V,R).WenotethatthecompositionrelationR2 =R×Rconsistsofallpairs

(u, v)suchthatthereisapathoflength2fromutov.Similarly:

RK ={(u,v)|thereisapathoflengthKfromutov}.

ThetransitiveclosureR*oftherelationRonVmaynowbeviewedasthesetoforderedpairs(u,v)suchthat thereisapathfromutovinthegraphG.Furthermore,bytheabovediscussion, weneedonlylookatsimple

pathsoflength m −1orlessandcycles oflength morless.Accordingly,wehavethefollowingresultwhich

characterizesthetransitiveclosureR*ofR.

Theorem 7: LetRbearelationonasetVwithmelements.Then:

(i) R∗=R∪R2 ∪...∪Rm isthetransitiveclosureofR.

(ii) ThepathmatrixPofG(V,R)istheadjacencymatrixofG(V,R*).

6 WARSHALL’SALGORITHM,SHORTESTPATHS

LetGbeadirectedgraphwithmvertices,v1,v2,...,vm.SupposewewanttofindthepathmatrixPofthe graph G.Warshallgaveanalgorithmwhichismuchmoreefficientthancalculatingthepowersoftheadjacency matrixA.Thisalgorithmisdefinedinthissection,andasimilaralgorithmisusedtofindshortestpathsinGwhen G isweighted.

Warshall’sAlgorithm

Firstwedefinem-squareBooleanmatricesP0,P1,.. .,Pm wherePk[i,j]denotestheijentryofthe matrix Pk:

Forexample,

Pk[i,j]=

⎧1 ifthereisasimplepathfromvi tovj whichdoesnotuseany

⎨otherverticesexceptpossiblyv,v,…,v

⎩0 otherwise.

P3[i,j]=1 ifthereisasimplepathfromvi tovj whichdoesnotuseany

otherverticesexceptpossiblyv1,v2,v3.

Observethatthefirstmatrix P0 =A,theadjacencymatrixofG.Furthermore,since Ghasonly mvertices,the last matrixPm =P, thepathmatrixofG.

WarshallobservedthatPk[i,j]=1canoccuronlyifoneofthefollowingtwocasesoccurs:

(1) Thereisasimplepathfromvi tovj whichdoesnotuseanyothervertices exceptpossiblyv1,v2,…,vk−1;

hence

Pk−1[i,j]=1

(2) Thereisasimplepathfromvi tovk andasimplepathfromvk tovj whereeachsimplepathdoesnotuse any otherverticesexceptpossiblyv1, v2,…,vk−1;hence

Pk−1[i,k]=1 and Pk−1[k,j]=1

Thesetwocasesarepicturedasfollows:

(1)vi →···→vj;(2)vi →···→vk →···vj

where→···→denotespartofasimplepathwhichdoesnotuseanyotherverticesexceptpossibly v1,v2,…,

vk−1.Accordingly,theelementsofPk canbeobtainedby:

Pk[i,j]=Pk−1[i,j]∨(Pk−1[i,k]∧Pk−1[k,j])

where weusethelogical operationsofa∧(AND)and∨(OR). Inotherwords wecanobtain eachentryinthe matrix Pk bylookingatonlythreeentriesinthematrixPk−1.Warshall’salgorithmappearsinFig. 6.

Fig. 6

Shortest-pathAlgorithm

LetGbeasimpledirectedgraphwithmvertices,v1,v2,.. .,vm.SupposeGisweighted;thatis,supposeeach edgee ofG is assigneda nonnegativenumberw(e)calledtheweightorlengthofe.ThenG maybemaintained

inmemorybyitsweightmatrixW=[wij]definedasfollows:

w(e) ifthereisanedgeefromvi tovj

wij=

0ifthereisnoedgefromvi

tovj

The path matrixPtells uswhetherornot therearepathsbetweenthevertices.Nowwewanttofind amatrixQ

whichtellsusthelengthsoftheshortestpathsbetweentheverticesor,moreexactly,amatrixQ=[qij]where

qij =lengthoftheshortestpathfromvi tovj

NextwedescribeamodificationofWarshall’salgorithmwhichefficientlyfindsusthematrixQ.

Herewedefineasequence ofmatrices Q0,Q1,.. .,Qm (analogoustotheabovematrices P0,P1,.. .,Pm)

whereQk[i,j],theijentryofQk, isdefinedasfollows:

Qk[i,j]=thesmallerofthelengthoftheprecedingpathfromvi tovj orthesumofthelengthsofthe

precedingpathsfromvi tovk andfromvk tovj.

Moreexactly,

Qk[i,j]=MIN(Qk−1 [i,j], Qk

−1[i,k]+Qk−1

[k,j])

TheinitialmatrixQ0 isthesameastheweightmatrixWexceptthateach0inwisreplacedby∞(oravery,

verylargenumber).ThefinalmatrixQm willbethedesiredmatrixQ.

EXAMPLE 9 Figure 7showsaweightedgraphGanditsweightmatrixWwhereweassumethatv1 =R,

v2 =S,v3 =T,v4 =U.

SupposeweapplythemodifiedWarshall’salgorithmtoourweightedgraphGinFig. 7.Wewillobtain

thematricesQ0,Q1,Q3,andQ4 inFig. 8.(TotherightofeachmatrixQk inFig. 8,weshowthematrixof

Fig. 7

pathswhichcorrespondtothelengthsinthematrixQk.)TheentriesinthematrixQ0 arethesameastheweight matrixWexcepteach0inWisreplacedby∞(averylargenumber).Weindicatehowthecircledentriesare

obtained:

Q1[4,2]=MIN(Q0[4,2], Q0[4,1]+Q0[1,2])=MIN(∞,4+5)=9

Q2[1,3]=MIN(Q1[1,3], Q1[1,2]+Q1[2,3])=MIN(∞,5+∞)=∞

Q3[4,2]=MIN(Q2[4,2], Q2[4,3]+Q2[3,2])=MIN(9,3+1)=4

Q4[3,1]=MIN(Q3[3,1], Q3[3,4]+Q3[4,1])=MIN(10,5+4)=9

ThelastmatrixQ4 =Q,thedesiredshortest-pathmatrix.

Fig. 8