graph_theory_applications

《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