f(Program,Poet)=Programet

8.图论思想
a.图论基础
b.图的表示方法
c.经典图论算法
d.构造图论模型

a.图论基础

我认为图论问题应当是NOIP中最难的问题，因为命题者往往把图论题设计得很繁琐，提高了编写和调试的难度。当然，图论题也有简单的，而且，NOIP提高组并不是每年都会涉及到图论题。这里，我们的介绍也就不那么详尽了。

首先要弄清楚两个问题：什么是图？什么是图论？
图论中所指的图是由若干点和两点之间的线（称作“边”）构成的。图论是数学的重要分支，主要研究图的性质。
要注意的是，图论只研究两点间的关联，不关心位置、长度、距离等。也就是说，移动图上任何点的位置，或者把边画得弯弯曲曲，仍然未改变这个图。只有为两点之间增减点或边、改变边的方向或权值才使图发生改变。
这样，我们可以把图记作G=(V,E)，V是顶点集，E是边集。

一些图中，边是有方向的，这样的图叫有向图。
对于无向图和有向图，边都可以有权值，有时权值还可为负。

两点间有一条边连接，称这两点“相邻”。
任何两点间都有路径连通（即可从一点沿边到达另一点），则称这个图是连通图。
树是一种特殊的连通图。一个连通图是树的充要条件是边数=顶点数-1；一个图是
从一点出发可沿一条路径回到出发点，这条路径称为“回路”。

b.图的表示方法

图有很多中表示方法。把图上的点都标上序号，就可以用以下三种方法来表示图。
要注意正确选择表示方法，因为不同方法的时间复杂度、实现困难程度很可能有区别。

输入时常常采用邻接表。邻接表是这样的一个表：每列表示一条边；有两到三行，含义见下图。（NOIP输入时往往采用“每行表示一条边”的形式。）

1 2 2 ——有向图的边的起点，无向图的边的一点
3 3 4 ——有向图的边的终点，无向图的边的另一点
3 5 9 ——边的权值

处理数据时比较方便的方法是邻接矩阵。邻接矩阵是一个二维表：x行y列表示顶点x到y的边(x,y)的权值（无边则记为“0”或“∞”，无权值图的边记为“1”）。

- 1 2 3 4
1 - 5 0 9
2 5 - 8 3
3 0 8 - 0
4 9 3 0 - （对于无向图，(x,y)=(y,x)）

有时，表示图的最佳方式是链表。链表的每一个节点包含几个部分：所代表的顶点序号，它相邻顶点的指针、对应权值的列表。

c.经典图论算法

解决图论问题，我们需要一些基本的工具。这些就是图论的经典算法。

最小生成树问题：Prim算法。
问题描述——找出一个无向有权值连通图G=(V,E)的连通子图G’=(V,E’)，使G’是树且边的权值和最小。
算法——
1.选择一个顶点作起点，记为“已到达”，其他顶点“未到达”。先置E’为空。
2.找出所有连接一个“已到达”顶点和一个“未到达”顶点的边，从这些边中找出权值最小的边(i,j)。(i,j)加入E’。将(i,j)所连接的“未到达”顶点标记为“已到达”。
3.重复2，直到所有顶点均“已到达”。此时G’=(V,E’)为所求的连通子图。
算法实现时有很多要注意的问题，要恰当处理使时间复杂度为O(v^2)（v表示顶点数）。
如果用邻接矩阵处理，可设数组记录“未到达”顶点i与所有“已到达”顶点的边中权值最小的边(i,j)，每标记一个“已到达”顶点就调整一次该数组。这样做时间复杂度为O(v^2)。
另外，Kruskal算法也用来解决最小生成树问题，时间复杂度O(ve)（e表示边数）。其思路是——
按边的权值由小到大考虑每条边：若选取这条边后这条边不会与其他边构成回路，则选取这条边；否则抛弃这条边。最后已选取的v-1条边组成最小生成树。
具体实现请读者思考。

单源点最短路径问题：Dijkstra算法。
问题描述——找出一个有向有权值（非负）连通图G=(V,E)中某顶点a分别到其余的顶点的最短路径长度。
算法——
Dijkstra算法是一个贪心算法，时间复杂度为O(n^2)。读者可以想想为什么它是正确的。
这个算法用邻接矩阵实现，开始时，邻接矩阵中没有边的位置记为∞。
1.将a记为“已到达”，其他顶点“未到达”。开辟数组dist[]，用于储存a到其余各顶点的最短路径长度。
2.开辟数组cur[]，cur[i]表示当前“未到达”顶点i与a距离（如果i已到达，这个值是无意义的，记作∞）。
3.选取cur[]中最小的一项及其对应的顶点n。此时可得dist[n]=cur[n]。将n记为“已到达”，将cur[]中的该项记为∞。
4.对每个“未到达”顶点i，判断路径(a,n,i)的距离是否小于当前距离，即比较dist[n]+(n,i)和cur[i]，cur[i]取较小值。
5.重复3、4，直到全部顶点“已到达”。
另外，还有一种类似的问题，叫做“各顶点对最短路径问题”。我们同样可以用Dijkstra算法解决，但也可以用更为方便的Floyed算法解决。至于Floyed算法的具体步骤，请读者自行查阅。

AOV网问题：拓扑排序算法。
问题描述——AOV网（Active On Vertex network）是一种有向无权值图，它可以表示各顶点所代表的事件的承接关系。现在要给出一种可能的事件发生顺序，满足：
对于每条边，终点所代表事件的发生必须以起点所代表的事件已发生为前提；换句话说，若想到达某个顶点i，则i的所有前趋顶点必须都到达过。
算法——
1.找出所有无前趋的且未到达顶点，依次到达这些顶点并删除以它们中的某个为起点的所有边。
2.重复1，直到找不出任何符合要求的顶点。此时若所有顶点已到达，则先前到达顶点的顺序就是拓扑排序的一种结果；若还有顶点未到达，则说明存在AOV网存在回路，不能拓扑排序。
拓扑排序实际应用很广。比如在课程安排上，某些课程的学习必须建立在其他课程已学过的基础上，而某些课程之间先后顺序却可以调换。这样，通过拓扑排序，就可以得到几种合适的课程安排顺序。

AOE网问题：关键路径算法。
AOE网（Active On Edge network）是一种有向有权值图，一般情况下，它有一个源点和一个结束点。
有关AOE网的问题往往是实际生产生活中遇到的问题，其关键是求“关键路径”。这条关键路径往往是源点与结束点间权值和最大或最小的路径。由这条路径我们往往很容易推出很多结论。
关键路径的求法分两步：
1.拓扑排序。如果失败，则说明关键路径不存在；如果成功，也就为下一步划好了阶段。
2.动态规划。
具体解决办法读者可在实际问题中自己摸索。附件中给出一个求关键路径的源程序。

还有一些经典图论算法（如网络流算法）由于过于生僻或繁琐，这里不再介绍。这些在NOIP中的实际应用也极少。

d.构造图论模型

其实图论思想中价值最高的不是经典算法，而是图论建模。
下面介绍几个经典的图论模型应用。

构造回路——
篝火晚会问题（NOIP2005）：
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,… bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
输出最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。
思路：
把每个人和他最喜欢相邻的人连起来，如果能形成一个大圈（回路），这个大圈就是我们所要移动到的最终目标；如果形不成一个大圈，肯定就不能同时满足所有人的愿望，输出-1即可。
下面构造一个有向图：每个人作为一个顶点，从这个顶点仅出发一条边，指向这个人最终应该到的位置。

最终目标之一：1  2  3  4  5  6  初始：2  3  1  5  4  6  图：2→3→1  5→4  6
                                                            ┖──┘ ┖┘
注意：最终目标也可以是 2 3 4 5 1，5 4 3 2 1……

这样，图上会形成若干回路（有时有的顶点不在回路中）；一个命令对应一个回路，恰使这个回路上的所有人归位。
可是哪个最终目标需要的总代价最少？一个命令的价值对应一个回路的顶点数，命令的总价值对应所有回路顶点数之和。总代价最小，就意味着回路里的人最少，在原位不需移动的人最多！
我不想再说下去了，剩下的已经很明白了。如果你还不懂，只好——下载附件，看源代码吧！

构造路径、二部图——
狼羊菜问题：一位渔民带了狼、羊、菜，准备过河。可是小船每次只能容下渔民和一件物品。渔民不在时狼会吃羊、羊会吃菜。请设计一种最佳渡河方案。
有的人可能会笑我——三岁小孩的智力题放在这里做什么？
那你看看这一个变形：三个白人、三个黑人叫来你的小船，准备渡河。小船每次只能容下你和另两个人。要注意，你不在时某个岸边若黑人比白人多或白人比黑人多，白人和黑人就会打架。请给出所有安全的渡河方法。
这个问题就很复杂了。或许你绞尽脑汁可以得到一个解，可是怎么证明解的个数呢？
还是回到狼羊菜问题。我们考虑某一时刻的所有可能情形：（表示为河的出发岸/对岸）

狼羊菜人/─┐  /狼羊菜人
狼羊人/菜  │  菜/狼羊人
狼菜人/羊  │  羊/狼菜人
羊菜人/狼  │  狼/羊菜人
羊人/狼菜  └─狼菜/羊人

有些状态可以相互转化，我们用边连接起来（图中连了其中一条）。连完后成了一个无向图。
题目要求找出“狼羊菜人/”到“/狼羊菜人”的路径，也就变得很容易了吧？狼羊菜的变形问题当然也可以用类似的方法解决（如果我没记错，上面给出的变形问题是有四个解的）。
另外，像上面这样的图叫做“二部图”（有的地方称“二分图”）。它的特点是图顶点可以被分为两组，每组内部的顶点两两间均无边相连。
一个无向图是二部图的充要条件是图中无奇数边组成的回路。

还有一些很经典的图论建模问题，这里不再详述。你可以看看下面“未提及的经典问题”一栏。

终于完成这个系列了～如果你还向更深入地学习，请参考Programet的其他相关文章，谢谢你的支持～

习题
图论的习题 ——感谢 深蓝评测系统 提供习题

附件：关键路径算法、篝火晚会问题解法源文件
抱歉，只有对本站任何文章发表过评论才能阅读隐藏内容。
未提及的经典图论问题（点击这里查看）说谎岛问题

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

1. NOIP实用算法·教程 下载版
2. 五年NOIP提高组复赛算法及难度分析
3. NOIP实用算法·教程 下载版 2.0
4. NOIP实用算法 目录
5. NOIP实用算法 下载版 纠错通知

2009年8月28日 星期五