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

图论的基本思想及方法 湖南省长沙市长郡中学 任恺 【摘要】 文章着眼于图论基本思想及方法的讨论，不涉及高深的图论算法。 文章主要从两方面阐述图论的基本思想：一是合理选择图论模型；二是如何深入挖掘问题本质，充分利用模型的特性。同时还归纳了一些解决问题的普适性方法。 【关键字】 基本思想、图论模型、问题本质、定义法、分析法、综合法 【正文】 一、引论 图是用点和边来描述事物和事物之间的关系，是对实际问题的一种抽象。之所以用图来解决问题，是因为图能够把纷杂的信息变得有序、直观、清晰。因而图论中最基本的思想就是搭建合适的模型，深刻挖掘问题的本质，分析和利用图论模型各种性质，从而到达解决问题的目的。下面着重从模型的选择和发掘利用图的性质来阐述图的基本思想和运用方法。 二、例：滑雪者（Olympiad of Informatics 2002 Stage III：Skiers） 题目大意：给出一个平面图，图中有n（2 ≤ n ≤ 5000）个点，m条有向边。每个点都有不同的横坐标和纵坐标，有一个最高点vh和一个最低点vl。每条有向边连接着两个不同的点，方向是从较高点连到较低点。对于图中任意一点u，都至少存在一条vh到u的路径和一条u到vl的路径。任务：图中由每个点发出的边都已经按照结束点的位置从左到右给出。要求你用若干条从vh到vl的路径覆盖图中所有的边，并且使路径数最少。所谓覆盖，就是指每条边至少在一条路径中。选取的路径之间可以有相同的边。（题目中和下面分析中所说的路径都是有向路径，若a到b存在一条路径，并不表示b到a一定存在一条路径。）样例： 图2-1中所示的平面图最少需要8条路径才能覆盖所有的边。 2.1 以网络流为模型 分析一下样例，很快联想到经典的网络流模型：最高点vh 是网络的源点，而最低点vl 是网络的汇点。题目中的路径是网络中从源点到汇点的流要求用路径覆盖图中所有的边，且路径数最少，就是要求网络中每条边的流量大于等于1，并且从源点流出的总流量最小。 因此解决这个问题只需要建立一个有容量下界的网络，然后求这个网络的最小可行流。大致做法：首先求出可行流– 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，有x R xR是自反的。 对于X中的所有的x和y，只要有x R y且≠ y，就有R是反对称的。 只要有x R y和y R z，就有x R zR是传递的。符合这些特性的关系叫做偏序，通常用≤标记R。a ≤ b也可以记作 ≥ a。若有a ≤ b，且a ≠ b，那么就记作a b或者 a。又叫做严格偏序关系。偏序≤的集X用(X, ≤)表示。令R是集合X上的一个偏序，对于属于X的两个元素x、y，若有x R y 或y R x，则x和y被称作是可比的，否则被称为不可比的。集合X上的一个偏序关系R，如果使得X中的任意一对元素都是可比的，那么该偏序R就是一个全序。数集上的小于等于关系就是一个全序。令a和b是偏序集(X, ≤)中的两个元素。若有a b，且X中不存在另一个元素c，使得a c b，那么就称a被b覆盖（或b覆盖a），记作a c b。若X是一个有限集，由偏序集的传递性易知，任一个偏序关系都可以用多个覆盖关系表示出来，也就是说可以用覆盖关系有效的表示偏序关系。 有限偏序集(X, ≤)的图表示是用平面上的点描述的。偏序集中的元素用平面上的点来表示。若有a b，那么a在平面上的位置就应当低于b在平面上的位置若a c b，那么a和b之间连一条边。也可以用有向图来表示偏序关系，图中的每个结点对应偏序集中的每个元素。若偏序集中的两个元素有a c b，那么对应到图中的两个结点a和b，就有一条从b到a的有向边(b, a)。 链：链是E的一个子集C，在偏序关系≤下，它的每一对元素都是可比的，即C是E的一个全序子集。 反链（或称杂置）：顾名思义，它和链的定义恰恰相反。反链是E的一个子集A，在偏序关系≤下，它的每一对元素都是不可比的。链和反链的大小是指集合中元素的个数。令原图表示的偏序集为(X, ≤)，而新构造的偏序集为(E, ≤)。则集合E