图论算法及其建模-朱全民力作课件

图论基本算法及其模型构建NOIP若干图论的考题Core(2007)

:图的多源最短路算法及其简单处理双栈排序(2008):栈的应用+二分图的搜索最优贸易(2009):基本图论关押罪犯(2010):二分答案+二分图的判定引水入城(2010)：二分图的构造+贪心图图的概念

G=(V,E)图的基本概念有向图、顶点、入度、出度、弧、环无向图、边、路径、顶点的度、邻接简单图、完全图平面图、二分图

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.

以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.

根据此图便可找到渡河方法.(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示

权矩阵

无向图G的权矩阵A是一个对称矩阵.

邻接表表节点

typearcptr=^arcnode;arcnode=recordadjvex:vtxptr;nextarc:arcptr;info:…{和弧有关的其他信息}end;vex=Recordvexdata:…{和顶点有关的其他信息}firstarc:arcptr;end;adjlist=array[vtxptr]ofvexnode;图的连通性问题无向图的连通分量直接遍历得到的顶点序列即为一个连通分支有向图的强连通分量有向图G=(V,E)中，如果两个点A和B，从A出发有路径可以到B、并且从B出发有路径可以到A，那么就称A和B属于同一个连通分量。对于V的一个子集V’，如果V’中任意两个点都属于同一个连通分量，则V’称之为一个强连通分量。对于一个强连通分量V’，如果加入任意一个点v，V’∪{v}都不再是一个强连通分量，则V’就称之为一个极大强连通分量。思考题1：求网线线序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,…,N

给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号思考题2：神经网络

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。兰兰规定，Ci服从公式(1)（其中n是网络中所有神经元的数目）公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态Ci，要求你的程序运算出最后网络输出层的状态。

【输入格式】

第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij【输出格式】

输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！若输出层的神经元最后状态均为0，则输出NULL。点连通度与边连通度在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。求割点与桥（R.Tarjan算法）DFS(u)：u在搜索树（以下简称为树）中被遍历到的次序号。Low(u)：u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。显然有，Low(u)=Min

{DFS(u)，

DFS(v)(u,v)为后向边(返祖边

Low(v)(u,v)为树枝边(父子边)

}割点和桥的判定一个顶点u是割点，当且仅当满足(1)或(2)

(1)u为树根，且u有多于一个子树。

(2)u不为树根，且满足存在(u,v)为树枝边

(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。求点双连通分支对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。求边双连通分支对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。思考题3：受欢迎的牛每一头牛的愿望就是变成一头最受欢迎的牛。现在有N(N<=10000)头牛，给你M(M<=50000)对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。欧拉道路和回路经过每条边一次且仅一次先看回路必要条件：所有点度为偶数充分条件：还是“所有点度为偶数”证明！把欧拉回路构造出来“圈套圈”可能套不出来吗？想一想欧拉道路和回路有向的情形入度=出度如何套圈？道路有两个奇度点正好是起点和终点哪个是起点，哪个是终点？有向+无向怎么办？网络流！不要求掌握最小生成树问题求一个连通子图，使得边权和最小Prim算法任意时刻的中间结果都是一棵树从一个点开始每次都花最小的代价，用一条加进一个新点问题：这样做是对的吗？如何快速找到这个“最小代价”？时间复杂度分析一般：O(n2)堆优化：O(n*logm)Prim算法的正确性换一种说法如果存在一个MST，包含当前所有边则也存在一个MST,它包含最小代价边(u,v)反证法！假设存在这样的MST当前结点集为S，剩下的结点集为T由于在MST中S-T连通一定有跨越S-T的某边(u’,v’)它不是最小代价边(u,v)删除(u’,v’)，加入(u,v)，S和T分别连通，且S-T通过(u,v)连通得到了一个更小的MST！Kruskal算法任意时刻的中间结果是一个森林从n个点的集合开始每次选不产生圈的前提下权最小的边加入问题：这样做是对的吗？如何快速的判断是否产生圈时间复杂度分析O(mlogm)思考题5：其他问题次小生成树：所谓次小生成树就是只比最小生成树的权和大一点的生成树。K度最小生成树：给出一个K，某个结点的度不能超过k的最小生成树。最大边-最小边最小生成树有根生成树，给定一个根，其他结点的权为每个结点到根结点路径，求最小生成树最短路问题问题描述：给加权图GSSSP：求给定起点s到其他所有点的最短路APSP：求每两对点的最短路算法标号设定类：dijkstra标号修正类：bellman-ford动态规划类：floyd-warshall变形与应用举例SSSP(Dijkstra算法)核心思想：按路径递增的次序产生最短路径的算法

1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点

2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,若经过vj,将j设为已检查的点,放入集合.3)以次短路径出发找第三短的路径,类似第二步的方法.4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点的最短路径求出.Dijkstra算法令d’(u)=min{d[v]+w(v,u)|v存在}，设中最小的元素为i，则令（即求出了i的最短路长度），并根据d[i]来对进行更新。每次求出一个d值，重复n次就可以得到所有点的最短路径长度。下面是Dijkstra算法的伪代码：ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin(ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin();{取出d’中值最小的结点i}d[i]:=d’(i);Delete(i,d’);{令d[i]等于d’(i)，并将i从d’中删除}Foreachnodeuexistedge(i,u)【{对每条从i连出的边进行检查}Ifd’(u)<d[i]+w(i,u)Thend’(u):=d[i]+w(i,u);】{根据d[i]对d’(u)进行更新}】End;Dijkstra算法适用条件:所有边的权值非负定理2每当结点u插入集合S时，有d[u]=w(s,u)成立。效率:用一维数组来实现优先队列Q，O(V2)，适用于中等规模的稠密图二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂度过高，理论价值远大于实用价值思考题6：最优乘车一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士,这样换乘几次后到达S公园。现在用整数1，2，……N给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，2，……S，公园巴士站的编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。输入N和M条公交线路信息求最少换车的次数Bellman-Ford算法Bellman-Ford算法流程分为三个阶段：(1)初始化：将除源点外的所有顶点的最短距离估计值

d[v]←+∞,d[s]←0;(2)迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）(3)检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在

d[v]中。Bellman-Ford算法Bellman-Ford算法运用了松弛技术，对每一结点v∈V，逐步减小从源s到v的最短路径的估计值d[v]直至其达到实际最短路径的权w(s,v)，如果图中存在负权回路，算法将会报告最短路不存在。Bellman-Ford(G,w,s)：boolean//图G，边集函数

w，s为源点

foreachvertexv∈V（G）

do//初始化

1阶段

d[v]←+∞

d[s]←0;//1阶段结束

fori=1to|v|-1do//2阶段开始，双重循环。

foreachedge（u,v）∈E(G)do//边集数组要用到，穷举每条边。

Ifd[v]>d[u]+w(u,v)then//松弛判断

d[v]=d[u]+w(u,v)//松弛操作

2阶段结束

foreachedge（u,v）∈E(G)do

Ifd[v]>d[u]+w(u,v)then

Exitfalse

ExittrueBellman-Ford算法适用条件:任意边权为实数的图Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作，要是一个结点的最短路径估计值也没能更新，就可以退出了。经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很多的数。SPFA(ShortestPathFasterAlgorithm)SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列

queue和一个指示顶点是否在队列中的标记数组

mark。定理4在平均情况下，SPFA算法的期望时间复杂度为O(E)。证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条边的图，点的平均出度为E/V，所以每处理一个点的复杂度为O(E/V)。假设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布有关。我们设h=kV，则算法SPFA的时间复杂度为在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在一般情况下的时间复杂度为O(E)。（证毕）SPFA算法适用条件任意边权为实数的图定理3只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）SPFA算法

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。SPFA(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.WhileNotEMPTY(Q)5.Dou←DLQUEUE(Q)6.For每条边(u,v)E[G]7.Dotmp←d[v]8.Relax(u,v,w)9.If(d[v]<tmp)and(v不在Q中)10.ENQUEUE(Q,v)

我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：思考题7：最优贸易C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。设C国n个城市的标号从1~n，阿龙决定从1号城市出发，并最终在n号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。阿龙决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。假设C国有5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。假设1~n号城市的水晶球价格分别为4，3，5，6，1。阿龙可以选择如下一条线路：1->2->3->5，并在2号城市以3的价格买入水晶球，在3城市以5的价格卖出水晶球，赚取的旅费数为2。阿龙也可以选择如下一条线路1->4->5->4->5，并在第1次到达5号城市时以1的价格入水晶球，在第2次到达4号城市时以6的价格卖出水晶球，赚取的旅费数为5。现在给出n个城市的水晶球价格，m条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。样例3767473621356747362135APSP:floyd-warshall算法设d[i，j，k]是在只允许经过结点[1…k]的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：如果最短路经过点k，那么d[i，j，k]应该等于d[i，k，k-1]+d[k，j，k-1]；如果最短路不经过点k，那么d[i，j，k]应该等于d[i，j，k-1]。综合起来d[i，j，k]=min{d[i，k，k-1]+d[k，j，k-1]，d[i，j，k-1]}边界条件是d[i，j，0]=w(i，j)（不存在的边权为∞）算法框架基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路fork:=1tondofori:=1tondoforj:=1tondoif(d[i,k]<∞)and(d[k,j]<∞)and(d[i,k]+d[k,j]<d[i,j])thend[i,j]:=d[i,k]+d[k,j]时间复杂度：O(n3)用途：预处理！一定要背下来！思考题8：树网的核给出一棵无根树，边上有权。称树的最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。

思考题9：瘦陀陀和胖陀陀一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。瘦陀陀处在城市A胖陀陀处在另外一个未知的城市他们打算选一个城市X（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市X然后等待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）接着一起回到他们的家乡城市B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。一个例子（续）瘦陀陀正专注地看回家的地图地图上标有n（n≤200）个城市和某些城市间直达的道路以及每条道路的过路费瘦陀陀还知道在每一座城市举办宴会的花费。给出地图和A、B的位置请你告诉瘦陀陀回家的最小费用你的程序会接收到多次询问即对于每对城市(c1,c2)，你的程序应该立刻给出瘦陀陀从c1到c2的最小花费。二分图定义1： 令X={x1,x2,…,xm},Y={y1,y2,…,yn},且X∩Y＝Ф，而△是序偶e=(x,y)的集合，其中x∈X,y∈Y,那么三元组G＝（X，△，Y）称作偶图，也叫二分图。简单来说:二分图就是把图的点集分为两个（X和Y），其中只有X中的点和Y中的点有边，X和Y内部的点没有边。如图：三个典型问题

在一个有禁止位置的m×n棋盘上，能放置非攻击型车的最多个数是多少？在一个有禁止位置的m×n棋盘上，能放置多米诺牌覆盖的最多个数是多少？一个公司有n个工作空缺，需要有一定技能的人填补，同时有m个人申请这些项工作，每人能胜任n项工作中的若干项，问最多有多少项工作能找到合适的人选？二分图的构造采用深度优先遍历：对所遍历的点编号为奇数的染黑颜色，为偶数的染白颜色。若对某个点既要然黑颜色，也要染白颜色，则不能构成二分图采用宽度优先遍历，对奇数层结点染黑色，对偶数层结点染白色，若发现某个结点即属于奇数层，也属于偶数层，则不能构成二分图把所有的黑点放在一个集合，所有白点放在一个集合，然后将原来的边连起来，就是二分图。思考题10：关押罪犯S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间发生摩擦，并成影响力为c的冲突事件。警察局长准备将罪犯们在座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？4614253423351212283511366182418053412884【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。思考题11：引水入城为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。样例36845644734333322112思考题12：双栈排序有两个队列和两个栈,分别命名为队列1(q