图论在算法设计中的应用

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景
• 1.2 本文的主要工作
• 1.3 本文的章节安排
• 第二章 图论的基本介绍
• 2.1 图论的历史、发展和基本概念
• 2.2 图的基本概念
• 第三章 算法设计和图论
• 3.1 算法的定义与特性
• 3.2 图论的一些基本算法
• 3.2.1 最小生成树算法
• 3.2.2 最短路径算法
• 3.3 图论与算法的结合
• 3.3.1 图论模型在程序设计过程中的应用
• 3.3.2 并行图论算法
• 3.3.3 图论的图像分割算法
• 3.3.4 神经网络与图论
• 3.3.5 图论的聚类算法
• 第四章 基于图论的聚类算法设计
• 4.1 背景介绍
• 4.2 聚类的介绍
• 4.3 基于最小生成树的聚类算法
• 4.3.1 最小生成树的表示和构建
• 4.3.2 改进的最小生成树算法
• 4.3.3 确定真正的不相容边
• 4.3.4 改进的最小生成树算法的评价
• 第五章 结束语
• 致谢
• 参考文献
• 研究成果