图论的算法与应用简述

张孟 张惠

摘 要：图论一开始由著名数学家欧拉提出，属于数学的一个分支。它是一个重要的现代数学工具，随着图论在自然科学、经济管理、工程技术以及社会问题等方面的频繁应用，对图论的学习和研究已不局限于数学界，其他科学如电子学、计算机科学等也都越来越重视对图论的研究。本文对图论的算法和应用做了简要的概述。

关键词：图论；赋权图；神经网络；复杂网络

一、引言

图论自1736年由欧拉提出以来，至今已有280年的历史。它是数学的一个分支，属于离散数学，因此具有离散数学的很多特征。图论（Graph Theory），顾名思义，是研究图形的一种理论。自然界和人类社会中的大量事物，往往存在着错综复杂的联系，这些事物和事物之间的关系往往可以用图形来表示。图形中的点代表要研究的事物，点之间的连线代表事物之间的联系。

把图记为G，图中每个点为顶点，顶点组成的集合为顶点集，记为V，点之间的连线为边，边组成的集合为图的边集，记为E。图G指的就是一个二元组（V，E），用V（G）表示G的顶点集，E（G）表示G的边集。一条边e=（u，v）的意思是说，边e和u，v两个顶点相关联，我们称u，v是e的端点，u和v是相邻的。边可分为有向边和无向边，e有方向为有向边，e没有方向则为无向边。对于有向边，有（u，v）≠（v，u），对于无向边，有（u，v）=（v，u）。有向边组成的图为有向图，无向边组成的图称为无向图。

对任意两个图，记为G，H，如果H的顶点集是G的顶点集的子集，且H的边集是G的边集的子集，那么我们称H是G的子图；如果V（H）=V（G），E（H）是E（G）的子集，则称H是G的支撑子图。

如果在图的每条边上赋以权数，就可得到赋权图，记作G=（V，E，W），W为权集。在处理实际问题中，赋权图非常有用，权数的确定依据实际情况而定，可以代表不同的含义。如比较常见的情况，权数代表两地之间的距离或行程时间，也可以表示一道程序需要的加工时间等。

二、图论的算法

在计算机科学中，图论提供了一种简单有效的建模方式，很多复杂的问题可以通过图论由基本运算及规定的运算顺序构成的完整的解题步骤得到简化和解决。一个算法有五个重要特征：有穷性、确切性、输入、输出和可行性。有穷性是指执行步骤有限，确切性是指算法的每一个步骤都有确切的含义，输入是指一个算法有0个或多个输入，输出是指一个算法有1个或多个输出，可行性是指这个算法在原则上是行得通的，可以精确地运行，并且人可以通过纸和笔来完成有限次运算。

图论中一些常用的算法有并行图论算法、阈值分割算法、最短路径算法、最小生成树算法、最小支撑树聚类算法。下面选择其中几种算法作简要介绍。

并行图论算法的研究历史比较早，上世纪八十年代中期基本成熟，其研究可以分为两大类。第一类着重研究像无向图的连通分支、有向图的可达性、强连通分支、最小生成树等一些基本图问题，相对比较简单。另一类是对比较复杂的图问题的研究，如最大基数加权匹配问题、图着色、最大流最小割等问题，这一类问题的研究相对于第一类问题的研究比较滞后。

阈值分割算法是一种图像分割技术，利用图像中要提取的目标和背景在灰度特性上的差异，把图像视为具有不同灰度等级的两类区域的组合，根据选取的合适的阈值确定图像中的像素点属于目标还是背景。使用该方法的关键点是如何确定最优阈值，这个问题同时也是使用该方法的难点所在。

最短路径法1959年被提出，该算法给出了从一个给定的点s到其他每一个点的最短路径。该算法的具体操作过程在运筹学中也有涉及，被称为Dijkstra算法。其输入和输出如下：

输入：赋权图G=（V，E，W）和s∈V，其中|V|=n，e∈E，W（e）≥0

输出：s到G中每一点的最短路径及距离。

最小生成树算法应用的一个典型问题是赋权无向图，常见的算法是避圈法，它的基本思想是在有m条边的无向连通带权图中，把这m条边按照权重的大小排序，为e1，e2，e3，…em，然后取e1在T中，依次检查e2，e3，…em，若这些被检查的边与已在T中的边不能构成回路，则把该边放在T中，否则丢弃。算法结束后，T就是G的最小生成树。

对于最小支撑树聚类算法的详细内容，这里就暂不介绍了。

三、图论的应用

图论是一门非常古老的学科，它诞生于十八世纪三四十年代，二十世纪四五十年代其真正兴起并形成了一门独立的学科。到目前为止，图论已经广泛地运用于计算机科学、数学、系统工程、控制工程、通讯网络、心理学、管理学等领域。利用图论解决问题时通常需要进行图论建模，这样可以简化问题，突出研究问题要点，方便对问题的本质进行深入研究。图论建模既可以求解最优化问题，也可以用于求解存在性问题或者构造性问题等。在求解问题时，对研究对象的全面调查是为了将原型理想化、简单化，降低问题解决的难度，但也不会过度简化。

图论的一个重要应用是在人工神经网络方面。神经网络诸多方面的研究中图论发挥了重要的工具作用，例如神经网络的结构算法、神经网络的模型设计、神经网络的稳定性理论、人工神经网络分类研究等。此外，人工神经网络也可以作为工具应用于一些比较困难的图论问题的研究当中。

另一个与图论关系密切的课题是复杂网络理论的研究。复杂网络高度概括了复杂系统的重要特征，如互联网、交通网、电力网等等。图论在复杂网络中的应用具有很强的生命力，尤其是代数图论在复杂网络中的应用。图论方法可以应用于复杂网络的同步估计，也可以用于研究复杂网络建模、复杂网络结构特征等方面的研究。

参考文献：

[1]方富贵.图论的算法和应用研究[J].计算机与数字工程，2012，02：115-117+132.

[2]段志生.图论与复杂网络[J].力学进展，2008，06：702-712.

[3]王丽丽.图论的历史发展研究[D].山东大学，2012.

[4]许进，保铮.神经网络与图论[J].中国科学E辑：技术科学，2001，06：533-555.

（作者单位：郑州工业应用技术学院基础教学部）