附录2《图论》课程专题论文论文题目：中国邮递员问题各种算法的对比分析班级：2008级数学与应用数学组长：马利巍2011年12月27日论文评价指标与鉴定意见---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---论文编号2008SX2011—002姓名马利巍陈世红周子婷石静余庭学号P081513092P081513090P081513091P081513095P081513120成绩分工情况构思论文框架，进行论文摘要部分、以及内容撰写，对论文内容进行审定工作构思论文框架，进行论文主体内容撰写，对论文归纳总结，并进行论文文字敲定工作构思论文框架，进行论文主体内容撰写，总结论文，并进行论文文字敲定工作构思论文框架，对论文内容审定，对论文进行归纳总结，以及论文格式排版工作构思论文框架，进行论文文字敲定，以及论文打印工作论文题目中国邮递员问题各种算法的对比分析完成人马利巍陈世红周子婷石静余庭班级2008级数学与应用数学指标论文评价（对表格中的各栏，用“√”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86—100分）B（70—85分）C（60—69分）D（0—59分）鉴定意见成绩评阅人职称专业摘要---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---本文基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,进一步讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型；并研究了随机中国邮递员问题,建立了相应的确定型等价模型。并可以利用奇度数结点的配对来进行求解。根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。提出了“虚拟权值”和“虚拟节点”的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解；然后,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。通过各种算法分析比较表明,新算法具有易于解读、编码简单等特点。关键字：中国邮递员问题整数规划最优化模型奇度数结点最小生成树DNA计算多聚酶链式反应AbstractBasedonthetraditionalChinesetofigurewithoutthepostmanproblem,Thecorrespondingdisplayintegerprogrammingmodel，furtherdiscussedbasedonadirectedgraphofthegeneralizedChinathepostmanproblem，thecorrespondingdisplayintegerprogrammingmodel；AndthetraditionalChinathepostmanproblem，establishedthecorrespondingequivalentmodelthatcanandcanuseodddegreeofnodestosolvingmatching。Accordingtothisthoughtgivesanewmethodforsolvingthinking—byremovingtheoriginalgraphofthedegreeandusethenodeaccidentallyminimumspanningtreetodeterminethedegreeofthenode′spairing。Putforwardthe“virtualweights”and“virtualnode”，givenChinaapostmanofDNAcomputingalgorithmisbasedon。FirstthenewalgorithmismoreMeiliantogethertoexcludethetechnologyofreactionsolution，andthengotthepostmanallfeasiblesolutionstoproblems；---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---Andthen，basedonthesurfacewithDNAcalculationmethodsandfluorescentmarkers，andfromallthefeasiblesolutionofeventuallygettheoptimalsolution。Throughthecomparisonofthealgorithmanalysisshowthatthenewalgorithmiseasytoread，codesimplefeatures。Keywords：ThepostmanproblemofChinaIntegerprogrammingOptimizationmodelOdddegreenodeMinimumspanningtreeDNAcalculationMoreMeiliantogetherinresponse1.问题的综述中国邮递员问题（Chinesepostmanproblem）也称中国邮路问题，是我国数学家管梅谷于1960年首次提出来的，引起了世界不少数学家的关注。例如1973年匈牙利数学家Edmonds和Johnson对中国邮路问题提供了一种有效算法。这个问题的实际模型是：一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过由他负责投递的每条街道至少一次...