朱睿大牛：图论基础与网络流习题集锦

,图论基础与网络流习题集锦,北京大学 朱睿,大纲,图论部分：,1.,图论简介,2.,生成树与生成树计数,3.,欧拉回路与哈密顿回路,4.,割与流，匹配,网络流问题部分：,1.,习题,2.,习题,3.,更多的习题,图论简介,一个无向图,G,一般被抽象为一个二元组,1.V,是一个集合并被称为,G,的点集。,2.E,是,V,的无序积的多重子集，被称为,G,的边集。其元素被称为无向边。,一个有向图,D,一般被抽象为一个二元组,1.V,是一个集合并被称为,D,的点集。,2.E,是,V,的卡氏积的多重子集，被称为,D,的边集。其元素被称为有向边。,图的阶：即,|V|,。,零图,：,|E| = 0,。,基图：将,D,的有向边改为无向边，成为一个无向图。,无向完全图：简单无向图中每个点都与其他点相邻。,有向完全图：简单有向图中对于任意,vi,vj,V,都有,E,且,E,。,图论简介,平行边：即重边。,环：即自环。,简单图：不含平行边且不含环的图。,度：无向图中，与某点关联的边的数量。,入度，出度：有向图中，与某点关联的入边和出边的数量。,K-,正则图：无向简单图中所有点的度数都为,K,。,握手定理：所有点度数之和等于,2*|E|,。,同构：两个无向图,与,，若存在双射函数,f:V1-V2,，使得对于任意,vi,vj,V1,f(vi),f(vj),V2,时，,E1,当且仅当,E2,，则称这两个无向图同构。,生成树与生成树计数,生成树：一个连通无向图的极小连通子图，被称为这个图的生成树,最小生成树：一个边带权的连通无向图的极小连通子图，同时包含最小的边权,Prim,算法,Kruskal,算法,生成树计数问题：如何求出一个连通无向简单图的不重复生成树个数？,生成树与生成树计数,Matrix-Tree,（矩阵树）定理：,假设图,G,是一个包含,n,个点无向图。,定义,G,的度数矩阵,DG,为一个,n*n,的矩阵，并且对于任意,i,j,，有,Dij=0,；当,i=j,时，,Dij,为节点,i,的度数。,定义,G,的邻接矩阵,AG,为一个,n*n,的矩阵，并且对于任意,属于,G,的边集时，,Aij,为,1,；否则为,0,。,定义,G,的,Laplace,算子,(Kirchhoff,矩阵,),为,CG=DG-AG,。,那么图,G,的生成树个数为,CG,的任意一个,n-1,阶主子式（即去掉第,r,行第,r,列，,r,任意）的行列式之绝对值。,欧拉回路与哈密顿回路,欧拉回路：,对于一个连通图，遍历所有边并回到起点的路径被称为是一条欧拉回路。,无向图欧拉回路的充要条件：,连通并且每个点的度数都为偶数。,有向图欧拉回路的充要条件：,强连通并且每个点的入度和等于出度和。,欧拉回路与哈密顿回路,哈密顿回路：遍历图中所有点一次且仅一次并最终回到起点的路径被称为哈密顿回路。,哈密顿通路：遍历图中所有点一次且仅一次的路径被称为哈密顿通路。,到目前为止，还没有一个简明的条件能作为判断一个图是否存在哈密顿回路的充要条件,T T,这里给出一个充分条件：,若对于无向简单图,G,，任意两个不相邻点的度数之和大于或等于,n-1,，则该图存在哈密顿通路。,若对于无向简单图,G,，任意两个不相邻点的度数之和大于或等于,n,，则该图存在哈密顿回路。,割与流，匹配,流：,假设,G,(,V,E,),是一个有限的有向图，它的每条边,(u,v)E,都有一个非负值实数的容量,c,(,u,v,),。如果,(u,v),不属于,E,，我们假设,c,(,u,v,) = 0,。我们区别两个顶点：一个源,s,和一个汇,t,。一个网络流是一个对于所有结点,u,和,v,都有以下特性的实函数,f:VVR,其满足以下三个要求：,1.,容量限制：,f(u,v) = c(u,v),2.,斜对称：,f(u,v) = -f(v,u),3.,流守恒：除非,u=s,或,u=t,，否则,(wV) f(u,w) = 0,则该网络流的流量为,s,的总输出（或,t,的总输入）,割：设,Ci,为网络,N,中一些弧的集合，若从,N,中删去,Ci,中的所有弧，即：使得从,顶点,Vs,到顶点,Vt,的路集为空集时，称,Ci,为,Vs,和,Vt,间的一个割。,割与流，匹配,最大流：从,s,到,t,的所有可行的网络流中，流量最大的网络流。,最小割：从,s,到,t,的割中，删除边权和最小的割。,对于一个给定的,s,和,t,，最大流,=,最小割,割与流，匹配,对于一个无向图,G = ,点独立集：,V,的一个子集 使得该集合中任意两点之间没有边。,点支配集：,V,的一个子集 使得任意,V,中元素要么属于该集合，要么与该集合中点有边相连。,点覆盖集：,V,的一个子集 使得任意,E,中元素都与该集合中某个或某两个元素相关联。,极大,/,最大点独立集，极小,/,最小点支配集，极小,/,最小点覆盖集。,同样的，我们可以定义边覆盖集（即用边覆盖所有点）与边独立集（即任意两条边之间没有共同点）。,割与流，匹配,匹配：,G,的一个边独立集，又被称为,G,的一个匹配。,极大匹配与最大匹配。,二部图（二分图）：若无向图,G,的点集,V,可以分割成两个互不相交的子集，并且对于边集,E,中的所有边,(vi,vj),所关联的两个顶点,vi,和,vj,都分属这两个子集，那么图,G,就被称为一个二部图。,二部图匹配的霍尔定理（婚姻定理）：设有二部图,G=,且,|V1|,出度和的点连一条大小为,|,入度和,-,出度和,|/2,的边，所有出度和,入度和的点连一条,|,出度和,-,入度和,|/2,的边。,无向图中边,(vi,vj),若变成了有向边,，那么在流中连一条容量为,1,的边,，意为反悔。满流则有解。,网络流习题集锦：趣味工厂,有一个工厂，工厂中有,n,个工人与,n,种产品。每个工人能够生产这些产品中的一部分。,现在我们希望作一个,k,天的工作规划，使得每一天每一个产品恰好有一个工人在从事生产，并且在这,k,天内每个工人都不会生产重复的产品。,1n100, 1kn,思考：直接的贪心算法是否正确？,网络流习题集锦：趣味工厂,解答：,将所有工人看做一个点排成一排在左边，所有产品看做一个点排成一排在右边，若某个工人会制造某个产品，则在相应的两个点上连容量为,1,的边。,此时，我们考虑到对这个图做网络流，源向左边每个点都连一条容量为,K,的边，右边每个点向终点连一条容量为,K,的边，如果没有流满，那么显然是不可能有解的。而如果流满，则根据,Hall,定理，我们也可以知道它是有解的，然后一遍一遍进行二分图匹配即可。,网络流习题集锦：路径覆盖,路径覆盖类题目，主要是指这样一类问题：给定一个图以及一系列行走规则，问如何使用最小的代价将用一系列按照行走规则的路径覆盖住。,下面我们就来具体问题具体反分析。,网络流习题集锦：股票走势,小,L,最近迷恋上了炒股，他拿到了,n,支股票在,0,到,k-1,时刻的价格表。他想要把每只股票的价格根据时刻依次连成一个走势折线图，以此观察股票的情况。,但是小,L,不想铺张浪费，所以在每张纸上他不想只画一条折线，而是把尽量多的折线画到一张纸上，使用尽量少的纸。两条折线能够画到一张纸上，是要求它们不相交，包括在端点处。,数据规模：,1n100,，,2k25,思考：如何找到图中的网络流模型？,提示：发现“折线”这一条件的特殊性。,网络流习题集锦：股票走势,解答：,首先考虑如何建图。,假设我们将每只个股都看做一个点，如果,A,与,B,可以放在一张纸上，就连一条边，这样得到了一个无向图。,但是很不幸，这个无向图没有给我们提供任何信息。,考虑到折线一定是连续的，那么两个可以在同一张纸上的股票，是可以定义序关系的的。,将无向图改造成有向图，若某只股票的折线完全高于另一只股票的折线，那么连一条有向边，这样我们得到了一个拓扑图，问题转化成了用最少的链来覆盖这个有向图，即最小链覆盖。,使用匹配,/,网络流解决最小链覆盖，由于链上每个节点都有一个后继节点，那么将每个点拆成两个点排成两排，若,A,能到,B,则从,A,左向,B,右连边，那么答案就是,n-,匹配数。,网络流习题集锦：星际竞速,N,个点,M,条边的有向图，将所有点从,1N,标号，每条边,Eij,都只能从编号小的点走到编号大的点，代价为,Pij,。,可以使用瞬移，从任意点瞬移到,i,号点的代价为,Ai,。,要求从一个标号为,N+1,的孤立点出发，经过所有点一次且仅一次，问最小代价。,N =800,，,M (u, u),。,从,st,向所有,u,连边，容量为,1,费用为,0,；,从所有,u,向,en,连边，容量为,1,费用为,0,；,若,u,v,之间在原图中有边，那么在,u,与,v,之间连边，费用为路径费用,Puv,，容量为,1,。,从,st,向所有,v,连边，费用为瞬移到,v,点的代价。,在这个图上运行费用流，就能得到最小代价。,网络流习题集锦：营救行动,一个,N,个点,M,条边的带点标号的无向图，经过一条边需要一定的时间。现在有,K,个人在,0,号点，,K,个人可以分头行动。在访问第,i,号点之前不能经过第,i+1,号点，,K,个人中任意一个经过某个点之后就可以认为该点被访问了。问访问完所有点的前提下，这,K,个人的行走路径长度之和最小是多少。,网络流习题集锦：营救行动,其实这也是一道路径覆盖的题目，相当于把,1n,这个序列拆成,K,个序列，并使得总路程和最小。,于是我们可以先用改动过的,Floyd,算法求出在保证只访问标号比,i,j,都小的节点的前提下，,i,到,j,的最短路。,之后和上题有相似之处，将点,i,拆成两个点,Ai,和,Bi,。,对于,i!=0,，由,Ai,向,Bi,连一条费用为,0,容量为,1,的边，然后,Bi,向汇点连一条容量为,1,费用为,0,的边。,源点向,B0,连一条容量为,k,费用为,0,的边。,每个,B,点都向比自己大的,A,点连一条容量为,1,费用为最短路的边。,等等，这个算法好像有问题？,与上一题不同的是，这题要求遍历所有节点。因此我们应该把所有,A-B,的边增设下界,1,。,网络流习题集锦：闭合子图,最大权闭合子图类问题：,给定一些事件。,事件之间有依赖关系，比如若选了,A,就一定要选,B,。,建图的经典思想：,S-(pA)A-(inf)B-(pB)T,S-A-T,S-B-T,A-(c)B,用,c,作为最小割,网络流习题集锦：加工顺序,有,N,个工作，,M,种机器，每种机器你可以租或者买过来,.,每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数，求最大利润。,N=1200,M=1200,网络流习题集锦：加工顺序,分析与解答：,这道题显然是最大权闭合子图的模型。,将所有任务放在左边，源向任务连容量为报酬的边；将所有机器放在右边，向汇连容量为购买代价的边；,任务向它需要的机器连容量为租用代价的边。,网络流习题集锦：最优选择,给定一张,n,个点的无向简单图，上面有一些点给定了一个整数的权值，有一些点没有。定义一条边的权值为它相关联的两个点的权值的异或。现在要求你确定剩下的那些点的权值，使得该图的边权和最小。,N=500,提示：按位处理。,网络流习题集锦：最优选择,解答：首先可以发现，位与位之间没有任何关系，可以按位处理。也就是说，我们只需要确定某个点选,0,还是选,1,就可以了。,由于只有,01,不同的点才会产生代价，那么我们自然的想到了最小割，也就是使,01,不同的边尽量少。,建立虚拟源汇,st,，,en,。将,st,向所有已经标为,0,的点连容量为无穷的边，从所有已经标为,1,的点向,en,连容量为无穷的边，对于原图的每一条边都变成一条新的流量为,1,的双向边。对于这个图，求出其最小割，则与源点在同一个割集的点填,0,，与汇点在同一个割集的点填,1,即可。,谢谢,zrphercule,