加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 组合数学与图论

组合数学与图论.pdf

组合数学与图论

caoqian_seu
2010-11-30 0人阅读 举报 0 0 暂无简介

简介:本文档为《组合数学与图论pdf》,可适用于高等教育领域

UndergraduateTextsinMathematicsEditorsSAxlerKARibetForothertitlespublishedinthisseries,gotohttp:wwwspringercomseriesJohnMHarris•JeffryLHirst•MichaelJMossinghoffCombinatoricsandGraphTheorySecondEditionJohnMHarrisJeffryLHirstDepartmentofMathematicsMathematicalSciencesFurmanUniversityAppalachianStateUniversityGreenville,SCBodenheimerDrUSABoone,NCjohnharrisfurmaneduUSAjlhmathappstateeduMichaelJMossinghoffDepartmentofMathematicsDavidsonCollegeBoxDavidson,NCUSAmimossinghoffdavidsoneduEditorialBoardSAxlerKARibetMathematicsDepartmentDepartmentofMathematicsSanFranciscoStateUniversityUniversityofCaliforniaSanFrancisco,CAatBerkeleyUSABerkeley,CAaxlersfsueduUSAribetmathberkeleyeduISSN:ISBN:eISBN:DOI:LibraryofCongressControlNumber:MathematicsSubjectClassification():c©SpringerScienceBusinessMedia,LLCAllrightsreservedThisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewrittenpermissionofthepublisher(SpringerScienceBusinessMedia,LLC,SpringStreet,NewYork,NY,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysisUseinconnectionwithanyformofinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynowknownorhereafterdevelopedisforbiddenTheuseinthispublicationoftradenames,trademarks,servicemarks,andsimilarterms,eveniftheyarenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyaresubjecttoproprietaryrightsPrintedonacidfreepaperspringercomToPriscilla,Sophie,andWill,Holly,Kristine,Amanda,andAlexandraPrefacetotheSecondEditionTherearecertainrulesthatonemustabidebyinordertocreateasuccessfulsequelRandyMeeks,fromthetrailertoScreamWhilewemaynotfollowthepreciserulesthatMrMeekshadinmindforsuccessfulsequels,wehavemadeanumberofchangestothetextinthissecondeditionInthenewedition,wecontinuetointroducenewtopicswithconcreteexamples,weprovidecompleteproofsofalmosteveryresult,andwepreservethebook’sfriendlystyleandlivelypresentation,interspersingthetextwithoccasionaljokesandquotationsThefirsttwochapters,ongraphtheoryandcombinatorics,remainlargelyindependent,andmaybecoveredineitherorderChapter,oninfinitecombinatoricsandgraphs,mayalsobestudiedindependently,althoughmanyreaderswillwanttoinvestigatetrees,matchings,andRamseytheoryforfinitesetsbeforeexploringthesetopicsforinfinitesetsinthethirdchapterLikethefirstedition,thistextisaimedatupperdivisionundergraduatestudentsinmathematics,thoughotherswillfindmuchofinterestaswellItassumesonlyfamiliaritywithbasicprooftechniques,andsomeexperiencewithmatricesandinfiniteseriesThesecondeditionoffersmanyadditionaltopicsforuseintheclassroomorforindependentstudyChapterincludesanewsectioncoveringdistanceandrelatednotionsingraphs,followinganexpandedintroductorysectionThisnewsectionalsointroducestheadjacencymatrixofagraph,anddescribesitsconnectiontoimportantfeaturesofthegraphAnothernewsectionontrails,circuits,paths,andcyclestreatsseveralproblemsregardingHamiltonianandEulerianpathsinviiiPrefacetotheSecondEditiongraphs,anddescribessomeelementaryopenproblemsregardingpathsingraphs,andgraphswithforbiddensubgraphsSeveraltopicswereaddedtoChapterTheintroductorysectiononbasiccountingprincipleshasbeenexpandedEarlyinthechapter,anewsectioncoversmultinomialcoefficientsandtheirproperties,followingthedevelopmentofthebinomialcoefficientsAnothernewsectiontreatsthepigeonholeprinciple,withapplicationstosomeproblemsinnumbertheoryThematerialonPo´lya’stheoryofcountinghasnowbeenexpandedtocoverdeBruijn’smoregeneralmethodofcountingarrangementsinthepresenceofonesymmetrygroupactingontheobjects,andanotheractingonthesetofallowedcolorsAnewsectionhasalsobeenaddedonpartitions,andthetreatmentofEuleriannumbershasbeensignificantlyexpandedThetopicofstablemarriageisdevelopedfurtheraswell,withthreeinterestingvariationsonthebasicproblemnowcoveredhereFinally,theendofthechapterfeaturesanewsectiononcombinatorialgeometryTwoprincipalproblemsservetointroducethisricharea:aniceproblemofSylvester’sregardinglinesproducedbyasetofpointsintheplane,andthebeautifulgeometricapproachtoRamseytheorypioneeredbyErdo˝sandSzekeresinaproblemabouttheexistenceofconvexpolygonsamongfinitesetsofpointsintheplaneInChapter,anewsectiondevelopsthetheoryofmatchingsfurtherbyinvestigatingmarriageproblemsoninfinitesets,bothcountableanduncountableAnothernewsectiontowardtheendofthischapterdescribesacharacterizationofcertainlargeinfinitecardinalsbyusinglinearorderingsManynewexerciseshavealsobeenaddedineachchapter,andthelistofreferenceshasbeencompletelyupdatedThesecondeditiongrewoutofourexperiencesteachingcoursesingraphtheory,combinatorics,andsettheoryatAppalachianStateUniversity,DavidsonCollege,andFurmanUniversity,andwethanktheseinstitutionsfortheirsupport,andourstudentsfortheircommentsWealsothankMarkSpenceratSpringerVerlagFinally,wethankourfamiliesfortheirpatienceandconstantgoodhumorthroughoutthisprocessThefirstandthirdauthorswouldalsoliketoaddthat,sincetheoriginalpublicationofthisbook,theirfamilieshavebothgainedtheirownsecondadditions!MayJohnMHarrisJeffryLHirstMichaelJMossinghoffPrefacetotheFirstEditionThreethingsshouldbeconsidered:problems,theorems,andapplicationsGottfriedWilhelmLeibniz,DissertatiodeArteCombinatoria,ThisbookgrewoutofseveralcoursesincombinatoricsandgraphtheorygivenatAppalachianStateUniversityandUCLAinrecentyearsAonesemestercourseforjuniorsatAppalachianStateUniversityfocusingongraphtheorycoveredmostofChapterandthefirstpartofChapterAonequartercourseatUCLAoncombinatoricsforundergraduatesconcentratedonthetopicsinChapterandincludedsomepartsofChapterAnothersemestercourseatAppalachianStateforadvancedundergraduatesandbeginninggraduatestudentscoveredmostofthetopicsfromallthreechaptersThereareratherfewprerequisitesforthistextWeassumesomefamiliaritywithbasicprooftechniques,likeinductionAfewtopicsinChapterassumesomepriorexposuretoelementarylinearalgebraChapterassumessomefamiliaritywithsequencesandseries,especiallyMaclaurinseries,attheleveltypicallycoveredinafirstyearcalculuscourseThetextrequiresnopriorexperiencewithmoreadvancedsubjects,suchasgrouptheoryWhilethisbookisprimarilyintendedforupperdivisionundergraduatestudents,webelievethatotherswillfinditusefulaswellLowerdivisionundergraduateswithapenchantforproofs,andeventalentedhighschoolstudents,willbeabletofollowmuchofthematerial,andgraduatestudentslookingforanintroductiontotopicsingraphtheory,combinatorics,andsettheorymayfindseveraltopicsofinterestxPrefacetotheFirstEditionChapterfocusesonthetheoryoffinitegraphsThefirstsectionservesasanintroductiontobasicterminologyandconceptsEachofthefollowingsectionspresentsaspecificbranchofgraphtheory:trees,planarity,coloring,matchings,andRamseytheoryThesefivetopicswerechosenfortworeasonsFirst,theyrepresentabroadrangeofthesubfieldsofgraphtheory,andinturntheyprovidethereaderwithasoundintroductiontothesubjectSecond,andjustasimportant,thesetopicsrelateparticularlywelltotopicsinChaptersandChapterdevelopsthecentraltechniquesofenumerativecombinatorics:theprincipleofinclusionandexclusion,thetheoryandapplicationofgeneratingfunctions,thesolutionofrecurrencerelations,Po´lya’stheoryofcountingarrangementsinthepresenceofsymmetry,andimportantclassesofnumbers,includingtheFibonacci,Catalan,Stirling,Bell,andEuleriannumbersThefinalsectioninthechaptercontinuesthethemeofmatchingsbeguninChapterwithaconsiderationofthestablemarriageproblemandtheGale–ShapleyalgorithmforsolvingitChapterpresentsinfinitepigeonholeprinciples,Ko¨nig’sLemma,Ramsey’sTheorem,andtheirconnectionstosettheoryThesystemsofdistinctrepresentativesofChapterreappearininfiniteform,linkedtotheaxiomofchoiceCountingisrecastascardinalarithmetic,andapigeonholepropertyforcardinalsleadstodiscussionsofincompletenessandlargecardinalsThelastsectionsconnectlargecardinalstofinitecombinatoricsanddescribesupplementarymaterialoncomputabilityFollowingLeibniz’sadvice,wefocusonproblems,theorems,andapplicationsthroughoutthetextWesupplyproofsofalmosteverytheorempresentedWetrytointroduceeachtopicwithanapplicationoraconcreteinterpretation,andweoftenintroducemoreapplicationsintheexercisesattheendofeachsectionInaddition,webelievethatmathematicsisafunandlivelysubject,sowehavetriedtoenlivenourpresentationwithanoccasionaljokeor(wehope)interestingquotationWewouldliketothanktheDepartmentofMathematicalSciencesatAppalachianStateUniversityandtheDepartmentofMathematicsatUCLAWewouldespeciallyliketothankourstudents(inparticular,JaeIlShinatUCLA),whosequestionsandcommentsonpreliminaryversionsofthistexthelpedustoimproveitWewouldalsoliketothankthethreeanonymousreviewers,whosesuggestionshelpedtoshapethisbookintoitspresentformWealsothankSharonMcPeake,astudentatASU,forherrenderingoftheKo¨nigsbergbridgesInaddition,thefirstauthorwouldliketothankRonGould,hisgraduateadvisoratEmoryUniversity,forteachinghimthemethodsandthejoysofstudyinggraphs,andforcontinuingtobehisadvisorevenaftergraduationHeespeciallywantstothankhiswife,Priscilla,forbeinghisperfectmatch,andhisdaughterSophieforaddingcolorandbrightnesstoeachandeverydayTheirpatienceandsupportthroughoutthisprocesshavebeenimmeasurableThesecondauthorwouldliketothankJudithRoitman,whointroducedhimtosettheoryandRamsey’sTheoremattheUniversityofKansas,usinganearlydraftPrefacetotheFirstEditionxiofherfinetextAlso,hewouldliketothankhiswife,Holly(theotherProfessorHirst),forhavingtheinfinitetolerancethatsetsherapartfromthenormThethirdauthorwouldliketothankBobBlakley,fromwhomhefirstlearnedaboutcombinatoricsasanundergraduateatTexasAMUniversity,andDonaldKnuth,whoseclassConcreteMathematicsatStanfordUniversitytaughthimmuchmoreaboutthesubjectMostofall,hewouldliketothankhiswife,Kristine,forherconstantsupportandinfinitepatiencethroughoutthegestationofthisproject,andforbeingsomeonehecanalways,well,countonSeptemberJohnMHarrisJeffryLHirstMichaelJMossinghoffContentsPrefacetotheSecondEditionviiPrefacetotheFirstEditionixGraphTheoryIntroductoryConceptsGraphsandTheirRelativesTheBasicsSpecialTypesofGraphsDistanceinGraphsDefinitionsandaFewPropertiesGraphsandMatricesGraphModelsandDistanceTreesDefinitionsandExamplesPropertiesofTreesSpanningTreesCountingTreesTrails,Circuits,Paths,andCyclesTheBridgesofKo¨nigsbergEulerianTrailsandCircuitsHamiltonianPathsandCyclesThreeOpenProblemsPlanarityxivContentsDefinitionsandExamplesEuler’sFormulaandBeyondRegularPolyhedraKuratowski’sTheoremColoringsDefinitionsBoundsonChromaticNumberTheFourColorProblemChromaticPolynomialsMatchingsDefinitionsHall’sTheoremandSDRsTheKo¨nig–Egerva´ryTheoremPerfectMatchingsRamseyTheoryClassicalRamseyNumbersExactRamseyNumbersandBoundsGraphRamseyTheoryReferencesCombinatoricsSomeEssentialProblemsBinomialCoefficientsMultinomialCoefficientsThePigeonholePrincipleThePrincipleofInclusionandExclusionGeneratingFunctionsDoubleDecksCountingwithRepetitionChangingMoneyFibonacciNumbersRecurrenceRelationsCatalanNumbersPo´lya’sTheoryofCountingPermutationGroupsBurnside’sLemmaTheCycleIndexPo´lya’sEnumerationFormuladeBruijn’sGeneralizationMoreNumbersPartitionsStirlingCycleNumbersStirlingSetNumbersBellNumbersEulerianNumbersContentsxvStableMarriageTheGale–ShapleyAlgorithmVariationsonStableMarriageCombinatorialGeometrySylvester’sProblemConvexPolygonsReferencesInfiniteCombinatoricsandGraphsPigeonsandTreesRamseyRevisitedZFCLanguageandLogicalAxiomsProperAxiomsAxiomofChoiceTheReturnofderKo¨nigOrdinals,Cardinals,andManyPigeonsCardinalityOrdinalsandCardinalsPigeonsFinishedOffIncompletenessandCardinalsGo¨del’sTheoremsforPAandZFCInaccessibleCardinalsASmallCollageofLargeCardinalsWeaklyCompactCardinalsInfiniteMarriageProblemsHallandHallCountablyManyMenUncountablyManyMenEspousableCardinalsPerfectMatchingsFiniteCombinatoricswithInfiniteConsequenceskcriticalLinearOrderingsPointsofDepartureReferencesReferencesIndexGraphTheory“Beginatthebeginning,”theKingsaid,gravely,“andgoontillyoucometotheendthenstop”LewisCarroll,AliceinWonderlandThePregolyaRiverpassesthroughacityonceknownasKo¨nigsbergInthessevenbridgesweresituatedacrossthisriverinamannersimilartowhatyouseeinFigureThecity’sresidentsenjoyedstrollingonthesebridges,but,ashardastheytried,noresidentofthecitywaseverabletowalkaroutethatcrossedeachofthesebridgesexactlyonceTheSwissmathematicianLeonhardEulerlearnedofthisfrustratingphenomenon,andinhewroteanarticleaboutitHisworkonthe“Ko¨nigsbergBridgeProblem”isconsideredbymanytobethebeginningofthefieldofgraphtheoryFIGUREThebridgesinKo¨nigsbergJMHarrisetal,CombinatoricsandGraphTheory,DOI:,c©SpringerScienceBusinessMedia,LLCGraphTheoryAtfirst,theusefulnessofEuler’sideasandof“graphtheory”itselfwasfoundonlyin

用户评价(0)

关闭

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

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

提示

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

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

组合数学与图论

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利