资源描述：
《K边导出子图问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、上海交通大学硕士学位论文K边导出子图问题研究姓名：郑一源申请学位级别：硕士专业：计算机软件与理论指导教师：傅育熙20081201个是关于图论的。图论中的困难问题更是不胜枚举，有许多看起来简单的问题却是NP完全的。本文对图论中的K边导出子图问题进行了研究，即问一个图中是否存在一个含有K条边的导出子图。本文给出了多项式吋间规约证明了在一般图上该问题是一个困难问题，即是NP完全的。同吋本文还在各种图类上对该问题的复杂进行了研究，也得到了一些否定或正面的结论。关键词：算法，复杂性，导出子图，规约StudyofThek-EdgeInducedSubg
2、raphProblemABSTRACTSolutiontoproblems,alsoknownasalgorithm,isnotonlyatechnicaltermforcomputerscience.Ithasbeenstudiedforthousandsofyearsasabranchofmathematics.Theemergenceofthecomputermakesitpossibletousecomputersimulationandtosolvepracticalproblems,andasaresultofthelastce
3、nturycomputerCPUprocessingpowerlimitations,memory,disk,suchasalackofresourcessothatpeoplebegantofocusonthebestwaystosolvetheproblem.Thisgreatlystimulatedthedevelopmentofalgorithmsforavarietyoftypesofproblems.Atthesametime,inorderforthealgorithmtobeevaluatedgoodorbad,itdeve
4、lopedthecomplexitytheory.Itisthemainmethodtosolvetheproblemfromthestepsrequiredisthetimetorun,aswellastheuseofadditionalspacetoevaluatethequalityofthealgorithm・Ifthealgorithmisrunningonthealgorithm'sinputthelengthofthepolynomial,generallyisconsideredtobeagoodalgorithm.Itgr
5、aduallythroughthestudyfoundthatsomeoftheproblemsseemdonothaveagoodalgorithm.Evenmoresurprisingisthattheseproblemsexist,ifanyoneofthealgorithmcanbeagoodsolution,theseproblemscanfindagoodalgorithm.Therefore,thetypeofpeopleclassifiedasaclassofproblemscalledNP-complete,isgener
6、allybelievedthatwhenaproblemisNP-completetherecanbenopolynomialtimealgorithmtosolveit.Graphtheoryisoneoftheoldestbranchesofmathematics.Graphtheoryandalgorithmhaveanaturallink,suchasthesevenbridgeproblem・SeveralofKarpes21basicNP-completeproblemsbelongtographtheory.Thereexis
7、tsahugenumberofgraphproblemwhichisNP-complete?manyseemedsimplequestionisinfactNP・complete.Inthispaper,westudythek-edgeinducedsubgraphproblem,thatis,askedwhetherthereexistsaninducedsubgraphwhichcontainskedge・Inthispaper,weprovethisproblemtobeadifficultproblemthatisNPcomplet
8、ethroughapolynomialreduction.Meanwhile,thisthesisalsofocusesonavarietycategoriesofgraphs.
