算法合集之《图论的基本思想及方法》.doc

图论的基本思想及方法 任恺
图论的基本思想及方法
湖南省长沙市长郡中学任恺
【摘要】
文章着眼于图论基本思想及方法的讨论，不涉及高深的图论算法。
文章主要从两方面阐述图论的基本思想：一是合理选择图论模型；二是如何深入挖掘问题本质，充分利用模型的特性。同时还归纳了一些解决问题的普适性方法。
【关键字】
基本思想、图论模型、问题本质、定义法、分析法、综合法
【正文】
一、引论
图是用点和边来描述事物和事物之间的关系，是对实际问题的一种抽象。之所以用图来解决问题，是因为图能够把纷杂的信息变得有序、直观、清晰。因而图论中最基本的思想就是搭建合适的模型，深刻挖掘问题的本质，分析和利用图论模型各种性质，从而到达解决问题的目的。下面着重从模型的选择和发掘利用图的性质来阐述图的基本思想和运用方法。
二、合理选择图论模型
在解决一道实际问题时，往往先将实际问题抽象成一个数学模型，然后在模型上寻找合适的解决方法，最后再将解决方法还原到实际问题本身。而图论模型就是一种特殊的数学模型。在搭建图论模型时，是通过图中的点和边来体现原问题的特点。搭建的模型务必要真实的、贴切的和透彻的反映出原问题的本质，同时也要做到力求简练、清晰。图论问题往往关系错综复杂，变化多端，因此搭建一个合适的模型实非易事。在选择图论模型时，应该深入分析实际问题的特点，大胆的猜想和验证。下面通过一个具体实例，来揭示选择合适图论模型的重要性和一些方法：
例一：滑雪者（PolandOlympiadofInformatics2002StageIII：Skiers）
题目大意：给出一个平面图，图中有n（2≤n≤5000）个点，m条有向边。每个点都有不同的横坐标和纵坐标，有一个最高点vh和一个最低点vl。每条有向边连接着两个不同的点，方向是从较高点连到较低点。对于图中任意一点u，都至少存在一条vh到u的路径和一条u到vl的路径。任务：图中由每个点发出的边都已经按照结束点的位置从左到右给出。要求你用若干条从vh到vl的路径覆盖图中所有的边，并且使路径数最少。所谓覆盖，就是指每条边至少在一条路径中出现。选取的路径之间可以有相同的边。（题目中和下面分析中所说的路径都是有向路径，若a到b存在一条路径，并不表示b到a一定存在一条路径。）
原题请见附录
1
2
3
4
5
9
6
8
10
13
12
11
7
14
15
图2-1
样例：图2-1中所示的平面图最少需要8条路径才能覆盖所有的边。
2.1以网络流为模型
分析一下样例，很快联想到经典的网络流模型：最高点vh是网络的源点，而最低点vl是网络的汇点。题目中的路径是网络中从源点到汇点的流。要求用路径覆盖图中所有的边，且路径数最少，就是要求网络中每条边的流量大于等于1，并且从源点流出的总流量最小。
因此解决这个问题只需要建立一个有容量下界的网络，然后求这个网络的最小可行流。大致做法：
首先求出可行流：枚举每条流量为0的边，设为(i,j)。找到一条从s到i的路径和一条从j到t的路径。对“s–i–j–t”路径上的每一条边流量加1，这样既满足了每个点的流量平衡，又满足了边(i,j)的容量下界。然后在可行流上进行修改，从汇点到源点求一个最大可行反向流，就得到了一个最小可行流。
分析算法二的复杂度：求可行流时，可以先预处理源点和汇点到每个顶点的路径，因此构造可行流的时间复杂度为O(|E|+|V|)。求最大流时，可以用朴素的增广路算法，复杂度为O(|E|C)，C是进行增广的次数。因为是平面图，根据欧拉公式有O(|E|)=O(|V|)，而反向流的流量最大为O(|E|)，所以总的复杂度为O(|V|2)=O(n2)。此算法实际效率很高，能够迅速的通过测试数据。但是，这种模型并没有很好的挖掘原题中平面图的性质，所以改进的余地应该很大。
2.2以偏序集为模型
题目中强调了每个点都有不同的横纵坐标，图是有向无环平面图。而且图中两点之间的有向边似乎反映着一种元素的比较关系。是否存在更好的模型描述此图呢？为了更好的揭示问题的本质，下面引入偏序集。
2.2.1偏序集的相关概念
偏序集是一个集合X和一个二元关系R，符合下列特性：
对于X中的所有的x，有xRx，即R是自反的。
对于X中的所有的x和y，只要有xRy且x≠y，就有，即R是反对称的。
只要有xRy和yRz，就有xRz，即R是传递的。
符合这些特性的关系叫做偏序，通常用≤标记R。a≤b也可以记作b≥a。若有a≤b，且a≠b，那么就记作a<b或者b>a。<又叫做严格偏序关系。含偏序≤的偏序集X用(X,≤)表示。
令R是集合X上的一个偏序，对于属于X的两个元素x、y，若有xRy或yRx，则x和y被称作是可比的，否则被称为不可比的。集合X上的一个偏序关系R，如果使得X中的任意一对元素都是可比的，那么该偏序R就是一个全序。例如，正