图论与特殊图概述

图论图论什么是图?ABCD哥尼斯堡七桥示意图问题1(哥尼斯堡七桥问题):

能否从任一陆地出发通过每座桥恰好一次而回到出发点？ABDC七桥问题模拟图欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.(——著名的欧拉图问题)问题2(哈密顿环球旅行问题):

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）问题3(四色问题):

对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问题):

一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.

这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？图论的基本概念

图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.

定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中

①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②

E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.

如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.

如果E的每一条边都是无向边,则称G为无向图(如图1);

如果E的每一条边都是有向边,则称G为有向图(如图2);

否则,称G为混合图.图1图2并且常记V={v1,v2,…,vn},|V|

=n;E={e1,e2,…,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个顶点和6条边的图,G的图解如下图所示.欧拉图欧拉回路欧拉回路问题是图论中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥（如图1）。于是产生了这样一个问题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述，就是在图2中找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯堡七桥问题”。图1图2欧拉图欧拉回路无数热衷于此的人试图解决这个问题，但均以失败告终。问题传到了欧拉（LeonhardEuler,1707-1783）那里，立即引起了这位大数学家的重视。经过悉心研究，欧拉终于在1736年发表了论文《哥尼斯堡的七座桥》，不但成功地证明了“七桥问题”无解，而且找到了对于一般图是否存在这类回路的充要条件。后人为了纪念欧拉这位伟大的数学家，便将这类回路称为欧拉回路。欧拉图欧拉回路首先介绍相关概念和定理。设是一个图。

欧拉通路(回路)：通过图G（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路(回路)称为欧拉通路(回路)。欧拉图与半欧拉图：具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。桥：设无向图G=<V,E>，若存在边集E的一个非空子集E1，使得p(G-E1)>p(G)，而对于E1的任意真子集E2，均有p(G-E2)=p(G)，则称E1是G的边割集，或简称割集；若E1是单元集，即E1={e}，则称e为割边或桥。[p(G)表示图G的连通分支数.]

图中,(3)不是欧拉图,(4)是欧拉图.例是欧拉图；不是欧拉图，但存在欧拉通路；即不是欧拉图，也不存在欧拉通路。例1、(蚂蚁比赛问题)甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？例2、一笔画问题无向欧拉图的判定无向图存在欧拉回路的充要条件：

连通且没有奇点。无向图存在欧拉路径的充要条件：

连通且奇点个数为2。(1)既无欧拉回路,也无欧拉通路.(2)中存在欧拉通路,但无欧拉回路.(3)中存在欧拉回路.图a)存在一条欧拉通路：v3v1v2v3v4v1；图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图；图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。有向欧拉图的判定有向图存在欧拉回路的充要条件：

基图连通且所有顶点入度等于出度。有向图存在欧拉路径的充要条件：

基图连通且存在某顶点入度比出度大1，另一顶点出度比入度大1，其余顶点入度等于出度。欧拉回路存在性的判断欧拉回路问题可以分为无向图中的欧拉回路和欧拉通路，有向图中的欧拉回路和欧拉通路。这几个问题大抵相像。有向欧拉回路有：定理：假设有像多重图D有性质：当忽略有向边上的方向时，得到的图是连通的，那么D有有向欧拉回路当且仅当D的每个顶点的入度和出度相等。类似的，对有向欧拉通路有：定理：D有有向欧拉通路，当且仅当除两个不同顶点B和C之外，D的其它顶点的入度和出度相等，且B的出度比入度大1，C的入度比出度大1。在这种情况下，有向欧拉通路自B出发，至C终止。由上面的定理可以知道，如果要判断一个有向图的欧拉回路是否存在，需要先判断连通性，再判断出度入度。对于无向图，判断方法类似。判断连通性可以通过DFS或者并查集来实现。求无向图欧拉回路的算法在图中任意找一个回路C；将图中属于C的边删除；在残留图的各个极大连通分量中求欧拉回路；将各极大连通分量中的欧拉回路合并到C上。欧拉回路的构建在构建欧拉回路之前需要判断欧拉回路是否存在。构建欧拉回路可以使用Fleury算法（能不走桥就不走桥）：Fleury算法：（1）任取v0∈V(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）当（2）不能再进行时，算法停止。可以证明，当算法停止时所得简单回路Pm=v0e1v1e2...emvm（vm=v0）为G中的一条欧拉回路。构建欧拉回路的Fleury算法可以实用DFS来实现。算法的图示动态过程：欧拉算法描述

voidDFS(Graph&G,SqStack&S,intx,intt){

k=0;//一个标志,来标记当前访问的节点是否还有邻接边可供访问

Push(S,x);//将本次遍历边所经由的点入栈

for(i=t;i<v;i++)//v是顶点数,e是边数

if(G[i][x]>0)

{

k=1;

G[i][x]=0;G[x][i]=0;//此边已访问,删除此边

DFS(G,S,i,0);//寻找下一条关联的边,本次找到的是与x关联的i,在

//下一层中将寻找与i关联的边

break;

}//if,for欧拉算法描述

if(k==0)

//如果k=0,说明与当前顶点关联的边已穷尽

{

Pop(S);

GetTop(S,m);

G[x][m]=1;G[m][x]=1;//恢复在上一层中被删除的边

a=x+1;//如果可能的话,从当前节点的下一条关联边开始搜寻

if(StackLength(S)!=e)//继续搜寻,边还没有全部遍历完

{

Pop(S);//还原到上一步去

DFS(G,S,m,a);//

}//if

else

//搜寻完毕,将最后节点也入栈

Push(S,x);

}//if}//DFS欧拉算法描述

voidEuler(Graph&G,intx){//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个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子按照合适的顺序排成一行，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。样例malformmouseacm样例malformmouseacmmmmm模型以26个英文字母作为顶点。对于每一个单词，在图中从它的首字母向末字母连一条有向边。模型问题转化为在图中寻找一条不重复地经过所有边的路径，即欧拉路径。这个问题能够在O(|E|)时间内解决。实例：PKU2337问题描述给出一些字符串，让你首尾串起来串成一串，并且输出一个字典序最小的方案。如果不能，输出“***”。否则输出字典序最小的回路。输入26alohaarachniddoggopherrattiger3oakmapleelm输出aloha.arachnid.dog.gopher.rat.tiger***实例：PKU2337在没有特殊要求的情况下，DFS遍历图的结点顺序是可以任选的。但是这里由于加上了字典序最小的要求，所以DFS遍历时需要按照以下的优先顺序：1.如果有不是桥的边，遍历这些边中字典序最小的边。2.否则，遍历这些这些桥中字典序最小的边。比如一个单词，abcde，那么就连接一条a到e的有向边。如此构成的图一共最多有26个节点。每条边都代表一个单词，那么就转化成了：找一条路，遍历所有的边。就是欧拉通路问题。遍历欧拉通路的方法：确定一个起点（出度-入度=1，或者等于0（如果存在欧拉回路的话））从起点开始深搜（首先要保证图中存在欧拉回路或者通路）dfs(vid,eid)其中vid表示当前搜到的点。eid表示当前搜到的边（一个点可能会有很多边）对于每条边，都是等它搜索完了后，把它代表的内容（这里是单词）压入一个栈中。最后深搜结束后，依次弹栈就是答案。DoorMan

(SouthCentralUSA2002)大意：给定N(<=20)个房间,房间之间有门相隔，门的数目不超过100道，当前人在第M个房门，当前人每经过一道门的时候就把经过的门锁上，问有没有一条路可以使得我们走到第0个房门的时候所有的门都锁上了。思路：我们可以把门看成是两个房间之间的边，那么问题可以转化成找一条欧拉路径。PS：判断的时候只要判断所有的边在一起就行了，所有的点不一定连通，当0点和M点不连通的时候，无解。注意这组数据。最短路

定义1

设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记则称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)是G

中连接u,v的最短路.重要性质：

若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.

即：最短路是一条路，且最短路的任一段也是最短路.

求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.Bellman-ford算法算法简单介绍

这个算法能在更一般的情况下解决最短路的问题。何谓一般，一般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。适用条件:任意边权为实数的图Bellman-Ford算法Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作，要是一个结点的最短路径估计值也没能更新，就可以退出了。经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很多的数。算法简单介绍Bellmanford类似于Dijkstra算法，对每一个节点v，逐步减小从起点s到终点v最短路的估计量dist[v]直到其达到真正的最短路径值mindist[v]。Bellman-ford算法同时返回一个布尔值，如果不存在从源结点可达的负权回路，算法返回布尔值TRUE，反之返回FALSE。算法具体流程枚举每条边(u,v)∈E（G）。对枚举到的边进行一次松弛操作。回到步骤1，此过程重复n-1次，以确定没有可以更优化的情况。枚举每条边（u，v）若仍然存在可以更新的边，则说明有向图中出现了负权回路，于是返回布尔值FALSE。否则返回布尔值TRUE。voidBellman_ford(void){inti,j,k;for(i=1;i<=C;i++)Dist[i]=INF;Dist[S]=0;for(i=1;i<=C-1;i++){for(j=1;j<=C;j++)for(k=1;k<=C;k++)if(Dist[k]>Dist[j]+Graph[j][k])Dist[k]=Dist[j]+Graph[j][k];}for(j=1;j<=C;j++)for(k=1;k<=C;k++)if(Dist[k]>Dist[j]+Graph[j][k]){printf("-1");return;}return;}.......A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下

ForTime=1toN-1 For(u,v)∈E Relax(u,v)上图数据中，总运算量高达N^2而边(S,A1)虽然被调用N次。但实际有用的只有一次香甜的黄油

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）

香甜的黄油INPUTFORMAT第一行:三个数，奶牛数N，牧场数（2<=P<=800），牧场间道路数C(1<=C<=1450)第二行到第N+1行:

1到N头奶牛所在的牧场号第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的OUTPUTFORMAT

一行

输出奶牛必须行走的最小的距离和

香甜的黄油SAMPLEINPUT(filebutter.in)345234121135237243345

香甜的黄油SAMPLEOUTPUT(filebutter.out)8{说明：放在4号牧场最优}

负权回路输入数据给出一个有N(2<=N<=1,000)个节点，M(M<=100,000)条边的带权有向图.要求你写一个程序,判断这个有向图中是否存在负权回路.如果从一个点沿着某条路径出发,又回到了自己,而且所经过的边上的权和小于0,就说这条路是一个负权回路.如果存在负权回路,只输出一行-1;如果不存在负权回路,再求出一个点S(1<=S<=N)到每个点的最短路的长度.约定:S到S的距离为0,如果S与这个点不连通,则输出NoPath.负权回路输入格式（loop.in）第一行:点数N(2<=N<=1,000),边数M(M<=100,000),源点S(1<=S<=N);以下M行,每行三个整数a,b,c表示点a,b(1<=a,b<=N)之间连有一条边,权值为c(-1,000,000<=c<=1,000,000)输出格式（loop.out）

如果存在负权环,只输出一行-1,否则按以下格式输出共N行,第i行描述S点到点i的最短路:如果S与i不连通,输出NoPath;如果i=S,输出0;

其他情况输出S到i的最短路的长度.

负权回路样例输入

68113412634-7642245363451354样例输出064-3-27

例题二中国邮递员问题A城市的交通系统由若干个路口和街道组成，每条街道都连接着两个路口。所有街道都只能单向通行。每条街道都有一个长度值。例题二中国邮递员问题一名邮递员传送报纸和信件，要从邮局出发经过他所管辖的每一条街道，最后返回邮局。每条街道可以经过不止一次。他应该如何安排自己的路线，使得走过的总长度最短呢？样例路线总长度为14分析容易看出题目给出的是一个图的模型。在有向图中找一条权值最小的回路，使得它经过图中的每条边至少一次。分析如果问题有解，那么一定满足以下条件：

1、基图连通；

2、不存在某个顶点入度为0或出度为0。分析为了简化问题，我们暂时不考虑边的权值。问题的核心条件是：“每条边经过至少一次”。转化为如下形式：将图中的某些边拆分成若干条平行边，使得图中存在欧拉回路。分析设顶点v的入度与出度之差为p(v)。对于p(v)>0的顶点，需要增加p(v)条从v出发的边；对于p(v)<0的顶点，需要增加-p(v)条到v结束的边；对于p(v)=0的顶点，需要增加相等数量的从v出发的边和到v结束的边。分析p(v)>0网络的源点，向网络发出p(v)单位的流；p(v)<0p(v)=0网络的汇点，从网络接收

-p(v)单位的流；网络的中间结点，接收的流量等于发出的流量。分析原问题转化为多源多汇的最大流问题。我们可以通过附加超级源s和超级汇t的方法将其转化为单源单汇的经典最大流问题。分析下面我们考虑边的权值。对于原图中的边e，将其费用值w(e)赋为对应边的长度；其余的边不产生费用，将其费用值赋为0。求网络中从s到t的最小费用最大流。最后，我们只需根据各边的流量情况将原图进行改造，并在新图中求欧拉回路即可。小结本题的解答过程中，运用了欧拉图的一些性质对题目进行分析，通过联想、类比将问题对应到一个流网络模型上，并使用最小费用最大流算法解决问题。拓展如果将条件改成“所有街道都能够双向通行”，该如何解决？如果将条件改成“部分街道能够双向通行，部分街道只能单向通行”呢？例题三赌博机一台赌博机由n个整数发生器T1,T2,…,T