很多实际的生产问题都能被抽象成一张大的图。具体一点的例子，比如需要在若干个城市之间铺设铁路或者架设电网，那么城市就是图里面的点，铁路电网就是图里面的边。抽象一点的例子，比如完成一个项目的过程中所有可能出现的状态都可以视为一个点，而状态到状态之间的转换就是边。上一篇文章中我们说过运筹学是处理实际生产生活中遇到的问题的。一旦实际问题被抽象成了一个图的模型（注意与机器学习里面的图模型区分开来），很多图论里面的算法就可以用来解决实际问题，所以图论是运筹学当中的一个很大的分支。今天我们就介绍一下几个图论的基本算法及其在生产生活中的应用。
一最小生成树
比如现在要在若干个村子之间架设电网，保证每个城市都通上电（先不考虑电网输电能力大小）。虽然理论上讲，任何两个村子之间都可以架设电线，不过那样的话成本很到，不划算，我们需要在所有可能的连线里面找到一组总长最短的边，保证这些边把每个村子都连上了。在图论中，这是一个典型的最小生成树问题。有两种解决最小生成树的方法，第一种办法是把所有的边按照从小到大的顺序添加到图里面，如果产生回路就舍弃它，直到覆盖了所有的点。另一种方法是把图上的边按照从大到小的顺序删除，直到再删下去就一定会产生离散的点为止。
二最短路径
图论中应用最广的问题可能就是最短路径问题了。地图上很多城市之间都有道路相连，想从一个城市到另一个城市，往往有多种选择，可是走那条路距离最短呢？如果地图规模不大，我们可以一眼就看出来。可是随着地图规模变大，就很难再一眼看出来了，需要有严格的算法保证找到最短路径。目前已经有了很多种最短路径算法，他们的基本思想也不尽相同。以著名的Dijkstra算法为例，它每次会选择距离“所有已经选择过了的点”中距离最近的下一个点，一步步的迭代下去。这个流程保证了算法会按照距离出发点由近到远的顺序选择每一个点。
三最大流-最小割问题
油气输送网络又许多不同的边组成，每一条边的运输能力有限。输送油气资源的时候，为了最大化运输量，需要合理安排通过每一条边的油气流量。这就是在一个网络寻找最大流的问题（等价于寻找最小割）。解决问题的想法很简单，找到一组边，它们把整个网络分成了两部分，流的源和目的地址分属于这两个部分。我们称这样一组边为图的一个分割。由于所有的油气流都要通过分割中的边，所以最大流其实受制于分割的流通能力的。于是最大流应该等于流通能力最小的分割。剩下的问题，就是一步步调整，找到最小分割了。
网友评论