Digraphs - Theory - Algorithms and Applications.pdf - matematyka - agat1

J¿rgenBang-Jensen,GregoryGutin

Digraphs

Theory,Algorithmsand

Applications

15thAugust2007

Springer-Verlag

BerlinHeidelbergNewYork

LondonParisTokyo

HongKongBarcelona

Budapest

Wededicatethisbooktoourparents,especiallytoourfathers,B¿rge

Bang-JensenandthelateMikhailGutin,who,throughtheirverybroad

knowledge,stimulatedourinterestinscienceenormously.

Preface

Graphtheoryisaverypopularareaofdiscretemathematicswithnotonly

numeroustheoreticaldevelopments,butalsocountlessapplicationstoprac-

ticalproblems.Asaresearcharea,graphtheoryisstillrelativelyyoung,but

itismaturingrapidlywithmanydeepresultshavingbeendiscoveredover

thelastcoupleofdecades.

Thetheoryofgraphscanberoughlypartitionedintotwobranches:the

areasofundirectedgraphsanddirectedgraphs(digraphs).Eventhoughboth

areashavenumerousimportantapplications,forvariousreasons,undirected

graphshavebeenstudiedmuchmoreextensivelythandirectedgraphs.One

ofthereasonsisthatundirectedgraphsforminasenseaspecialclassof

directedgraphs(symmetricdigraphs)andhenceproblemsthatcanbefor-

mulatedforbothdirectedandundirectedgraphsareofteneasierforthe

latter.Anotherreasonisthat,unlikeforthecaseofundirectedgraphs,for

whichthereareseveralimportantbookscoveringbothclassicalandrecent

results,nopreviousbookcoversmorethanasmallfractionoftheresults

obtainedondigraphswithinthelast25years.Typically,digraphsareconsid-

eredonlyinonechapterorbyafewelementaryresultsscatteredthroughout

thebook.

Despiteallthis,thetheoryofdirectedgraphshasdevelopedenormously

withinthelastthreedecades.Thereisanextensiveliteratureondigraphs

(morethan3000papers).Manyofthesepaperscontain,notonlyinteresting

theoreticalresults,butalsoimportantalgorithmsaswellasapplications.

Thisclearlyindicatesarealnecessityforabook,coveringnotonlythebasics

ondigraphs,butalsodeeper,theoreticalaswellasalgorithmic,resultsand

applications.

Thepresentbookisanattemptto¯llthishugegapintheliterature

andmaybeconsideredasahandbookonthesubject.Itstartsatalevel

thatcanbeunderstoodbyreaderswithonlyabasicknowledgeinuniversity

mathematicsandgoesallthewayuptothelatestresearchresultsinseveral

areas(includingconnectivity,orientationsofgraphs,submodular°ows,paths

andcyclesindigraphs,generalizationsoftournamentsandgeneralizations

ofdigraphs).Thebookcontainsmorethan700exercisesandanumberof

applicationsaswellassectionsonhighlyapplicablesubjects.Duetothefact

thatwewishtoaddressdi®erentgroupsofreaders(advancedundergraduate

viii Preface

andgraduatestudents,researchersindiscretemathematicsandresearchers

invariousareasincludingcomputerscience,operationsresearch,arti¯cial

intelligence,socialsciencesandengineering)notalltopicswillbeequally

interestingtoallpotentialreaders.However,westronglybelievethatall

readerswill¯ndanumberoftopicsofspecialinteresttothem.

Eventhoughthisbookshouldnotbeseenasanencyclopediaondirected

graphs,weincludedasmanyinterestingresultsaspossible.Thebookcon-

tainsaconsiderablenumberofproofs,illustratingvariousapproachesand

techniquesusedindigraphtheoryandalgorithms.

Oneofthemainfeaturesofthisbookisthestrongemphasisonalgorithms.

Thisissomethingwhichisregrettablyomittedinsomebooksongraphs.

Algorithmson(directed)graphsoftenplayanimportantroleinproblems

arisinginseveralareas,includingcomputerscienceandoperationsresearch.

Secondly,manyproblemson(directed)graphsareinherentlyalgorithmic.

Hence,wheneverpossiblewegiveconstructiveproofsoftheresultsinthe

book.>Fromtheseproofsonecanveryoftenextractane±cientalgorithm

fortheproblemstudied.Eventhoughwedescribemanyalgorithms,partly

duetospacelimitations,wedonotsupplyallthedetailsnecessaryinorder

toimplementthesealgorithms.Thelater(oftenhighlynon-trivialstep)isa

scienceinitselfandwereferthereadertobooksondatastructures.

Anotherimportantfeatureisthevastnumberofexerciseswhichnotonly

helpthereadertotrainhisorherunderstandingofthematerial,butalso

complementstheresultsintroducedinthetextbycoveringevenmoremate-

rial.Attemptingtheseexercises(mostofwhichappearinabookforthe¯rst

time)willhelpthereadertomasterthesubjectanditsmaintechniques.

Throughitsbroadcoverageandtheexercises,stretchingfromeasyto

quitedi±cult,thebookwillbeusefulforcoursesonsubjectssuchas(di)graph

theory,combinatorialoptimizationandgraphalgorithms.Furthermore,it

canbeusedformorefocusedcoursesontopicssuchas°ows,cyclesand

connectivity.Thebookcontainsalargenumberofillustrations.Thiswill

helpthereadertounderstandotherwisedi±cultconceptsandproofs.

Tofacilitatetheuseofthisbookasareferencebookandasagraduate

textbook,wehaveaddedcomprehensivesymbolandsubjectindexes.Itisour

hopethatthedetailedsubjectindexwillhelpmanyreadersto¯ndwhatthey

arelookingforwithouthavingtoreadthroughwholechapters.Inparticular,

thereareentriesforopenproblemsandconjectures.Everyclassofdigraphs

whichisstudiedinthebookhasitsownentrycontainingthemajorityofpages

onwhichthisclassistreated.Assub-entriestotheentry`prooftechniques'

wehaveindexeddi®erentprooftechniquesandsomerepresentativepages

wherethetechniqueisillustrated.

Duetoourexperience,wethinkthatthebookwillbeausefulteaching

andreferenceresourceforseveraldecadestocome.

Preface ix

Highlights

Inthisbookwecoverthemajorityoftheimportanttopicsondigraphsrang-

ingfromquiteelementarytoveryadvancedones.Belowwegiveabriefoutline

ofsomeofthemainhighlightsofthisbook.Readerswhoarelookingformore

detailedinformationareadvisedtoconsultthelistofcontentsorthesubject

indexattheendofthebook.

Chapter1containsmostoftheterminologyandnotationusedinthis

bookaswellseveralbasicresults.Thesearenotonlyusedfrequentlyinother

chapters,butalsoserveasillustrationsofdigraphconcepts.Furthermore,

severalapplicationsofdirectedgraphsarebasedontheseelementaryresults.

Onesuchapplicationisprovidedinthelastsectionofthechapter.Basic

conceptsonalgorithmsandcomplexitycanalsobefoundinthechapter.

Duetothecomprehensivesubjectandnotationindices,itisbynomeans

necessarytoreadthewholechapterbeforemovingontootherchapters.

Chapters2and3coverdistancesand°owsinnetworks.Althoughthe

basicconceptsofthesetwotopicsareelementary,boththeoreticalandal-

gorithmicaspectsofdistancesindigraphsaswellas°owsinnetworksare

ofgreatimportance,duetotheirhighapplicabilitytootherproblemsondi-

graphsandlargenumberofpracticalapplications,inparticular,asapowerful

modelingtool.

Westartwiththeshortestpathproblemandacollectionofclassicalalgo-

rithmsfordistancesinweightedandunweighteddigraphs.Themainpartof

Chapter2isdevotedtominimizationandmaximizationofdistanceparame-

tersindigraphs.Weconcludethechapterbythefollowingapplications:the

one-waystreetproblem,thegossipproblemandexponentialneighbourhood

localsearch,anewapproachto¯ndnearoptimalsolutionstocombinatorial

optimizationproblems.

InChapter3wecoverbasic,aswellassomemoreadvancedtopicson

°owsinnetworks.Theseincludeseveralalgorithmsforthemaximum°ow

problem,feasible°owsandcirculations,minimumcost°owsinnetworksand

applicationsof°ows.Wealsoillustratetheprimal-dualalgorithmapproach

forlinearprogrammingbyapplyingittothetransportationproblem.Al-

thoughthereareseveralcomprehensivebookson°ows,webelievethatour

fairlyshortandyetquitedetailedaccountofthetopicwillgivethemajor-

ityofreaderssu±cientknowledgeofthearea.Thereaderwhomastersthe

techniquesdescribedinthischapterwillbewellequippedforsolvingmany

problemsarisinginpractice.

Chapter4isdevotedtodescribingseveralimportantclassesofdirected

graphs,suchaslinedigraphs,thedeBruijnandKautzdigraphs,series-

paralleldigraphs,generalizationsoftournamentsandplanardigraphs.We

concentrateoncharacterization,recognitionanddecompositionofthese

classes.Manypropertiesoftheseclassesarestudiedinmoredetailinthe

restofthebook.

Digraphs - Theory - Algorithms and Applications.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: