图论知识.docx

1、图论知识Graph Theory图论知识译 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中的一个数字，每条边都是集合

2、E中的成员，注意并不是每个节点都有边与其他结点相连，这样没有边与其他结点相连的结点被称作孤立结点。 有时，边会与一些数值关联，类似表示边的长度或花费。我们把这些数字称作边的权，这样边有权的图被称为边权图。类似的，我们还定义了点权图，即每个结点都有一个权。 图论的几个例子奶牛的电信 (USACO 锦标赛 1996)农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,.,a(c)，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a(c)就可以互发电邮。很不幸，有时候奶牛会不小心踩到电脑上

3、，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。 图: 每个结点表示一台电脑，而边就相对应的成了连接各台电脑的缆线。 骑马修栅栏农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从

4、任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。输入数据保证至少有一个解。图: 农民John从一个栅栏交叉点开始，经过所有栅栏一次。因而，图的结点就是栅栏交叉点，

5、边就是栅栏。 骑士覆盖问题 在一个 n x n 的棋盘中摆放尽量少的骑士，使得棋盘的每一格都会被至少一个骑士攻击到。但骑士无法攻击到它自己站的位置. 图: 这里的图较为特殊，棋盘的每一格都是一个结点，如果骑士能从这一格跳到另一格，这就说在这两个格相对应的结点之间有一条边。 穿越栅栏 1999 USACO 春季公开赛农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1=W=38)及长H(1=H=100)。2*H+1行，每行

6、2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：+-+-+-+-+-+|+-+-+|+-+-+|+-+-+-+-+如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。图: 如上图，图的每一个位置都是一个结点，如果两个相邻的位置之间没有被栅栏分开，则说在这两个位置相对应的结点之间有一条边。 用语：我们再看刚才的图：

7、如果有一条边起点与终点都是同一个结点，我们就称它为环边，表示为(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为结点数），而密集图的定义相反。例如，上图就是一张稀疏图。 有

8、向图：在以上内容中我们介绍的图都为无向图，即每一条边都是“双向”的，如果存在一条边(1,3)，则我们可以从结点1到达结点3，也可以从结点3到达结点1，换句话说，如果存在边(1,3)就必定存在边(3,1)。 但有时，图也必须被定于成有向图，即每条边都有一个方向，我们只能“单向”地根据边的方向遍历图。这样的边又称为弧。弧用带箭号的直线或弧线表示。有向图结点的出度就是指从该结点“出发”的弧的个数，相反，结点的入度就是指在该结点“结束”的弧的个数。例如，上图结点6的入度为2，出度为1。 路径：如果我们说结点u到结点x有路径，就是指存在一个结点的序列 (v 0, v 1, ., v k) 且v 0 =

9、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。 在一条路径序列中，如果所经过的结点都只在序列中出现一次，我们就称它为简单路径。 环的定义是一条起始结点与中止结点为同一结点的路径，如果一个环除了起始结点（中止结点）以外的所有结点都只在环中出现一次，那么这种环被称为简单环。 以上定义同样适用于有向图。 图的表示法选择一个好的

10、方法来表示一张图是十分重要的，因为不同的图的表示方法有着不同的时间及空间需求。 通常，结点被用数字编号来表示，我们可以通过它们的编号数字来对他们进行索引。 这样，似乎所有问题都集中在如何表示边上了。 边集边集表示法似乎是最明显的表示法，他将所有边列成一张表，用结点来表示边。 该表示法容易编写，容易调试且所需空间小。但是，它需要花费相当大的代价用于确定一条边是否存在，即确定两个结点是否相连。利用边集添加新边是很快的，但删除旧边就很麻烦了，尤其是当需要删除的边在边集中的所在位置不确定时。 对于带权图，该表示法也只需要在边集中添加一个元素，用于记录边权。同样，该表示法也适用于有向图和稀疏图。 例：一

11、张无向无权图可以表示成边集如下： V1V2e143e213e325e461e536邻接矩阵 邻接矩阵式表示图的另一种方法，邻接矩阵是一个N乘以N的数组（N为结点数）。 如果边集E中存在边(i,j)，则对应数组的(i,j)元素的值为一。相反，如果数组元素的值为零，就意味着图中结点i与j之间没有边。无向图的邻接矩阵总是关于左上右下对角线对称。 该表示法容易编写。但他对空间的需求和浪费较大，尤其是对于较大的稀疏图，调试起来也比较麻烦，并且寻找与某一结点相连的结点也很慢。不过该表示法在判断两结点是否相连，以及在添加、删除结点方面速度都是极快的。 对于带权图，数组的(i,j)元素的值被表示为边(i,j)

12、的权。对于无权复杂图来说，数组的(i,j)元素的值可以用于表示结点(i,j)之间边的个数。而对于有权复杂图来说，邻接矩阵很难将其表示清楚。 例：下面是用邻接矩阵表示一幅无权图的例子： V1V2V3V4V5V6V1001001V2000010V3100101V4001000V5010000V6101000邻接表 第三种表示图的方法是用一个列表列出所有与现结点之间有边存在的结点名称。该方法可以用一个长度为N的数组来实现（N为结点个数），数组的每一个元素都是一个链表表头。数组的第i元素所连接的链表连接了所有与结点i之间有边的结点名称。 该表示方法较难编写，特别是对于复杂图，两结点之间边的个数不受限制

13、的时候，链表可能要做成环，或者要动态分配内存。邻接表的调试也同样十分麻烦，特别是使用了环形链表后。但是，这种表示法所需求的空间与边集相同，寻找某结点的相邻结点也十分容易，然而，如果需要判断两结点是否相邻，就需要遍历该结点的所有相邻结点以证明相邻性，这浪费了不少时间。添加边十分容易，但删除边就十分困难了。 将该表示法用于带权图，就需要在链表的每一节上添加一个元素用于储存该节表示的两结点之间的权。有向图与复杂图同样可以用邻接表表示。对于有向图，我们只需存储单向的相邻即可。 例：邻接表表示无向图如下： 邻接结点结点13, 62536, 4, 1435263, 1表示法的选择:对于某些图来说，我们并不

14、需要考虑所有结点之间的关系，例如上面的骑士覆盖和穿越栅栏两题，我们只需考虑与某结点相邻结点之间的关系，确定相连，我们就不用考虑存储两个不相邻结点之间的信息。当然，这些信息来自于题目本身的暗示。 如果你发现一种表示方法可以在规定空间与时间范围内实现你的算法解决问题，并且可以使你的程序变得简洁、容易调试，那它通常就是对的。记住，编写与调试的简单是最重要的，我们不需要为一些毫无意义的加快程序速度，减少使用空间来浪费编写与调试的时间。 我们还要通过题目给我们的信息，确定我们要对图进行哪些操作，权衡后来决定表示方法。下面的表示我们为您提供的选择依据（N为结点数，M为边数，d max 为图中度的最大值）：

15、 功效表边集邻接矩阵邻接表消耗空间2xMN22xM连接判断的消耗时间M1d max检查某结点所有相邻结点的消耗时间MNd max添加边的消耗时间111删除边的消耗时间M22xd max图的连通性 如果一个图的任意两个结点之间都有一条以上的路径相连，我们就称该图为连通图。例如下图就不是连通图，因为结点2到结点4之间没有路径相通。但是如果我们在该图的结点5和6之间添加一条边，该图就成为了连通图。子图： 如果G = (V, E)成立，且有集合V是V集合的子集，集合E是集合E的子集，那么我们就说 图 G = (V, E) 是图 G = (V, E) 的子图。 同时，在边集合E中出现的边必须是连接结点集

16、合V中出现的两结点的边。我们考虑下图，它是例图的一个子图，其中V= 1, 2, 3, 4,，E = (1, 3), (1, 4)。但是如果我们在边集E中添加一条边(1, 6)，E仍然是E的子集，但由于在V中没有出现结点6，边(1, 6)就不可能在子图G = (V, E)中出现。 连通子图，如同它的名称一样，是一张图的子图，且该子图就有连通性，如下图，1, 3, 4, 6，2, 5，1, 3, 4 ，1，3都是该图的连通子图（原文中在此仅标注了结点，我们尚且将边默认为所有这些结点之间的边译者）。同时，我们还定义了极大连通子图，它的定义可以理解为将连通子图扩展的尽量大，在例图中仅有两个极大连通子图

17、：1, 3, 4, 6和2, 5。非连通图的极大连通子图被称为连通分量；有向图中的连通图叫做强连通图；非强连通图中的极大连通子图被称为强连通分量。一个连通图的生成树是该图的极小连通子图，在有N个结点的情况下，生成树仅有N-1条边。 特殊的图：连通且无环的无向图被称作树。许多树都是“层次化”的。通常，树都有一个“最顶上的”结点，被称作根结点；相反，“最底下的”结点们被称作叶结点。除了根结点以外，所有结点都仅有一个父结点，即与它相连的那个上一层结点；除了叶结点以外，所有结点都至少有一个子女结点，即与它相连的所有下一层结点。同样，类推地，还有祖先结点、后代结点。经过这样的定义后，树的样式就可以构划得像一棵倒过来生长的树了（如上图）。 不连通且无环的无向图被称为森林（如下图）。他也可以理解为是有许多树构成的图。有向无环图（Directed Acyclic Graph）被称为DAG，是他的英文缩写。 一个图的任意结点与其它所有结点有边相连的图被称为完全图。如果一个图的所有结点可以被分为两个组，同组之间的任意结点都没有边相连，即所有边连接的都是不同组的两个结点，这样的图被称为二分图。