关闭

关闭

关闭

封号提示

内容

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

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

GTM 173-Diestel R___Graph theor…

手机1651586804
2012-07-25 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《GTM 173-Diestel R___Graph theory (3ed Springer 2005)pdf》,可适用于人文社科领域

ReinhardDiestelGraphTheoryElectronicEditionc©SpringerVerlagHeidelberg,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,inparticulartoanymonographsorsurveyarticlesonthethemeofthatchapterTheyalsooffersomehistoricalandotherremarksonthematerialpresentedinthetextEndsofproofsaremarkedbythesymbol�Wherethissymbolisfounddirectlybelowaformalassertion,itmeansthattheproofshouldbeclearafterwhathasbeensaidaclaimwaitingtobeverified!Therearealsosomedeepertheoremswhicharestated,withoutproof,asbackgroundinformation:thesecanbeidentifiedbytheabsenceofbothproofand�Almosteverybookcontainserrors,andthisonewillhardlybeanexceptionIshalltrytopostontheWebanycorrectionsthatbecomenecessaryTherelevantsitemaychangeintime,butwillalwaysbeaccessibleviathefollowingtwoaddresses:http:wwwspringernycomsupplementsdiestelhttp:wwwspringerdecataloghtmlfilesdeutschmathhtmlPleaseletmeknowaboutanyerrorsyoufindLittleinatextbookistrulyoriginal:eventhestyleofwritingandofpresentationwillinvariablybeinfluencedbyexamplesThebookthatnodoubtinfluencedmemostistheclassicGTMgraphtheorytextbyBolloba´s:itwasinthecourserecordedbythistextthatIlearntmyfirstgraphtheoryasastudentAnyonewhoknowsthisbookwellwillfeelitsinfluencehere,despitealldifferencesincontentsandpresentationIshouldliketothankallwhogavesogenerouslyoftheirtime,knowledgeandadviceinconnectionwiththisbookIhavebenefitedparticularlyfromthehelpofNAlon,GBrightwell,RGillett,RHalin,MHintz,AHuck,ILeader,T�Luczak,WMader,VRo¨dl,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’stheoremduetoBo¨hme,Go¨ringandHarant(whichhasnototherwisebeenpublished)Finally,thereisahostofsmallsimplificationsandclarificationsofargumentsthatInoticedasItaughtfromthebook,orwhichwerepointedouttomebyothersToalltheseIoffermyspecialthanksTheWebsiteforthebookhasfollowedmetohttp:wwwmathunihamburgdehomediestelbooksgraphtheoryIexpectthisaddresstobestableforsometimeOncemore,mythanksgotoallwhocontributedtothissecondeditionbycommentingonthefirstandIlookforwardtofurthercomments!DecemberRDPrefacexiAboutthethirdeditionThereisnodenyingthatthisbookhasgrownIsitstillas‘leanandconcentratingontheessential’asIsaiditshouldbewhenIwrotetheprefacetothefirstedition,nowalmosteightyearsagoIbelievethatitis,perhapsnowmorethaneverSowhytheincreaseinvolumePartoftheansweristhatIhavecontinuedtopursuetheoriginaldualaimofofferingtwodifferentthingsbetweenonepairofcovers:•areliablefirstintroductiontographtheorythatcanbeusedeitherforpersonalstudyorasacoursetext•agraduatetextthatofferssomedepthinselectedareasForeachoftheseaims,somematerialhasbeenaddedSomeofthiscoversnewtopics,whichcanbeincludedorskippedasdesiredAnexampleattheintroductorylevelisthenewsectiononpackingandcoveringwiththeErdo˝sPo´satheorem,ortheinclusionofthestablemarriagetheoreminthematchingchapterAnexampleatthegraduatelevelistheRobertsonSeymourstructuretheoremforgraphswithoutagivenminor:aresultthattakesafewlinestostate,butonewhichisincreasinglyreliedonintheliterature,sothataneasilyaccessiblereferenceseemsdesirableAnotheraddition,alsointhechapterongraphminors,isanewproofofthe‘Kuratowskitheoremforhighersurfaces’aproofwhichillustratestheinterplaybetweengraphminortheoryandsurfacetopologybetterthanwaspreviouslypossibleTheproofiscomplementedbyanappendixonsurfaces,whichsuppliestherequiredbackgroundandalsoshedssomemorelightontheproofofthegraphminortheoremChangesthataffectpreviouslyexistingmaterialarerare,exceptforcountlesslocalimprovementsintendedtoconsolidateandpolishratherthanchangeIamawarethat,asthisbookisincreasinglyadoptedasacoursetext,thereisacertaindesireforstabilityManyoftheselocalimprovementsaretheresultofgenerousfeedbackIgotfromcolleaguesusingthebookinthisway,andIamverygratefulfortheirhelpandadviceTherearealsosomelocaladditionsMostofthesedevelopedfrommyownnotes,pencilledinthemarginasIpreparedtoteachfromthebookTheytypicallycomplementanimportantbuttechnicalproof,whenIfeltthatitsessentialideasmightgetoverlookedintheformalwriteupForexample,theproofoftheErdo˝sStonetheoremnowhasaninformalpostmortemthatlooksathowexactlytheregularitylemmacomestobeappliedinitUnliketheformalproof,thediscussionstartsoutfromthemainidea,andfinallyarrivesathowtheparameterstobedeclaredatthestartoftheformalproofmustbespecifiedSimilarly,thereisnowadiscussionpointingtosomeideasintheproofoftheperfectgraphtheoremHowever,inallthesecasestheformalproofshavebeenleftessentiallyuntouchedxiiPrefaceTheonlysubstantialchangetoexistingmaterialisthattheoldTheorem(thatcrnedgesforceaTKr)seemstohavelostitsnice(andlong)proofPreviously,thisproofhadservedasawelcomeopportunitytoexplainsomemethodsinsparseextremalgraphtheoryThesemethodshavemigratedtotheconnectivitychapter,wheretheynowliveundertheroofofthenewproofbyThomasandWollanthatknedgesmakeakconnectedgraphklinkedSotheyarestillthere,leanerthaneverbefore,andjustpresentingthemselvesunderanewguiseAsaconsequenceofthischange,thetwoearlierchaptersondenseandsparseextremalgraphtheorycouldbereunited,toformanewchapterappropriatelynamedasExtremalGraphTheoryFinally,thereisanentirelynewchapter,oninfinitegraphsWhengraphtheoryfirstemergedasamathematicaldiscipline,finiteandinfinitegraphswereusuallytreatedonaparThishaschangedinrecentyears,whichIseeasaregrettableloss:infinitegraphscontinuetoprovideanaturalandfrequentlyusedbridgetootherfieldsofmathematics,andtheyholdsomespecialfascinationoftheirownOneaspectofthisisthatproofsoftenhavetobemoreconstructiveandalgorithmicinnaturethantheirfinitecounterpartsTheinfiniteversionofMenger’stheoreminSectionisatypicalexample:itoffersalgorithmicinsightsintoconnectivityproblemsinnetworksthatareinvisibletotheslickinductiveproofsofthefinitetheoremgiveninChapterOncemore,mythanksgotoallthereadersandcolleagueswhosecommentshelpedtoimprovethebookIamparticularlygratefultoImreLeaderforhisjudiciouscommentsonthewholeoftheinfinitechaptertomygraphtheoryseminar,inparticulartoLilianMatthiesenandPhilippSpru¨ssel,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)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/49

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料