graph theory with applications [bondy, murty 1976 north-holland]

《graph theory with applications [bondy, murty 1976 north-holland]》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、GRAPHTHEORYWITHAPPLICATIONSJ.A.BondyandU.S.R.MurtyDepartmentofCombinatoricsandOptimization,UniuersityofWaterloo,Ontario,CanadaNORTH-HOLLANDNewYorkAmsterdamOxford@J.A.BondyandU.S.R.Murty1976FirstpublishedinGreatBritain1976byTheMacrniilanPressLtd.Firstpubli

2、shedintheU.S.A.1976byElsevierSciencePublishingCo.,Inc.52VanderbiltAvenue,NewYork,N.Y.10017FifthPrinting.1982.SoleDistributorintheU.S.A:ElsevierSciencePublishingCo.,Inc.LibraryofCongressCataloginginPublicationDataBondy,JohnAdrian..Graphtheorywithapplicatio

3、ns.Bibliography:p.Includesindex.1.Graphtheory.I.Murty,U.S.R.,jointauthor.11.Title.QA166.B671979511l.575-29826ISBN0-444-19451-7Allrightsreserved.Nopartofthispublicationmaybereproducedortransmitted,inanyformorbyanymeans,withoutpermission.PrintedintheUnitedS

4、tatesofAmericaToourparentsPrefaceThisbookisintendedasanintroductiontographtheory.Ouraimhasbeentopresentwhatweconsidertobethebasicmaterial,togetherwithawidevarietyofapplications,bothtootherbranchesofmathematicsandtoreal-worldproblems.Includedaresimplenewpr

5、oofsoftheoremsofBrooks,Chviital,TutteandVizing.Theapplicationshavebeencarefullyselected,andaretreatedinsomedepth.Wehavechosentoomitallso-called'applications'thatemployjustthelanguageofgraphsandnotheory.Theapplicationsappearingattheendofeachchapteractually

6、makeuseoftheorydevelopedearlierinthesamechapter.Wehavealsostressedtheimportanceofefficientmethodsofsolvingproblems.Severalgoodal-gorithmsareincludedandtheirefficienciesareanalysed.Wedonot,however,gointothecomputerimplementationofthesealgorithms.Theexercis

7、esattheendofeachsectionareofvaryingdifficulty.Theharderonesarestarred(*)and,forthese,hintsareprovidedinappendixI.Insomeexercises,newdefinitionsareintroduced.Thereaderisrecom-mendedtoacquainthimselfwiththesedefinitions.Otherexercises,whosenumbersareindicat

8、edbyboldtype,areusedinsubsequentsections;theseshouldallbeattempted.AppendixI1consistsofatableinwhichbasicpropertiesoffourgraphsarelisted.Whennewdefinitionsareintroduced,thereadermayfindithelpfultocheckhisunderstandi