[PDF] GRAPH THEORY WITH APPLICATIONS

Jan 1, 2020 · Manual Laguna and Johan Marklund GRAPH THEORY AND ITS APPLICATIONS, THIRD EDITION Jonathan L Gross, Jay Yellen and Mark

[PDF] GRAPH THEORY WITH APPLICATIONS

Feb 4, 2013 · 8 Graph Theory with Applications The adjacency matrix of a graph is generally considerably smaller than its incidence matrix, and it is in thi~

[PDF] Graph Theory and Applications

The graph reduced to its connected components is acyclic (why ?) This shows up in many applications, eg in the dictionary graph The connected components

[PDF] Graph Theory with Algorithms and its Applications - X-Files

Graph Theory has become an important discipline in its own right because of its applications to Computer Science, Communication Networks, and

[PDF] Recent Advances in Graph Theory and its Applications

Feb 7, 2020 · Recent Advances in Graph Theory and its Applications Badwaik Jyoti S Department Of Mathematics, Kavikulguru Institute of Technology

[PDF] Graph Theory and Applications - WH5 (Perso) - Directory has no

The graph reduced to its connected components is acyclic (why ?) This shows up in many applications, eg in the dictionary graph The connected components

[PDF] applications of graph theory in computer science an overview

The field graph theory started its journey from the problem of Koinsberg bridge in 1735 This paper gives an overview of the applications of graph theory in

[PDF] graph theory with applications - Département dinformatique et de

'applications' that employ just the language of graphs and no theory The applications A graph is finite if both its vertex set and edge set are finite In this book

GRAPHTHEORY

WITHAPPLICATIONS

J.A.BondyandU.S.R.Murty

UniversityofWaterloo,

Ontario,Canada'

NORfH-HOLLAND

NewYork•Amsterdam•Oxford

®J.A.BondyandV.S.R.Muny1976

FirstpublishedinGreatBritain1976by

The·MacmillanPressLtd.

FirstpublishedintheU.S.A.1976by

ElseyierSciencePublishingCo.,Inc.

52VanderbiltAvenue,NewYork,N.Y10017

FifthPrinting,1982.

SoleDistributor

intheU.S.A:

ElsevierSciencePublishingCo.

.,Inc.

Library

ofCongressCataloginginPublicationData

Bondy,JohnAdrian.

Graphtheorywith,applications.

Bibliography:p.

Includes

index.

QA166.B671979511'.575-29826·

ISBN7 All formorbyanymeans,withoutpermission.

Printed

intheUnitedStatesofAmerica

·Toourparents

Preface

variety 'applications' gorithms shouldallbeattempted. arelisted. helpful appendixV. Many us

Chungphaisan

Preface

vii manuscriptandvaluablesuggestions, andtotheubiquitousG.O.M.forhis kindness andconstantencouragement. B. financialsupport.Finally,wewouldlike toexpressourappreciationtoJoan

Selwoodfor

artwork..

J.A.Bondy

U.S.R.Murty

Preface

1GRAPHSANDSUBGRAPHS

1.1GraphsandSimpleGraphs.

1.2

GraphIsomorphism

1.3

TheIncidenceandAdjacencyMatrices

1.4Subgraphs

1.5VertexDegrees_

1.6Pathsan"dConnection

1.7Cycles._

Applications

1.8The"ShortestPathProblem_

1.,9Sperner'sLemma.

2TREES

2.1Trees

2.2

CutEdgesandBonds..

2.3CutV'ertices.

2.4Cayley'sFormula.

Applications.

2.5TheCo"nnectorProblem

3CONNECTIVITY

3.1Connectivity.

3.2Block"s"_

4EULERTOURSAN-nHAMILTONCYCLES"

4.1EulerTours_

4.2HamiltonCycles.

Applications

4.3The",ChinesePostmanProblem

4.4TheTravellin,g'SalesDlanProblem

vi 1 4 7 8 10 12 14 15 21
25
27
31
32
,36" ' 42'
44.
47
51
53
62
65

5MATCHINGS

5.1Matchings

5.2

MatchingsandCoveringsinBipartiteGraphs

5.3PerfectMatchings.

Applications

5.4ThePersonnelAssignmentProblem'.

5.5

TheOptimalAssignmentProblem

. 6EDGECOLOURINGS

6.1EdgeChromaticNumber

6.2Vizing'sTheorem.

Applications

TheTimetablingProblem

7INDEPENDENTSETSANDCLIQUES

7.1IndependentSets.

7.2Ramsey's

7.3Turan'sTheorem.

Applications

7.4Schur'sTheorem.

7.5AGeometryProblem.

8VERTEXCOLOU'RINGS

8.1ChromaticNumber

8.2Brooks'Theorem.

8.3Haj6s'·.

8..4Chromatic

8.5GirthandChromaticNumber

Applications

8.6AStorageProblem

9PLANARGRAPHS

IX 70
72
76
80
86
91
93
96

·101

·103,

109

·112

·113

·117

·122

123
125
129
.131

·163

9.1 9.2 9.3 9.4 9.5' 9.6 9.7, 9.8

PlaneandPlanarGraphs.135

DualGraphs..139

Euler'sFormula.143

Bridges..145

Kuratowski's

Theorem.151

Nonhamiltonian

PlanarGraphs..160

Applications

APIa.narityAlgorithm.

10DIRECTEDGRAPHS

10.1DirectedGraphs.

10.2DirectedPaths

10.3DirectedCycles.

Applications

10.4AJobSequencingPr?blem.

10.5DesigninganEfficientC.omputerDrum

10.6MakingaRoadSystemOne-Way

10.7RankingtheParticipantsinaTournament.

11NETWORKS·

11.1Flows.

11.2 Cuts

11.3TheMax-FlowMin-CutTheorem

Applications

11.4Menger'sTheorems

11.5FeasibleFlows

12THECYCLESPACEANDBONDSPACE

12.1CirculationsandPotentialDifferences.

12.2

TheNumberofSpanningTrees.

Applications

12.3PerfectSquares.

AppendixIHintstoStarredExercises

AppendixIIISomeInterestingGra.phs.

AppendixIVUnsolvedProblems.

AppendixVSuggestionsforFurtherReading.

Glossary

ofSymbols·

IndexContents

·171

·173

·176

·179

·181

·182

·185

·191

·194

·196

·203

206

·212

218

··220

·227

·232

234

·246

·254

·257

·261

1GraphsandSubgraphs

1.1GRAPHSANDSIMPLEGRAPHS

. AgraphGisanorderedtriple(V(G),E(G),t/!G)consistingofa '/erticesIiand'v'arecalledtheendsofe.

Exarttple1

G=(\l(G),E(O),t/!G)

where

V(G)-={Vt,V2,V3,V4,vs}

E(G)={el,e2'e3,e4,es,e6,e"es}

andt/JCiisdefinedby

Example2

H=(V(H),E(H),t/!H)

where

V(H)={u,v,w,x,y}

E(H)={a,b,C,d,e,f,g,h}

andisdefinedby t/!H(a)=UV,t/!H(b)=UU,t/!H(C)=VW, t/!H(e)=vx,t/!H(f)=wx,t/!H(g)=ux, t/!H(d)=wx t/!H(h)=xy 2 G

GraphTheorywithApplications

b h w H

Figure1.1.DiagramsofgraphsGandH

isthis representingvertices lines'edges'. 8, V, V2

Figure1.2.AnotherdiagramofG

representingavertexwhichis .possible.

GraphsandSubgraphs3

immediately

1.1.2).

beprovedinchapter9.) otheredgesofGarelinks. u (0) x (b)

Figure1.3.Planarandnonplanargraphs

nontrivial. graphs. edgesingraphG.

Moreover,whenjust

write,forinstance,

4Graph.TheorywithApplications·

Exercises

isindeedplanar.

1.1.3ShowthatifGissimple,thenE

1..2.GRAPHISOMORPHISM

andH.

6(Vl)=y,6(V2)=x,O(V3)=U,O(V4)=v,8(v's)=w

and (et)=h, (es)=e, (e2)=g, (e6)=c, =b, (e7)=d, (e4)=a (es)=f atoneedgejoinsanypairofvertices.) graphonnvertices;itisdenotedbyK n•

AdrawingofK

s isshowninfigure

GraphsandSubgraphs

(0)(b) 5 (c)

Figure1.4.(a)K

5; (b)thecube;(c)K

3•3

Exercises

and2differentfromtheonegiven. 1.2.2 vertices. onlyif6(u)6(v)EE(H). 6 1.2.6

GraphTheorywithApplications

Showthatthefollowinggraphsareisomorphic:

1.2.7 1.2.8

1.2.10

1.2.11

1.2.12

Showthat

(a)e(Km,n)=mn; (b) ifGissimpleandbipartite,thenE<:v 2 /4. {n/m}verticesisdenotedbyT m•n•

Showthat

e(Tm,n),withequalityonlyifG -Tm,n. O's

3-cube.)Showthatthek-cubehas2

k vertices,k2 k-1 edgesandis bipartite. withvertexset

V,twoverticesbeingadjacentinGCifandonly

G isself-complementary,thenv=0,1(mod4). itself. servesadjacency,andthat thesetofsuchpermutationsforma

GraphsandSubgraphs7

operationofcomposition. (b)Findf(K n) andf(Km,n). theidentity. vertexset {I,2,3}suchthatf(G)=A. shown morphismgroupofsomegraph.) V

2,there.isan

1.3THEINCIDENCEANDADJACENCYMATRICES

v andtheedgesby e.,e2,· · ·,e

E•

graph,its e1 e 1 e 2 e 3 e 4e s e 6 e, VIV2V 3v. V

11100101VI0211

V21110000V22010

V 3

0011001

V31 101

V400 01120V

4 10-11

M(G)A(G)

V484V3

Figure1.5

GraphTheorywithApplications

computers.

Exercises

graphG. (a)ShowthateverycolumnsumofMis2.' (b)WhatarethecolumnsumsofA? sothattheadjacencymatrixofGhastheform whereA 21
isthetransposeof'A 12 theautomorphismgroupofGisabelian

1.4SUBGRAPHS

, AgraphHisasubgraphofG(writtenHeG)ifV(H)cV(G),E(H)c isa asubgrap-h (orsupergraph)HwithV(H)=V(G),. .underly.ingsimplegraph. xo----ow c x0 c

GraphsandSubgraphs9

u - u f yvyvyv 99
dbd xwxwx cc

GAspanningG-{u,w}

subgraphofG uuu yvyv g

G-{a,b,f}Theinduced

subgraph

G[{u,v,x}]

Theedge-induced

5ubgraph

G[{a,C,e,g}]

Figure1.7

subgraphG[V\V']isdenotedbyG -V';itisthesubgraphobtainedfromG

V'={v}wewriteG-vforG-{v}.

,E\E'iswrittensimplyasG -E';itisthesubgraphobtainedfromGby setofedgesE'·isdenotedby-G+IfE'={e}wewriteG -eandG+e insteadof0-{e}andG+{e}.

LetG1andG

2 besubgraphsofG.WesaythatG t andG 2 aredisjointif common.TheunionG t UG 2 ofG t andG 2 isthe-subgraphwithvertexset

10GraphTheorywithApplications

V(GI)UV(Gz)andedgesetE(GI)UE(G

z );ifG 1 andG z aredisjoint,we sometimesdenotetheirunionbyGt+G

2•

TheintersectionG

1 nG 2 ofG 1 andG2isdefinedsimilarly,butinthiscaseG 1 andG 2 musthaveatleastone vertexincommon.

[PDF] [PDF] GRAPH THEORY WITH APPLICATIONS

GRAPHTHEORY

WITHAPPLICATIONS

J.A.BondyandU.S.R.Murty

UniversityofWaterloo,

Ontario,Canada'

NORfH-HOLLAND

NewYork•Amsterdam•Oxford

®J.A.BondyandV.S.R.Muny1976

FirstpublishedinGreatBritain1976by

The·MacmillanPressLtd.

FirstpublishedintheU.S.A.1976by

ElseyierSciencePublishingCo.,Inc.

52VanderbiltAvenue,NewYork,N.Y10017

FifthPrinting,1982.

SoleDistributor

ElsevierSciencePublishingCo.

Library

Bondy,JohnAdrian.

Graphtheorywith,applications.

Bibliography:p.

Includes

QA166.B671979511'.575-29826·

Printed

·Toourparents

Preface

Chungphaisan

Preface

Selwoodfor

J.A.Bondy

U.S.R.Murty

Contents

Preface

1GRAPHSANDSUBGRAPHS

1.1GraphsandSimpleGraphs.

GraphIsomorphism

TheIncidenceandAdjacencyMatrices

1.4Subgraphs

1.5VertexDegrees_

1.6Pathsan"dConnection

1.7Cycles._

Applications

1.8The"ShortestPathProblem_

1.,9Sperner'sLemma.

2TREES

2.1Trees

CutEdgesandBonds..

2.3CutV'ertices.

2.4Cayley'sFormula.

Applications.

2.5TheCo"nnectorProblem

3CONNECTIVITY

3.1Connectivity.

3.2Block"s"_

4EULERTOURSAN-nHAMILTONCYCLES"

4.1EulerTours_

4.2HamiltonCycles.

Applications

4.3The",ChinesePostmanProblem

4.4TheTravellin,g'SalesDlanProblem

Contents

5MATCHINGS

5.1Matchings

MatchingsandCoveringsinBipartiteGraphs

5.3PerfectMatchings.

Applications

5.4ThePersonnelAssignmentProblem'.

TheOptimalAssignmentProblem

6.1EdgeChromaticNumber

6.2Vizing'sTheorem.

Applications

TheTimetablingProblem

7INDEPENDENTSETSANDCLIQUES

7.1IndependentSets.

7.2Ramsey's

7.3Turan'sTheorem.

Applications

7.4Schur'sTheorem.

7.5AGeometryProblem.

8VERTEXCOLOU'RINGS