关闭

关闭

关闭

封号提示

内容

首页 GTM 173-Diestel R___Graph theory (3ed Springer …

GTM 173-Diestel R___Graph theory (3ed Springer 2005).pdf

GTM 173-Diestel R___Graph theor…

上传者: 手机1651586804 2012-07-25 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《GTM 173-Diestel R___Graph theory (3ed Springer 2005)pdf》,可适用于人文社科领域,主题内容包含ReinhardDiestelGraphTheoryElectronicEditioncSpringerVerlagHeidelberg,NewYo符等。

ReinhardDiestelGraphTheoryElectronicEditioncSpringerVerlagHeidelberg,NewYork,,Thisisanelectronicversionofthethird()editionoftheaboveSpringerbook,fromtheirseriesGraduateTextsinMathematics,volThecrossreferencesinthetextandinthemarginsareactivelinks:clickonthemtobetakentotheappropriatepageTheprintededitionofthisbookcanbeorderedviahttp:wwwmathunihamburgdehomediestelbooksgraphtheorywherealsoerrata,reviewsetcarepostedSubstantialdiscountsandfreecopiesforlecturersareavailableforcourseadoptionsseeherePrefaceAlmosttwodecadeshavepassedsincetheappearanceofthosegraphtheorytextsthatstillsettheagendaformostintroductorycoursestaughttodayThecanoncreatedbythosebookshashelpedtoidentifysomemainfieldsofstudyandresearch,andwilldoubtlesscontinuetoinfluencethedevelopmentofthedisciplineforsometimetocomeYetmuchhashappenedinthoseyears,ingraphtheorynolessthanelsewhere:deepnewtheoremshavebeenfound,seeminglydisparatemethodsandresultshavebecomeinterrelated,entirenewbrancheshavearisenTonamejustafewsuchdevelopments,onemaythinkofhowthenewnotionoflistcolouringhasbridgedthegulfbetweeninvariantssuchasaveragedegreeandchromaticnumber,howprobabilisticmethodsandtheregularitylemmahavepervadedextremalgraphtheoryandRamseytheory,orhowtheentirelynewfieldofgraphminorsandtreedecompositionshasbroughtstandardmethodsofsurfacetopologytobearonlongstandingalgorithmicgraphproblemsClearly,then,thetimehascomeforareappraisal:whatare,today,theessentialareas,methodsandresultsthatshouldformthecentreofanintroductorygraphtheorycourseaimingtoequipitsaudienceforthemostlikelydevelopmentsaheadIhavetriedinthisbooktooffermaterialforsuchacourseInviewoftheincreasingcomplexityandmaturityofthesubject,Ihavebrokenwiththetraditionofattemptingtocoverboththeoryandapplications:thisbookoffersanintroductiontothetheoryofgraphsaspartof(pure)mathematicsitcontainsneitherexplicitalgorithmsnor‘realworld’applicationsMyhopeisthatthepotentialfordepthgainedbythisrestrictioninscopewillservestudentsofcomputerscienceasmuchastheirpeersinmathematics:assumingthattheypreferalgorithmsbutwillbenefitfromanencounterwithpuremathematicsofsomekind,itseemsanidealopportunitytolookforthisclosetowheretheirheartlies!Intheselectionandpresentationofmaterial,IhavetriedtoaccommodatetwoconflictinggoalsOntheonehand,IbelievethatanviiiPrefaceintroductorytextshouldbeleanandconcentrateontheessential,soastoofferguidancetothosenewtothefieldAsagraduatetext,moreover,itshouldgettotheheartofthematterquickly:afterall,theideaistoconveyatleastanimpressionofthedepthandmethodsofthesubjectOntheotherhand,ithasbeenmyparticularconcerntowritewithsufficientdetailtomakethetextenjoyableandeasytoread:guidingquestionsandideaswillbediscussedexplicitly,andallproofspresentedwillberigorousandcompleteAtypicalchapter,therefore,beginswithabriefdiscussionofwhataretheguidingquestionsintheareaitcovers,continueswithasuccinctaccountofitsclassicresults(oftenwithsimplifiedproofs),andthenpresentsoneortwodeepertheoremsthatbringoutthefullflavourofthatareaTheproofsoftheselatterresultsaretypicallyprecededby(orinterspersedwith)aninformalaccountoftheirmainideas,butarethenpresentedformallyatthesamelevelofdetailastheirsimplercounterpartsIsoonnoticedthat,asaconsequence,someofthoseproofscameoutratherlongerinprintthanseemedfairtotheiroftenbeautifullysimpleconceptionIwouldhope,however,thatevenfortheprofessionalreadertherelativelydetailedaccountofthoseproofswillatleasthelptominimizereadingtimeIfdesired,thistextcanbeusedforalecturecoursewithlittleornofurtherpreparationThesimplestwaytodothiswouldbetofollowtheorderofpresentation,chapterbychapter:apartfromtwoclearlymarkedexceptions,anyresultsusedintheproofofothersprecedetheminthetextAlternatively,alecturermaywishtodividethematerialintoaneasybasiccourseforonesemester,andamorechallengingfollowupcourseforanotherTohelpwiththepreparationofcoursesdeviatingfromtheorderofpresentation,IhavelistedinthemarginnexttoeachproofthereferencenumbersofthoseresultsthatareusedinthatproofThesereferencesaregiveninroundbrackets:forexample,areference()inthemarginnexttotheproofofTheoremindicatesthatLemmawillbeusedinthisproofCorrespondingly,inthemarginnexttoLemmathereisareference(insquarebrackets)informingthereaderthatthislemmawillbeusedintheproofofTheoremNotethatthissystemappliesbetweendifferentsectionsonly(ofthesameorofdifferentchapters):thesectionsthemselvesarewrittenasunitsandbestreadintheirorderofpresentationThemathematicalprerequisitesforthisbook,asformostgraphtheorytexts,areminimal:afirstgroundinginlinearalgebraisassumedforChapterandonceinChapter,somebasictopologicalconceptsabouttheEuclideanplaneandspaceareusedinChapter,andapreviousfirstencounterwithelementaryprobabilitywillhelpwithChapter(Evenhere,allthatisassumedformallyistheknowledgeofbasicdefinitions:thefewprobabilistictoolsusedaredevelopedinthePrefaceixtext)TherearetwoareasofgraphtheorywhichIfindbothfascinatingandimportant,especiallyfromtheperspectiveofpuremathematicsadoptedhere,butwhicharenotcoveredinthisbook:thesearealgebraicgraphtheoryandinfinitegraphsAttheendofeachchapter,thereisasectionwithexercisesandanotherwithbibliographicalandhistoricalnotesManyoftheexerciseswerechosentocomplementthemainnarrativeofthetext:theyillustratenewconcepts,showhowanewinvariantrelatestoearlierones,orindicatewaysinwhicharesultstatedinthetextisbestpossibleParticularlyeasyexercisesareidentifiedbythesuperscript,themorechallengingonescarryaThenotesareintendedtoguidethereaderontofurtherreading,inparticulartoanymonographsorsurveyarticlesonthethemeofthatchapterTheyalsooffersomehistoricalandotherremarksonthematerialpresentedinthetextEndsofproofsaremarkedbythesymbolWherethissymbolisfounddirectlybelowaformalassertion,itmeansthattheproofshouldbeclearafterwhathasbeensaidaclaimwaitingtobeverified!Therearealsosomedeepertheoremswhicharestated,withoutproof,asbackgroundinformation:thesecanbeidentifiedbytheabsenceofbothproofandAlmosteverybookcontainserrors,andthisonewillhardlybeanexceptionIshalltrytopostontheWebanycorrectionsthatbecomenecessaryTherelevantsitemaychangeintime,butwillalwaysbeaccessibleviathefollowingtwoaddresses:http:wwwspringernycomsupplementsdiestelhttp:wwwspringerdecataloghtmlfilesdeutschmathhtmlPleaseletmeknowaboutanyerrorsyoufindLittleinatextbookistrulyoriginal:eventhestyleofwritingandofpresentationwillinvariablybeinfluencedbyexamplesThebookthatnodoubtinfluencedmemostistheclassicGTMgraphtheorytextbyBollobas:itwasinthecourserecordedbythistextthatIlearntmyfirstgraphtheoryasastudentAnyonewhoknowsthisbookwellwillfeelitsinfluencehere,despitealldifferencesincontentsandpresentationIshouldliketothankallwhogavesogenerouslyoftheirtime,knowledgeandadviceinconnectionwiththisbookIhavebenefitedparticularlyfromthehelpofNAlon,GBrightwell,RGillett,RHalin,MHintz,AHuck,ILeader,TLuczak,WMader,VRodl,ADScott,PDSeymour,GSimonyi,MSˇkoviera,RThomas,CThomassenandPValtrIamparticularlygratefulalsotoTommyRJensen,whotaughtmemuchaboutcolouringandallIknowaboutkflows,andwhoinvestedimmenseamountsofdiligenceandenergyinhisproofreadingofthepreliminaryGermanversionofthisbookMarchRDxPrefaceAboutthesecondeditionNaturally,IamdelightedathavingtowritethisaddendumsosoonafterthisbookcameoutinthesummerofItisparticularlygratifyingtohearthatpeoplearegraduallyadoptingitnotonlyfortheirpersonalusebutmoreandmorealsoasacoursetextthis,afterall,wasmyaimwhenIwroteit,andmyexcuseforagonizingmoreoverpresentationthanImightotherwisehavedoneTherearetwomajorchangesThelastchapterongraphminorsnowgivesacompleteproofofoneofthemajorresultsoftheRobertsonSeymourtheory,theirtheoremthatexcludingagraphasaminorboundsthetreewidthifandonlyifthatgraphisplanarThisshortproofdidnotexistwhenIwrotethefirstedition,whichiswhyIthenincludedashortproofofthenextbestthing,theanalogousresultforpathwidthThattheoremhasnowbeendroppedfromChapterAnotheradditioninthischapteristhatthetreewidthdualitytheorem,Theorem,nowcomeswitha(short)prooftooThesecondmajorchangeistheadditionofacompletesetofhintsfortheexercisesThesearelargelyTommyJensen’swork,andIamgratefulforthetimehedonatedtothisprojectTheaimofthesehintsistohelpthosewhousethebooktostudygraphtheoryontheirown,butnottospoilthefunTheexercises,includinghints,continuetobeintendedforclassroomuseApartfromthesetwochanges,thereareafewadditionsThemostnoticableofthesearetheformalintroductionofdepthfirstsearchtreesinSection(whichhasledtosomesimplificationsinlaterproofs)andaningeniousnewproofofMenger’stheoremduetoBohme,GoringandHarant(whichhasnototherwisebeenpublished)Finally,thereisahostofsmallsimplificationsandclarificationsofargumentsthatInoticedasItaughtfromthebook,orwhichwerepointedouttomebyothersToalltheseIoffermyspecialthanksTheWebsiteforthebookhasfollowedmetohttp:wwwmathunihamburgdehomediestelbooksgraphtheoryIexpectthisaddresstobestableforsometimeOncemore,mythanksgotoallwhocontributedtothissecondeditionbycommentingonthefirstandIlookforwardtofurthercomments!DecemberRDPrefacexiAboutthethirdeditionThereisnodenyingthatthisbookhasgrownIsitstillas‘leanandconcentratingontheessential’asIsaiditshouldbewhenIwrotetheprefacetothefirstedition,nowalmosteightyearsagoIbelievethatitis,perhapsnowmorethaneverSowhytheincreaseinvolumePartoftheansweristhatIhavecontinuedtopursuetheoriginaldualaimofofferingtwodifferentthingsbetweenonepairofcovers:•areliablefirstintroductiontographtheorythatcanbeusedeitherforpersonalstudyorasacoursetext•agraduatetextthatofferssomedepthinselectedareasForeachoftheseaims,somematerialhasbeenaddedSomeofthiscoversnewtopics,whichcanbeincludedorskippedasdesiredAnexampleattheintroductorylevelisthenewsectiononpackingandcoveringwiththeErdosPosatheorem,ortheinclusionofthestablemarriagetheoreminthematchingchapterAnexampleatthegraduatelevelistheRobertsonSeymourstructuretheoremforgraphswithoutagivenminor:aresultthattakesafewlinestostate,butonewhichisincreasinglyreliedonintheliterature,sothataneasilyaccessiblereferenceseemsdesirableAnotheraddition,alsointhechapterongraphminors,isanewproofofthe‘Kuratowskitheoremforhighersurfaces’aproofwhichillustratestheinterplaybetweengraphminortheoryandsurfacetopologybetterthanwaspreviouslypossibleTheproofiscomplementedbyanappendixonsurfaces,whichsuppliestherequiredbackgroundandalsoshedssomemorelightontheproofofthegraphminortheoremChangesthataffectpreviouslyexistingmaterialarerare,exceptforcountlesslocalimprovementsintendedtoconsolidateandpolishratherthanchangeIamawarethat,asthisbookisincreasinglyadoptedasacoursetext,thereisacertaindesireforstabilityManyoftheselocalimprovementsaretheresultofgenerousfeedbackIgotfromcolleaguesusingthebookinthisway,andIamverygratefulfortheirhelpandadviceTherearealsosomelocaladditionsMostofthesedevelopedfrommyownnotes,pencilledinthemarginasIpreparedtoteachfromthebookTheytypicallycomplementanimportantbuttechnicalproof,whenIfeltthatitsessentialideasmightgetoverlookedintheformalwriteupForexample,theproofoftheErdosStonetheoremnowhasaninformalpostmortemthatlooksathowexactlytheregularitylemmacomestobeappliedinitUnliketheformalproof,thediscussionstartsoutfromthemainidea,andfinallyarrivesathowtheparameterstobedeclaredatthestartoftheformalproofmustbespecifiedSimilarly,thereisnowadiscussionpointingtosomeideasintheproofoftheperfectgraphtheoremHowever,inallthesecasestheformalproofshavebeenleftessentiallyuntouchedxiiPrefaceTheonlysubstantialchangetoexistingmaterialisthattheoldTheorem(thatcrnedgesforceaTKr)seemstohavelostitsnice(andlong)proofPreviously,thisproofhadservedasawelcomeopportunitytoexplainsomemethodsinsparseextremalgraphtheoryThesemethodshavemigratedtotheconnectivitychapter,wheretheynowliveundertheroofofthenewproofbyThomasandWollanthatknedgesmakeakconnectedgraphklinkedSotheyarestillthere,leanerthaneverbefore,andjustpresentingthemselvesunderanewguiseAsaconsequenceofthischange,thetwoearlierchaptersondenseandsparseextremalgraphtheorycouldbereunited,toformanewchapterappropriatelynamedasExtremalGraphTheoryFinally,thereisanentirelynewchapter,oninfinitegraphsWhengraphtheoryfirstemergedasamathematicaldiscipline,finiteandinfinitegraphswereusuallytreatedonaparThishaschangedinrecentyears,whichIseeasaregrettableloss:infinitegraphscontinuetoprovideanaturalandfrequentlyusedbridgetootherfieldsofmathematics,andtheyholdsomespecialfascinationoftheirownOneaspectofthisisthatproofsoftenhavetobemoreconstructiveandalgorithmicinnaturethantheirfinitecounterpartsTheinfiniteversionofMenger’stheoreminSectionisatypicalexample:itoffersalgorithmicinsightsintoconnectivityproblemsinnetworksthatareinvisibletotheslickinductiveproofsofthefinitetheoremgiveninChapterOncemore,mythanksgotoallthereadersandcolleagueswhosecommentshelpedtoimprovethebookIamparticularlygratefultoImreLeaderforhisjudiciouscommentsonthewholeoftheinfinitechaptertomygraphtheoryseminar,inparticulartoLilianMatthiesenandPhilippSprussel,forgivingthechapteratestrunandsolvingallitsexercises(ofwhicheightysurvivedtheirscrutiny)toAngelosGeorgakopoulosformuchproofreadingelsewheretoMelanieWinMyintforrecompilingtheindexandextendingitsubstantiallyandtoTimStelldingerfornursingthewhaleonpageuntilitwasstrongenoughtocarryitsbabydinosaurMayRDContentsPrefaceviiTheBasicsGraphs*Thedegreeofavertex*Pathsandcycles*Connectivity*Treesandforests*Bipartitegraphs*Contractionandminors*Eulertours*SomelinearalgebraOthernotionsofgraphsExercisesNotesMatching,CoveringandPackingMatchinginbipartitegraphs*Matchingingeneralgraphs()PackingandcoveringTreepackingandarboricityPathcoversExercisesNotes*SectionsmarkedbyanasteriskarerecommendedforafirstcourseOfsectionsmarked(),thebeginningisrecommendedforafirstcoursexivContentsConnectivityConnectedgraphsandsubgraphs*Thestructureofconnectedgraphs()Menger’stheorem*Mader’stheoremLinkingpairsofvertices()ExercisesNotesPlanarGraphsTopologicalprerequisites*Planegraphs*Dra

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/49
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部