資源描述：
《graph_theory_applications》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、A?PPLICATIONSOFGRAPHTHEORYShariefuddinPirzadaandAshayDharwadkerAbstractGraphtheoryisbecomingincreasinglysignificantasitisappliedtootherareasofmathematics,scienceandtechnology.Itisbeingactivelyusedinfieldsasvariedasbiochemistry(genomics),electricalengineering(communicationn
2、etworksandcodingtheory),computerscience(algorithmsandcomputation)andoperationsresearch(scheduling).Thepowerfulcombinatorialmethodsfoundingraphtheoryhavealsobeenusedtoprovefundamentalresultsinotherareasofpuremathematics.Thispaper,besidesgivingageneraloutlookofthesefacts,inc
3、ludesnewgraphtheoreticalproofsofFermat’sLittleTheoremandtheNielson-SchreierTheorem.NewapplicationstoDNAsequencing(theSNPassemblyproblem)andcomputernetworksecurity(wormpropagation)usingminimumvertexcoversingraphsarediscussed.Wealsoshowhowtoapplyedgecoloringandmatchingingrap
4、hsforscheduling(thetimetablingproblem)andvertexcoloringingraphsformapcoloringandtheassignmentoffrequenciesinGSMmobilephonenetworks.Finally,werevisittheclassicalproblemoffindingre-entrantknight’stoursonachessboardusingHamiltoniancircuitsingraphs.IntroductionGraphtheoryisrap
5、idlymovingintothemainstreamofmathematicsmainlybecauseofitsapplicationsindiversefieldswhichincludebiochemistry,electricalengineering(communicationsnetworksandcodingtheory),computerscience(algorithmsandcomputations)andoperationsresearch(scheduling).Thewidescopeoftheseandothe
6、rapplicationshasbeenwell-documentedcf.[5][19].Thepowerfulcombinatorialmethodsfoundingraphtheoryhavealsobeenusedtoprovesignificantandwell-knownresultsinavarietyofareasinmathematicsitself.Thebestknownofthesemethodsarerelatedtoapartofgraphtheorycalled?PublishedintheJournalofT
7、heKoreanSocietyforIndustrialandAppliedMathematics(KSIAM),Vol.11,No.4,pp.19-38,2007.19APPLICATIONSOFGRAPHTHEORY–PIRZADAANDDHARWADKERmatchings,andtheresultsfromthisareaareusedtoproveDilworth’schaindecompositiontheoremforfinitepartiallyorderedsets.Anapplicationofmatchingingra
8、phtheoryshowsthatthereisacommonsetofleftandrightcosetrepresentativesofasubgroupinafiniteg
