图论基础与网络流习题集锦

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