图论知识
译 by Lucky Crazy
何为图？
正式地说，图G是由： 所有结点的集合 V ? 所有边的集合 E
?
构成的，简写成G(V，E)。
我们可以把结点假设成一个“地点”，而结点集合就是一个所有地点的集合。同样，边可以被假设成连接两个“地点”的一条“路”；那么边的集合就可以认为是所有这样的“路”的集合。 表示方法：
图通常用如下方法表示；结点是点或者圈，而边是直线或者曲线。
在上图中，结点 V = {1, 2, 3, 4, 5, 6} ，边E = {(1, 3), (1, 6), (2, 5), (3, 4), (3, 6)}.
每一个结点都是集合V中的一个数字，每条边都是集合E中的成员，注意并不是每个节点都有边与其他结点相连，这样没有边与其他结点相连的结点被称作孤立结点。
有时，边会与一些数值关联，类似表示边的长度或花费。我们把这些数字称作边的权，这样边有权的图被称为边权图。类似的，我们还定义了点权图，即每个结点都有一个权。 图论的几个例子
奶牛的电信 (USACO 锦标赛 1996)
农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,...,a(c)，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a(c)就可以互发电邮。很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。
图: 每个结点表示一台电脑，而边就相对应的成了连接各台电脑的缆线。 骑马修栅栏
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。输入数据保证至少有一个解。
图: 农民John从一个栅栏交叉点开始，经过所有栅栏一次。因而，图的结点就是栅栏交叉点，边就是栅栏。 骑士覆盖问题
在一个 n x n 的棋盘中摆放尽量少的骑士，使得棋盘的每一格都会被至少一个骑士攻击到。但骑士无法攻击到它自己站的位置.
图: 这里的图较为特殊，棋盘的每一格都是一个结点，如果骑士能从这一格跳到另一格，这就说在这两个格相对应的结点之间有一条边。 穿越栅栏 [1999 USACO 春季公开赛]
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。 给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。
2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X
或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）
这是一个W=5,H=3的迷宫：
+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+
如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。 图: 如上图，图的每一个位置都是一个结点，如果两个相邻的位置之间没有被栅栏分开，则说在这两个位置相对应的结点之间有一条边。 用语：
我们再看刚才的图：
如果有一条边起点与终点都是同一个结点，我们就称它为环边，表示为(v, v)，上图中没有环边。
简单图是指一张没有环边且边在边集E中不重复出现的图。与简单图相对的是复杂图。在我们的讨论中不涉及复杂图，所有的图都是简单图。
边 (u,v) 连接了结点u和结点v 。例如，边 (1,3) 连接了结点1与3。结点的度是指连接该结点所有边的个数。例如，结点3的度数是3，结点4的度数是1。 通常，如果结点u和v被用一条边连接，我们就说结点u与v相连，例如，上图结点2与5相连。
稀疏图 的定义是图的边的总数小于可能边数((N x (N-1))/2)（N为结点数），而密集图的定义相反。例如，上图就是一张稀疏图。
有向图：
在以上内容中我们介绍的图都为无向图，即每一条边都是“双向”的，如果存在一条边(1,3)，则我们可以从结点1到达结点3，也可以从结点3到达结点1，换句话说，如果存在边(1,3)就必定存在边(3,1)。
但有时，图也必须被定于成有向图，即每条边都有一个方向，我们只能“单向”地根据边的方向遍历图。这样的边又称为弧。弧用带箭号的直线或弧线表示。
有向图结点的出度就是指从该结点“出发”的弧的个数，相反，结点的入度就是指在该结点“结束”的弧的个数。例如，上图结点6的入度为2，出度为1。
路径：
如果我们说结点u到结点x有路径，就是指存在一个结点的序列 (v v ..., 0, 1,
v k) 且v 0 = u 、v k = x ， 以及(v 0, v 1) 是边集中的一条边，同样，(v 1, v 2), (v 2, v 3)??也是。
例如，上面的无向图， (4, 3, 1, 6) 就是从4到6的一条路径。
这条路径包含了边(4,3)、(3,1)、(1,6)。
如果结点x到v有一条路径，则我们从结点x开始通过边必定能访问到结点v。 在一条路径序列中，如果所经过的结点都只在序列中出现一次，我们就称它为简单路径。
环的定义是一条起始结点与中止结点为同一结点的路径，如果一个环除了起始结点（中止结点）以外的所有结点都只在环中出现一次，那么这种环被称为简单环。
以上定义同样适用于有向图。 图的表示法
选择一个好的方法来表示一张图是十分重要的，因为不同的图的表示方法有着不同的时间及空间需求。
通常，结点被用数字编号来表示，我们可以通过它们的编号数字来对他们进行索引。 这样，似乎所有问题都集中在如何表示边上了。
边集
边集表示法似乎是最明显的表示法，他将所有边列成一张表，用结点来表示边。 该表示法容易编写，容易调试且所需空间小。但是，它需要花费相当大的代价用于确定一条边是否存在，即确定两个结点是否相连。利用边集添加新边是很快的，但删除旧边就很麻烦了，尤其是当需要删除的边在边集中的所在位置不确定时。 对于带权图，该表示法也只需要在边集中添加一个元素，用于记录边权。同样，该表示法也适用于有向图和稀疏图。
例：
一张无向无权图可以表示成边集如下：
V1 V2 e1 4 3 e2 1 3 e3 2 5 e4 6 1 e5 3 6 邻接矩阵
邻接矩阵式表示图的另一种方法，邻接矩阵是一个N乘以N的数组（N为结点数）。 如果边集E中存在边(i,j)，则对应数组的(i,j)元素的值为一。相反，如果数组元素的值为零，就意味着图中结点i与j之间没有边。无向图的邻接矩阵总是关于左上右下对角线对称。
该表示法容易编写。但他对空间的需求和浪费较大，尤其是对于较大的稀疏图，调试起来也比较麻烦，并且寻找与某一结点相连的结点也很慢。不过该表示法在判断两结点是否相连，以及在添加、删除结点方面速度都是极快的。
图论知识
