图论与特殊图概述

1、什么是图什么是图?ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):): 能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？ABDC七桥问题模拟图七桥问题模拟图欧拉指出：欧拉指出： 如果每块陆地所连接的桥都是偶数座，则如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而从任一陆地出发，必能通过每座桥恰好一次而回到出发地回到出发地. (. (著名的欧拉图问题著名的欧拉图问题) )问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):): 十二面体的十二面体的2020个顶点代表

2、世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）问题问题3(3(四色问题四色问题):): 对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了国家染不同的颜色，则只需要四种颜色就够了. .问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育一座体育中心中心, ,小至组装一台机

3、床小至组装一台机床, ,一架电视机一架电视机, , 都要包括都要包括许多工序许多工序. .这些工序相互约束这些工序相互约束, ,只有在某些工序完只有在某些工序完成之后成之后, , 一个工序才能开始一个工序才能开始. . 即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系, ,一般认为这些关系是预知的一般认为这些关系是预知的, , 而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间. . 这时工程领导人员迫切希望了解最少需要多这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目少时间才能够完成整个工程项目, , 影响工程进度影响工程进度的要害

4、工序是哪几个？的要害工序是哪几个？ 图论中的图论中的“图图”并不是通常意义下的几何图并不是通常意义下的几何图形或物体的形状图形或物体的形状图, , 而是以一种抽象的形式来表而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统达一些确定的事物之间的联系的一个数学系统. . 定义定义1 一个有序二元组一个有序二元组(V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其中其中 V称为称为G的顶点集的顶点集, V , 其元素称为其元素称为顶顶点点或或结点结点, 简称简称点点; E称为称为G的边集的边集, 其元素称为其元素称为边边, 它联结它联结V 中的两个点中的两个点

5、, 如果这两个点是无序的如果这两个点是无序的, 则称该边则称该边为为无向边无向边, 否则否则, 称为称为有向边有向边. 如果如果V = v1, v2, , vn是有限非空点是有限非空点集集, 则称则称G为为有限图有限图或或n阶图阶图. 如果如果E的每一条边都是无向边的每一条边都是无向边, 则称则称G为为无向无向图图( (如图如图1)1); 如果如果E的每一条边都是有向边的每一条边都是有向边, 则称则称G为为有向图有向图( (如图如图2)2); 否则否则, 称称G为为混合图混合图. 图图1 1图图2 2并且常记并且常记V = v1, v2, , vn, |V | = n ;E = e1, e2,

6、 , em(ek=vivj ) , |E | = m.称点称点vi , vj为边为边vivj的的端点端点. 在有向图中在有向图中, 称点称点vi , vj分别为边分别为边vivj的的始点始点和和终点终点. 对于一个图对于一个图G = (V, E ), 人们常用图形来人们常用图形来表示它表示它, 称其为称其为图解图解. 凡是有向边凡是有向边, 在图解上都在图解上都用箭头标明其方向用箭头标明其方向. 例如例如, 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则G = (V, E ) 是一个有是一个有4个

7、顶点和个顶点和6条边的图条边的图, G的图解如下图所示的图解如下图所示. 欧拉图欧拉图 欧拉回路欧拉回路 欧拉回路问题是图论中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥（如图1）。 于是产生了这样一个问题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述，就是在图2中找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯堡七桥问题”。图1图2欧拉图欧拉图 欧拉回路欧拉回路 无数热衷于此的人试图解决这个问题，但均以失败告终。问题传到了欧拉（Leon

8、hard Euler, 1707-1783）那里，立即引起了这位大数学家的重视。经过悉心研究，欧拉终于在1736年发表了论文哥尼斯堡的七座桥，不但成功地证明了“七桥问题”无解，而且找到了对于一般图是否存在这类回路的充要条件。后人为了纪念欧拉这位伟大的数学家，便将这类回路称为欧拉回路。 欧拉图欧拉图 欧拉回路欧拉回路 首先介绍相关概念和定理。设是首先介绍相关概念和定理。设是 一个图。一个图。 欧拉通路欧拉通路(回路回路)：通过图G（无向图或有向图）中所有边边一次且仅一次行遍图中所有顶点的通路(回路)称为欧拉通路(回路)。欧拉图与半欧拉图欧拉图与半欧拉图：具有欧拉回路的图称为欧拉图，具有欧拉通路而

9、无欧拉回路的图称为半欧拉图。桥桥：设无向图G=，若存在边集E的一个非空子集非空子集E1，使得p(G-E1)p(G)，而对于E1的任意真子集真子集E2，均有p(G-E2)=p(G)，则称E1是G的边割集，或简称割集；若E1是单元集，即E1=e，则称e为割边或桥桥。p(G)表示图G的连通分支数.),(EVG a) 是欧拉图；b) 不是欧拉图，但存在欧拉通路；c) 即不是欧拉图，也不存在欧拉通路。甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？ 无向图存在欧拉回路的充

10、要条件：连通且没有奇点。 无向图存在欧拉路径的充要条件：连通且奇点个数为2。(1)既无欧拉回路,也无欧拉通路.(2)中存在欧拉通路,但无欧拉回路.(3)中存在欧拉回路. 图图a)a)存在一条欧拉通路：存在一条欧拉通路：v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1； 图图(b)(b)中存在欧拉回路中存在欧拉回路v v1 1v v2 2v v3 3v v4 4v v1 1v v3 3v v1 1，因而，因而(b)(b)是欧拉是欧拉图；图； 图图(c)(c)中有欧拉回路中有欧拉回路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8

11、 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是欧拉图。是欧拉图。 有向图存在欧拉回路的充要条件：基图连通且所有顶点入度等于出度。 有向图存在欧拉路径的充要条件：基图连通且存在某顶点入度比出度大1，另一顶点出度比入度大1，其余顶点入度等于出度。欧拉回路存在性的判断欧拉回路存在性的判断 欧拉回路问题可以分为无向图中的欧拉回路和欧拉通路，有向图中的欧拉回路和欧拉通路。这几个问题大抵相像。 有向欧拉回路有： 定理：假设有像多重图定理：假设有像多重图D有性质：当忽略有向边上的方向时，得到有性质：当忽略有向边上的方向时，得到的图是连通的，那么的图是连通的，那么D有有

12、向欧拉回路当且仅当有有向欧拉回路当且仅当D的每个顶点的入的每个顶点的入度和出度相等。度和出度相等。 类似的，对有向欧拉通路有： 定理：定理：D有有向欧拉通路，当且仅当除两个不同顶点有有向欧拉通路，当且仅当除两个不同顶点B和和C之外，之外，D的其它顶点的入度和出度相等，且的其它顶点的入度和出度相等，且B的出度比入度大的出度比入度大1，C的入度的入度比出度大比出度大1。在这种情况下，有向欧拉通路自。在这种情况下，有向欧拉通路自B出发，至出发，至C终止。终止。 由上面的定理可以知道，如果要判断一个有向图的欧拉回路是否存在，需要先判断连通性，再判断出度入度。对于无向图，判断方法类似。 判断连通性可以通

13、过DFS或者并查集来实现。1.在图中任意找一个回路C；2.将图中属于C的边删除；3.在残留图的各个极大连通分量中求欧拉回路；4.将各极大连通分量中的欧拉回路合并到C上。欧拉回路的构建欧拉回路的构建在构建欧拉回路之前需要判断欧拉回路是否存在。构建欧拉回路可以使用Fleury算法（能不走桥就不走桥）：Fleury算法：算法：（1）任取v0V(G)，令P0=v0；（2）设Pi=v0e1v1e2.eivi已经行遍，按下面方法来从 E(G)-e1,e2,.,ei中选取ei+1： （a）ei+1与vi想关联； （b）除非无别的边可供行遍，否则ei+1不应该为 Gi=G-e1,e2,.,ei中的桥.（3）当

14、（2）不能再进行时，算法停止。可以证明，当算法停止时所得简单回路Pm=v0e1v1e2.emvm（vm=v0）为G中的一条欧拉回路。构建欧拉回路的Fleury算法可以实用DFS来实现。算法的图示动态过程： 欧拉算法描述欧拉算法描述 void DFS(Graph &G,SqStack &S,int x,int t) k=0;/一个标志,来标记当前访问的节点是否还有邻接边可供访问 Push(S,x); /将本次遍历边所经由的点入栈 for(i=t;i0) k=1; Gix=0; Gxi=0; /此边已访问,删除此边 DFS(G,S,i,0);/寻找下一条关联的边,本次找到的是与x关

15、联的i,在 /下一层中将寻找与i关联的边 break; /if,for欧拉算法描述欧拉算法描述 if(k=0) /如果k=0,说明与当前顶点关联的边已穷尽 Pop(S); GetTop(S,m); Gxm=1;Gmx=1;/恢复在上一层中被删除的边 a=x+1;/如果可能的话,从当前节点的下一条关联边开始搜寻 if(StackLength(S)!=e)/继续搜寻,边还没有全部遍历完 Pop(S); /还原到上一步去 DFS(G,S,m,a);/ /if else /搜寻完毕,将最后节点也入栈 Push(S,x); /if/DFS欧拉算法描述欧拉算法描述 void Euler(Graph &am

16、p;G,int x)/G是存储图的邻接矩阵,都处理成无向图形式,值为1代表有边,0代表无边,不包括自回路,x是出发点InitStack(S);/用来存放遍历边时依次走过的顶点DFS(G,S,x,0);/深度优先遍历查找,0是指查询的起点/输出 while(!StackEmpty(S) GetTop(S,m); printf(-v%d,m); Pop(S); /while/Euler 有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。 你需要给这些盘子按照合适的顺序排成一行，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。 请你编写一个程序，判断是否能达到这

17、一要求。如果能，请给出一个合适的顺序。 malformmouseacmmalformmouseacmmmmm 以26个英文字母作为顶点。 对于每一个单词，在图中从它的首字母向末字母连一条有向边。 问题转化为在图中寻找一条不重复地经过所有边的路径，即欧拉路径欧拉路径。 这个问题能够在O(|E|)时间内解决。实例：实例：PKU 2337问题描述问题描述给出一些字符串，让你首尾串起来串成一串，并且输出一个字典序最小的方案。如果不能，输出“*”。否则输出字典序最小的回路。输入输入26alohaarachniddoggopherrattiger3oakmapleelm输出输出aloha.arachnid

18、.dog.gopher.rat.tiger*实例：实例：PKU 2337在没有特殊要求的情况下，DFS遍历图的结点顺序是可以任选的。但是这里由于加上了字典序最小的要求，所以DFS遍历时需要按照以下的优先顺序：1. 如果有不是桥的边，遍历这些边中字典序最小的边。2. 否则，遍历这些这些桥中字典序最小的边。比如一个单词，abcde，那么就连接一条a到e的有向边。如此构成的图一共最多有26个节点。每条边都代表一个单词，那么就转化成了：找一条路，遍历所有的边。就是欧拉通路问题。遍历欧拉通路的方法：确定一个起点（出度-入度=1，或者等于0（如果存在欧拉回路的话）从起点开始深搜（首先要保证图中存在欧拉回路

19、或者通路）dfs(vid, eid)其中vid表示当前搜到的点。eid表示当前搜到的边（一个点可能会有很多边）对于每条边，都是等它搜索完了后，把它代表的内容（这里是单词）压入一个栈中。最后深搜结束后，依次弹栈就是答案。Door Man (South Central USA 2002 ) 大意：给定N(=20)个房间,房间之间有门相隔，门的数目不超过100道，当前人在第M个房门，当前人每经过一道门的时候就把经过的门锁上，问有没有一条路可以使得我们走到第0个房门的时候所有的门都锁上了。 思路：我们可以把门看成是两个房间之间的边，那么问题可以转化成找一条欧拉路径。 PS：判断的时候只要判断所有的边在

20、一起就行了，所有的点不一定连通，当0点和M点不连通的时候，无解。 注意这组数据。 定义定义1 设设P(u, v) 是赋权图是赋权图G = (V, E , F) 中从中从点点u到到v的路径的路径, 用用E(P) 表示路径表示路径P(u, v)中全部边的中全部边的集合集合, 记记)()()(PEeeFPF则称则称F (P)为路径为路径P(u, v) 的的权权或或长度长度( (距离距离) ). 定义定义2 若若P0 (u, v) 是是G 中连接中连接u, v的路径的路径, 且对且对任意在任意在G 中连接中连接u, v的路径的路径P (u, v)都有都有F (P0)F(P), 则称则称P0 (u, v

21、) 是是G 中连接中连接u, v的的最短路最短路. 重要性质：重要性质： 若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的的最短路最短路. 即：最短路是一条路，且最短路的任一段也即：最短路是一条路，且最短路的任一段也是最短路是最短路. 求非负赋权图求非负赋权图G中某一点到其它各点最短路，中某一点到其它各点最短路，一般用一般用Dijkstra标号算法；求非负赋权图上任标号算法；求非负赋权图上任意两点间的最短路，一般用意两点间的最短路，一般用Floyd算法算法. .这两种这两种算法均适用于有向非负赋权图算法均适

22、用于有向非负赋权图. . 这个算法能在更一般的情况下解决最短路的问题。何谓一般，一般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。适用条件: 任意边权为实数的图Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操

23、作，要是一个结点的最短路径估计值也没能更新，就可以退出了。经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很多的数。 Bellman ford 类似于Dijkstra算法，对每一个节点v，逐步减小从起点s到终点v最短路的估计量distv直到其达到真正的最短路径值mindistv。Bellman-ford算法同时返回一个布尔值，如果不存在从源结点可达的负权回路，算法返回布尔值TRUE，反之返回FALSE。1. 枚举每条边(u,v) E（G）。2. 对枚举到的边进行一次松弛松弛操作。3. 回到步骤1，此过程重复n-1次，以确定没有可以更优化的

24、情况。4. 枚举每条边（u，v）若仍然存在可以更新的边，则说明有向图中出现了负权回路，于是返回布尔值FALSE。否则返回布尔值TRUE。void Bellman_ford (void) int i, j, k; for(i=1; i=C; i+)Disti = INF ; DistS = 0 ; for(i=1; i=C-1; i+) for(j=1; j=C; j+) for(k=1; kDistj+Graphjk)Distk=Distj+Graphjk; for(j=1; j=C; j+) for(k=1; kDistj+Graphjk) printf(-1); return; retur

25、n ; .A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N-1 For (u,v)ERelax(u,v)上图数据中，总运算量高达N2而边(S, A1)虽然被调用N次。但实际有用的只有一次 农夫农夫John发现做出全威斯康辛州最甜的黄油的方法：糖发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道。把糖放在一片牧场上，他知道N（1=N=500）只）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。当然，他将付出额外的费用在奶牛上。 农夫农夫Jo

26、hn很狡猾。他知道他可以训练这些奶牛，让它们很狡猾。他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。后下午发出铃声，以至他可以在晚上挤奶。 农夫农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）在那） INPUT FORMAT 第一行: 三个数，奶牛数N，牧场数（2=P=800），牧场间道路数C(1=C=1450) 第二行到第N+1行: 1到N头奶牛所在的牧场号 第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1=D=255），当然,连接是双向的 OUTPUT FORMAT 一行 输出奶牛必须行走的最小的距离和 SAMPLE INPUT (file butter.in) 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 SAMPLE OUTPUT (file but