P vs.NP问题一直是理论计算机科学领域中最为复杂的一个问题,已经被列为世界七大数学难题之首。P vs.NP问题已经吸引了世界上许多学者对其研究,但遗憾的是,仍然未获得被广泛认可的结论。在P vs.NP问题的研究中,对NP完全问题的探索是一个关键突破口。它不仅为证明P和NP的关系奠定了基础,而且对许多科学和应用领域具有深远的影响。本论文的研究正是以一个NP完全问题——MSP问题为基础开展的。本文以文献[1]为基础进一步对MSP问题进行研究,主要工作包括:1.给出更加详细的证明过程。文献[1]更加关注的是证明的思想和框架,因此没有给出关于算法正确性证明的全部细节。本论文把重心放在算法正确性证明的研究上,关注证明的每一个细节,最终给出关于算法正确性证明的详细过程。2.总结和证明算法的若干性质。在对求解MSP问题算法的分析中,通过剖析算法的主要过程,进而获得并证明了算法的两条重要性质——顶点边集守恒性质和顶点边集存在性质。3.对MSP问题及其求解算法进行新的理解和解读,发现一些新的性质,从新的角度解读了算法的过程和作用。本文给出的关于求解MSP问题的算法正确性的详细证明进一步验证了算法的正确性,新性质的扩展发现以及对算法过程和作用的新视角分析也为MSP问题的研究提供重要参考,并为该问题研究的进一步改进提供重要帮助。