[PDF] Chapter 5 Connectivity A graph admits a strongly

View - Download Chapter 5 Connectivity

Previous PDF

Next PDF

Chapter5

Connectivity

5.1Introduction

The(strong)connecti vitycorresponds tothefactthata (directed)(u,v)-pathexists forany pairofv erticesuandv.Howe ver,imaginethatthegraphsmodelsanetwork,forexamplethe verticescorrespondtocomputersand edgesto linksbetweenthem. Animportantissue isthat theconnectivity remainsevenif somecomputersand linksfail.Thiswillbemeasuredbythe notionofk-connectivity. LetGbeagraph. LetWbeans etofedges (resp.ofvertices).If G\W(resp.G-W)isnot connected,thenWseparates G,andWiscalledan edge-separator(resp.vertex-separator)or simplyseparatorofG. Foranyk≥1,Gisk-connectedifithas orderatleast k+1andno setofk-1vertices isaseparator .Inparticular ,thecompletegraphK k+1 istheonly k-connectedgraphwith k+1 vertices.TheconnectivityofG,denotedby κ(G),isthe maximuminteger ksuchthatGis k-connected.Similarly, agraphisk-edgeconnectedifithas atleasttw ov erticesand noset ofk-1edgesis aseparator .Theedge-connectivityofG,denotedby κ (G),isthe maximum integerksuchthatGisk-edge-connected. Foranyverte xx,ifSisav ertex-separator ofG-xthenS?{x}isav ertex-separatorof G, hence However,theconnecivityofG-xmaynotbe upperbounded byafunction ofκ(G);seeEx er- cise5.3(ii). Regardingegde-connectivity,thingsare abiteasier.Indeed,foranyedgee?E(G),Fisan edge-separatorofG\eifandonly ifF?{e}isanedge-separator ofG.Hence (G). Bydefinition,being 1-connected,1-edge-connected orconnectedis equivalent. Forlar ger Proposition5.1.LetGbe agraph withatleast twovertices. 57

58CHAPTER5.CONNECTIVITY

Proof.Removingalledgesincidentto averte xmakes thegraphdisconnected. Hence,κ

δ(G).

Letusassume thatκ

(G)=k.LetF={x 1 y 1 ,x 2 y 2 ,...,x k y k }beanedge-separator ofG suchthatall x i 'sareinthesame connectedcomponent CofG\F.IfG-{x 1 ,x 2 ,...,x k }is 1 ,x 2 ,...,x k }.Hence,x 1 hasatmost kneighbours, namelythex i 'sforx i ?=x 1 andthey i 'ssuchthatx i =x 1 .Thenthe neighbourhoodof x 1 isa (G). Reciprocally,theedge-connectivityof agraph cannotbeboundedbyits connectivity. See

Exercise5.3.

Anaturalquestion isho wtoadd averte x(computer)toanalreadye xistingk-connected graph(network) sothatitremainsk-connected.Obviously ,sincetheconnectivityisat least theminimumde greeby Proposition5.1,oneneedstolink thenew vertex toatleast kexisting vertices.Thiseasynecessarycondition isinf actsufficient.

Lemma5.2.LetGbe ak-connected graph. IfG

isobtainedfr omGby addinganewvertex x adjacenttoat leastkvertices ofG,then G isk-connected.

Proof.LetSbeaseparator SofG

.Letus showthat |S|≥k.IfScontainsx,thenS\{x} mustbea separatorofG.SinceGisk-connectedthen|S\{x}|≥kandso|S|≥k+1.Assume nowthatx/?S.IfN(x)?Sthen|S|≥k.Else,N(x)\S?=/0andN(x)\Sbelongstoa unique connectedcomponentof G \S(theoneof x).Hence,Sisaseparator ofG.Thus|S|≥kbecause

Gisk-connected.

Similarly,addinganew vertex ofdegree ktoak-edge-connectedgraphyields ak-edge- connectedgraph.

Lemma5.3.LetGbe ak-edg e-connectedgr aph.IfG

isobtainedfr omGby addinganew vertexxadjacenttoat leastk verticesofG, thenG isk-edg e-connected.

Proof.LeftinEx ercise5.5

5.22-edge-connectedgraphs

For2-edge-connectedgraphs,thereis astruct uraltheoremsimilar toTheorem1.15 forstrongly connecteddigraphs.It canbepro vedin exactlythe samew ay. Thefollowing propositionfollowseasilyfrom thedefinitionof 2-edge-connectivity. Proposition5.4.LetDbe a2-edgeconnectedgraph.Then everyedg eisinacycle. Proof.Lete=uvbeanedge. SinceGis2-edge-connectedthen G\eisconnected.Thus there isa(v,u)-pathinG\e.Itsconcatenation with(u,v)isac yclecontaininge. Definition5.5.LetGbeagraph andHbeasubgraph ofG.AH-handleisapath orac ycle (allvertices aredistinctexceptpossibly thetwo endvertices)such thatitsendverticesarein V(H)anditsinternal vertices areinV(G)\V(H).AhandledecompositionofGisasequence (C,P 1 ,...,P k )suchthat:

5.3.2-CONNECTEDGRAPHS 59

•C=G 0 isac ycle; i isaG i-1 -handleandG i =G i-1 ?P i •G k =G. H?Pis2-edge-connectedfor anyH-handleP.(SeeEx ercise5.6.)Hence, aneasyinduction immediatelyyieldsthat every graphadmittinga handledecompositionis2-edge-connected. Conversely,every2-edge-connectedgraphadmitsa handledecompositionstartingatanycycle. Theorem5.6.LetGbe a2-edge-connected graphand Cacycle .ThenGhasa handledecom- position(C,P 1 ,...,P k 1 ,...P k Sinceev eryedgexyinE(G)\E(H)withbothendv erticesinV(H)isaH-handle,Hisanin- ducedsubgraphof G.Supposefor acontradictionthat H?=G,thenV(H)?=V(G).SinceGis

2-edgeconnected,there isanedge vwwithv?V(G)andw?V(G)\V(H).SinceGis2-edge

connected,Gcontainsa(w,H)-pathP.Then,the concatenationof (v,w)andPisaH-handlein

G,contradictingthe maximalityof H.

Corollary5.7(Robbins,1939).Agraph admitsastronglyconnectedorientation ifandonly if itis2-edgeconnected. Proof.Necessity:Ifa graphGisnotconnected, thenthe reisno directedpathbetween anytwo verticesindistinctcomponentswhate ver betheorientation. Letusassume thatGhasanedge uvsuchthatG\uvisnotconnected. LetC u andC v bethec onnectedcomponents ofuandvin G\uv.Then,if uvisorientedfrom utov,thereis nodirected (v,u)-pathusingthis orientation. Sufficientcy:Letusassume thatGis2-edgeconnected. FromTheorem 5.6,Gadmitsa handledecomposition(C,P 1 ,...,P k ).OrientingCintoadirected cycleand eachP i intoadirected path,weobt ainanorientation DofGhavingahandledecomposition.So, by

Theorem1.15,Disstronglyconnected.

5.32-connectedgraphs

For2-connectedgraphs,thereis astructural theoremsimilarto Theorems5.6and 1.15. Observethatsincea2-connected graphisalso 2-edge-connectedbyProposition 5.1,ev ery edgeofa 2-connectedgraphcontains isin acycle. Moregenerally, forany twov erticesxandy (notnecessarilyadjacent) thereis acycle containingxandy.SeeEx ercise5.7. Definition5.8.LetGbeagraph andHbeasubgraph ofG.AH-earisapath whoseendvertices areinV(H)andwhoseinternal verticesare inV(G)\V(H).AneardecompositionofGisa sequence(C,P 1 ,...,P k )suchthat: •C=G 0 isac ycle;

60CHAPTER5.CONNECTIVITY

i isaG i-1 -earandG i =G i-1 ?P i •G k =G. Itisstraightforw ardtosho wthatifHisa2-connected subgraphofa graphG,thegraph H?Pis2-connectedforanyH-earP.(SeeEx ercise5.6.)Hence,aneasyinductionimmediately yieldsthate very graphadmittinganeardecompositionis2-connected.Conv ersely,e very2- connectedgraphadmits anear decompositionstartingat anyc ycle. Theorem5.9.LetGbe a2-connectedgr aphandC acycle. ThenGhas aneardecomposition (C,P 1 ,...,P k 1 ,...P k Sinceev eryedgexyinE(G)\E(H)withbothendv erticesinV(H)isaH-ear,Hisaninduced subgraphofG.Supposefor acontradictionthat H?=G,thenV(H)?=V(G).SinceGiscon- nected,thereis anedge vwwithv?V(G)andw?V(G)\V(H).SinceGis2-connected,G-v containsa(w,H)-earP.Theconcatenation of(v,w)andPisaH-earinG,contradictingthe maximalityofH.

5.4Contractionand k-connectedgraphs

Definition5.10.Lete=xybeanedge ofagraph G=(V,E).LetG/edenotethegraph obtainedfromGbycontractingtheedgeeinane wverte xv e thatisadjacent toallneighbours ofxandy.Formally ,G/ehasverte xsetV =(V\{x,y})?{v e }andedgeset E ={vw?

E|{v,w}∩{x,y}=/0}?{v

e w|w?(N Gquotesdbs_dbs17.pdfusesText_23

[PDF] a guide to artificial intelligence with visual prolog

[PDF] a guide to artificial intelligence with visual prolog pdf

[PDF] a guide to building deep learning systems pdf

[PDF] a guide to deep learning

[PDF] a guide to deep learning in healthcare nature

[PDF] a guide to deep learning in healthcare pubmed

[PDF] a guide to sql 8th edition pdf

[PDF] a guide to sql 9e pdf

[PDF] a guide to sql 9th edition pdf

[PDF] a guide to sql 9th edition pdf download

[PDF] a guide to sql 9th edition pdf free download

[PDF] a guide to sql pratt pdf

[PDF] a guide to sql standard pdf

[PDF] a harmonic minor harmonica

[PDF] a java class can have which of the following methods