图论在算法设计中的应用

雩风三日

图论在算法设计中的应用

0 |* `% C+ s5 h- m4 [$ r
   图论是一门古老的学科，它的诞生可追溯到1736年。在离散数学领域内，图论占有主导地位。图论具有直观、清晰、解决问题简捷等特点，更重要的是，实际中的许多实际问题可以划成等价的图论问题。正因为如此，图论具有广泛的应用价值，图论可将各种复杂的工程系统和管理问题用“图”来描述，然后用数学方法求得最优结果。图论中所研究的“图”，是由若干个点，称作顶点和若干条连接两顶点的线段称作边，组成。通常顶点可用来表示事物，边用来表示这些事物之间的关系。顶点的位置、边的长短是无关紧要的，当是可以设定不同的边的权值来表示顶点间的关系强弱。图论是解决许多工程问题中算法设计的一种有效地数学模型，便于计算分析和计算机存储。
    算法是解决问题的一系列步骤的集合。因此，算法设计与分析对于问题的解决至关重要。作为离散数学重要的组成部分，图论已成为当今算法设计中的一项重要内容。因为图论与算法问题有着密切关系，“图”为一些算法问题提供了一个直观的数学平台，图的理论也为这些算法的实现提供了理论依据。事实上，众多的算法问题都直接或间接地与图有关。例如在NP完全问题中有相当一部分是图论问题或与”图”有关。
2 W# p7 e. @3 W" H8 m    基于图论的上述优点，从而将图论的相关理论引用到算法设计中来。本文首先介绍一些图论的理论以及他们的应用。从最小生成树得到的算法出发，分析和总结最小生成树算法的优点和不足，进而提出一种基于最小生成树的改进算法应用于聚类分析算法中，之后对算法进行了分析，从中解释它在解决一些聚类问题的高效性优点。

关键词:图论；算法设计；聚类；最小生成树；改进的最小生成树算法
4 N3 p' D: v. w2 c. \