计算机算法基础 第2版 习题及答案 第11章

PAGE1第11章 网络流在例11.7的网络中，如果集合S={s，v3，v4}，T={v1，v2，t}，那么割(S,T)的容量是多少？解： 割(S,T)的容量是c(S,T)=13+12+9+19+7=60，参照下图。svsv1v2v3v45412181376109t19假设f是网络G(V,E)的一个流。证明，在剩余网络Gf(V,Ef)中，任一对顶点u和v之间有如下关系:cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。证明： 因为cf(u,v)=c(u,v)-(u,v)和cf(v,u)=c(v,u)–(v,u)，我们有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)–[(u,v)+(v,u)]。因为[(u,v)+(v,u)]=0，从而有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。证明任一个网络G(V,E)的最大流总可以由最多m个增广路径增广而得。(等价地证明，其最大流可以分解为最多m个增广流之和。)证明： 假设f是G(V,E)的最大流，其值为|f|=F。我们先复制一个网络G(V,E)的考贝，G’(V’,E’)=G(V,E)。其中，V’=V，E’=E，c’(u’,v’)=c(u,v)。因为网络G’和G完全一样，网络G的最大流也必定是G’的最大流，反之也成立。现在，我们利用G(V,E)的最大流f来找G’(V’,E’)的最大流。设G’(V’,E’)的初始流是零。我们证明，最多m次增广路径的增广可得到G’(V’,E’)的最大流。在G(V,E)中一条从源点s到汇点t的路径p称为一条流路径(flowpath)，如果路径p经过的每条边都有非零的流。我们定义这条流路径的流量为fp=min{f(u,v)|(u,v)p}，也就是路径p上有最小流量的边上的流。我们从G(V,E)的最大流f来找G’(V’,E’)的最大流的算法如下。Max-flow(G’(V’,E’))foreachedge(u’,v’)E’ f’(u’,v’)0 //初始流为零endforforeachedge(u,v)E F(u,v)f(u,v) //F(u,v)记下f的初值，算法会更改变f，但不改FendforwhilethereexistsaflowpathpinG(V,E) //如果存在一条s到t的流路径p(可用BFS找) f(p) //f(p)是p的流量，f(p)=min{f(u,v)|(u,v)p} foreachedge(u,v)p f’(u’,v’)f’(u’,v’)+ //增加G’中边(u’,v’)上流量 f(u,v)f(u,v)- //减少G中边(u,v)上流量 endforendwhileEnd上面算法的正确性可以证明如下。首先，我们证明，一条G中的流路径就是G’中的增广路径。因为G’中的任何一条边(u’,v’)上流量的增加就等于G中边(u,v)上流量的减少，两者之和f’(u’,v’)+f(u,v)始终不变，f’(u’,v’)+f(u,v)=0+F(u,v)c(u,v)=c’(u’,v’)，所以，在每次第7行while循环之后，G’中边(u’,v’)上的剩余容量c’f(u’,v’)满足以下不等式：c’f(u’,v’)=c(u,v)-f’(u’,v’)F(u,v)-f’(u’,v’)=f(u,v)。因此，只要f(u,v)>0，就有c’f(u’,v’)>0。所以，一条G中的流路径就是G’中的增广路径。其次，容易看出，每一次G中的流减少以后仍然是一个正常流。这是因为它满足f(u,v)c(u,v)和流量守恒。现在需要证明的是，只要G中的流不是零，就一定有流路径。我们用反证法。如果不是，那么，我们把所有从源点s有流路径可达的点放在集合S中，其它点放在集合T中。因为tT，(S,T)必定是个割，并且有f(S,T)=0从而|f|=0。这与G中的流不是零相矛盾。所以，上面的算法Max-flow正确地产生G’(V’,E’)的最大流。因为每次增广后，G中至少有一条边的流量为零，所以经过最多m次增广，G中所有边的流量为零，算法结束。这时，G’中的流增加到最大，并有流|f’|=F。因为网络G与G’完全一样，网络G(V,E)的最大流也可以由最多m个增广路径增广而得。用Edmonds-Karp算法找出以下每个网络的一个最大流。请参照图11-7的形式，图示每轮中的剩余网络，所用增广路径，以及对应的增广流。另外，请给出一个最小割。1212sv1v2v3v4471314164109t20(a)11sv1v2

v3

v4

615172124109t194(b)解： (a)tt12sv1v2v3v447131416410920(a)12/12sv1v2v3v40/40/70/130/1412/160/40/100/9t12/20(b)tt12/12sv1v2v3v40/40/74/134/1412/164/40/100/9t12/20(d)12sv1v2v3v4471314441098(c)121212/1212/12sv1v2v3v40/47/711/1311/1412/164/40/100/9t19/20(f)t12sv1v2v3v447910441098(e)1212441212sv1v2v3v4472344109t1(g)12191111图(f)中流是最大流，流量是23。一个最小割（S,T）是：S={s,v1,v2,v4}，T={t,v3}。(b)1111sv1v2v3v4615172124109t194(a)11/11sv1v2v3v40/60/150/1711/210/240/100/9t11/190/4(b)tt11/11sv1v2v3v40/615/1515/1711/2115/240/100/9t11/190/4(d)11sv1v2v3v461517102410984(c)1111tt11/11sv1v2v3v40/615/1515/1715/2119/240/100/9t11/194/4(f)11sv1v2v3v46151510910984(e)111121511/1111/11sv1v2v3v40/615/1517/1717/2121/242/100/9t11/194/4(h)11sv1v2v3v46151565109t84(gv1v2v3v4615174389t84(i)1711221图(h)中流是最大流，流量是32。一个最小割（S,T）是：S={s,v1,v2}，T={t,v3,v4}。如果把一个有向图G(V,E)中的一个边的集合H刪去后，图中没有从顶点a到顶点b的路径，那么称H为a到b的一个割。如果H是所有a到b的割中最小的，也就是它含有的边的个数最少，则称H为a到b的一个最小割，并且称|H|为a到b的边连通度。如果G本身就没有从a到b的路径，那么最小割为空集，a到b的边连通度为0。请把计算有向图G(V,E)中的从a到b的边连通度问题建模为一个网络流问题来解，使得流网络中的点的个数不超过O(n)，而边的个数不超过O(m)。这里，n=|V|，m=|E|。请严格证明你的方法的正确性。解： 建模和计算的过程表达在下面的伪码中。Edge-Connectivity(G(V,E),a,b)构造流网络G’(V’,E’)，其中V’=V，E’=E，并赋以E’中每一条边容量1以a为源点，b为汇点，计算网络G’(V’,E’)的最大流f和最小割(S,T)，让C(a,b)为所有穿越边的集合HC(a,b)k|H|returnH,k //最小割是H，连通度是kEnd算法正确性证明如下。首先，因为点aS，bT，删除集合H后，没有路径可以从点a到达点b，所以集合H是a到b的一个割。又因为每条边的容量是1，所以，c(S,T)=|C(a,b)|=|H|=k。下面证明，集合H小于等于任何一个a到b的割。假设H’是任意一个a到b的割。我们由H’构造一个流网络G’(V’,E’)的割(S’,T’)如下：E’E’–H’(删除H’)在余下的图G’中，定义集合S’为V’中有路径从点a可达的点，即S’={uV’|thereisapathpinG’fromnodeatonodeu}定义集合T’=V’–S’。因为H’是一个a到b的割，所以顶点b不属于集合S’。那么，(S’,T’)就是网络G’(V’,E’)的割。由最大流最小割定理，算法得到的割H最小，故满足|H|=|f|c(S’,T’)。所以(S’,T’)至少有|H|=k条穿越边。因为集合T’中的点都没有从点a可达的路径，所以，所有穿越边一定被删除了。这也就是说，H’包含了(S’,T’)中的所有穿越边。这意味着c(S’,T’)|H’|。因此有|H||H’|，H是a到b的一个最小割。如果把无向图G(V,E)中的一个边的集合H刪去后，剩余的图是一个不连通图，那么H称为一个割。图G的最小割所含的边数称为G的边连通度。如果G是个不连通图，那么最小割H为空集，G的边连通度为0。如果G是棵树，显然连通度为1，而一个回路的连通度为2。请设计一个用网络流来决定一个无向图G(V,E)的边连通度的算法。你调用网络流算法的次数不应超过n次，而且每次构造的流网络中的点的个数不超过O(n)，边的个数不超过O(m)。这里，n=|V|，m=|E|。解： 我们先构造一个加权有向图G’(V’,E’)，其中V’=V,E’={(u,v),(v,u)|(u,v)E}，即G中每条边(u,v)对应为G’中一对有向边(u,v)和(v,u)，并且赋给每条边容量1。构造好以后，算法如下。Undirected-Graph-Edge-Connectivity(G’(V’,E’))H’kSelectavertexsV’ //任选一个顶点sforeachvV’–{s} UseEdmonds-Karp(G’(V’,E’),s,v)tofindaminimumcut(S,T)。 //以s为源点，v为汇点，用Edmonds-Karp算法计算G’的最小割(S,T) C{(u,v)E’|uS,vT} //(S,T)的所有穿越边集合 if|C|<k then H’C k|C| endifendforH{(u,v)E|(u,v)H’} //H中边是图G中无向边returnH,kEnd因为|V’|=|V|，|E’|=2|E|，所以算法中每次求最大流的网络中的点的个数不超过O(n)，而边的个数不超过O(m)。另外，算法中一共调用最大流的算法n-1次，所以，复杂度符合要求。现在证明其正确性。首先，由G’(V’,E’)的构造知，如果H’是G’(V’,E’)中以s为源点，v为汇点的一个割(S,T)，其中sS，vT，那么，我们可由H’得到G(V,E)的一个割H如下：H={(u,v)E|(u,v)H’}。我们注意到，如果(u,v)H’，那么uS，vT。所以，(u,v)H’当且仅当((u,v)H，uS，vT)。因为删除H’后，图G’中没有从集合S到T的边，那么，删除H后，图G中也没有从集合S到T的边。所以H是G(V,E)的一个割。另外，任何一对边(u,v)和(v,u)之间，只能有一条属于H’，所以有|H|=|H’|。反之，如果H是G(V,E)的一个割，把H删除后，G(V,E)不连通，集合V可分为两部分，S和T，使得S和T之间没有边，并且有sS。选集合T中任一点v，那么，由H可构造一个G’(V’,E’)的以s为源点，v为汇点的一个割H’如下：H’={(u,v)E’|(u,v)HanduS,vT}。因为删除H后，图G中没有从集合S到T的边，那么，删除H’之后，图G’中也必定没有从集合S到T的边。所以H’是G’(V’,E’)的一个割。因为边(u,v)H对应的一对边(u,v)和(v,u)之间，只能有一条可以被选入H’，所以有|H|=|H’|。所以，找到G’(V’,E’)的任何两点间的最小割，就找到了G(V,E)的最小割。因为G’(V’,E’)的最小割一定会把顶点s和某个顶点v分开，所以我们对集合V-{s}中每个点v，逐个找出把顶点s和v分开的最小割。显然，其中最小的就是解。上面的算法Undirected-Graph-Edge-Connectivity正是这一思路的实现。如果一个图G(V,E)中的每个点的度数等于d，d>0，则称为d-正则图(d-regulargraph)。假设G(V,E)是一个d-正则的二部图，其中V=LR，而且|L|=|R|。E中任一条边连结L中一个点和R中一个点。证明这个二部图有完美匹配。证明： 我们只要证明这个二部图满足Hall氏定理。假设SL是集合L的任一个子集。R(S)是S在R中的映象，即R(S)={vR|uL使得(u,v)E}。考虑在S和R(S)之间的所有边的集合E’={(u,v)|uS，vR(S)}。因为S中每个点有相同度数d，所以有|E’|=d|S|。再考虑在L和R(S)之间的所有边的集合E’’={(u,v)|uL，vR(S)}。因为R(S)中每个点有相同度数d，所以有|E’’|=d|R(S)|。因为E’E’’，所以d|S|d|R(S)|，因此有|S||R(S)|。根据Hall氏定理，这个二部图有完美匹配。证明定理11.18:假设G(V,E)是一个单分支0-1网络，那么用Dinic算法计算它的最大流的时间复杂度是O(mn)。证明： 首先，我们注意到，对应于G(V,E)上的任一个整数流f的剩余图Gf也是一个单分支网络，这是因为每条边上要么没有流，要么流为1。所以，如果有流经过一个有单入边顶点u(us，ut)的话，在剩余图Gf中，它的单入边成为一条出边，而其中一条有流的出边成为一条单入边，所以点u仍然是一个单入边顶点。同理，如果有流经过一个有单出边顶点的话，这个点在剩余图Gf中仍然是一个有单出边的点。其次，假设剩余图Gf中，从源点s到汇点t的距离是k。V0,V1,…,Vk是Gf的距离图中各级顶点的集合，其中sV0，tVk。那么，我们可以为任一级顶点Vi，1£i£k-1，构造一个割。设Vi={v1,v2,…,vh}，构造一个割的步骤如下：SV0V1…Vi-1TVi+1Vi+2…Vk对Vi中每一个点v，如果点v有一条单入边，那么把点v归入集合T，否则点v有一条单出边，把点v归入集合S。容易看出，(S,T)是一个割。因为每条穿越边关联Vi中一个点，并且是一条单入边或单出边，所以，它的容量为c(S,T)=|Vi|。如果最大流的值是F的话，因为每条边容量是1，因而有Fc(S,T)=|Vi|(1£i£k-1)。由此得到i=1k-1Fi=1k-1|Vi|n-2<n，也就是(k-1)F<n或k<n/F+1，也就是k用证明引理11.17的方法可证Dinic算法只需进行2n轮阻塞流的计算。细节如下：如果网络中最大流Fn，那么Dinic算法显然只需进行最多Fn轮阻塞流的计算。如果网络中最大流F>n，那么经过n轮阻塞流的计算后，设网络G中流是f，而剩余网络中的最大流是Mf。因为这时距离图中s到t的距离k至少为n，kn，但是,又必须有kn/Mf，这里Mf是在剩余网络中的最大流。所以有Mfn/kn/n=n。这样，最多再经过n轮阻塞流的计算后即可找到最大流。因每次阻塞流的计算只需O(m)(矩阵平分问题)假设A={aij}是一个n´n的整数矩阵，其中每个元素都是非负整数，aij0(1£i,j£n)。我们用ARi和ACj分别表示矩阵A的第i行元素之和，与第j列的元素之和，即ARi=j=1naij(1£i£n)和ACj=i=1naij(1£j£n)。为简单起见，假设这些和都是偶数。现在我们希望把A分解为两个整数矩阵B和C之和，即A=B+C，使得B的第i行元素之和等于C的第i行元素之和，BRi=CRi(1£i£n)，而B的第j列元素之和也等于C的第j列元素之和，BCj=CCj(1£j£A=ARi53030请把这个矩阵平分问题建模为一个网络流问题，并证明一定有解。解： 我们构造一个流网络G如下:(a) 构造一个有向二部图G(UV,E)，其中U={u1,u2,…,un}代表矩阵A的n行，而V={v1,v2,…,vn}代表A的n列。如果aij>0，那么构造一条边(ui,vj)并赋以容量c(ui,vj)=aij。(b) 加上源点s，然后为U中每个点ui(1£i£n)，加上边(s,ui)并赋以容量c(s,ui)=12ARi(c) 加上汇点t，然后为V中每个点vj(1£j£n)，加上边(vj,t)并赋以容量c(vj,t)=12ACj作为例子，下面图示了由题中矩阵A所构造的网络。容易看出，这个网络的最大流使所有边(s,ui)饱和(1£i£n)，也使所有边(vj,t)饱和(1£j£n)。这是因为我们可以这样构造一个流f：f(s,ui)=c(s,ui)=12ARi (1£i£nf(vj,t)=c(vj,t)=12ACj (1£j£nf(ui,vj)=12c(ui,vj)=12aij (1£i,j£nuu1v1u2u3v2u4v3v4st63255533534321134411显然这是一个合法的流，并且使所有边(s,ui)饱和(1£i£n)，也使所有边(vj,t)饱和。这个流不一定是整数流，但因为网络中每个边容量为整数，所以必存在有等值的整数流。下面图显示上面图中网络的一个最大整数流。uu1v1u2u3v2u4v3v4st6/63/32/25/55/55/53/33/31/53/32/41/31/21/10/12/34/41/40/10/1有了这个最大整数流f，置元素bij=f(ui,vj)(1£i,j£n)即可构成矩阵B={bij}，而置元素cij=c(ui,vj)-f(ui,vj)(1£i,j£n)即可构造矩阵C={cij}。从上面图中的最大整数流所构造的矩阵正是题目中例子里的矩阵B和C。因为流量守恒，我们有：f(s,ui)=12ARi=j=1nf(ui,vj)=j=1nbij=BRi f(vj,t)=12ACj=i=1nf(ui,vj)=i=1nbij=BCj 所以，矩阵B满足要求。因为CRi=ARi-BRi=12ARi，CCj=ACj–BCj=12ACj，矩阵C(推广的Hall氏定理)假设B是二部图G(U,W,E)中U的一个子集，而R(B)W是B的映象集合，即R(B)={wW|$uÎB使(u,w)ÎE}。Hall氏定理说，G(U,W,E)有完全匹配的充要条件是，对任何子集BU，都有|B|£|R(B)|。现在，让我们来推广这个定理。让我们称差值d(B)=|B|-|R(B)|为集合B的映象差，而集合U的最大映象差则定义为max-d(U)=maxB⊆Ud(B)。显然，如果max-d(U)0，那么G有完全匹配。请证明，G的最大匹配的规模为(n–d)当且仅当max-d(U)=d，这里n=|U证明： 因为当max-d(U)=d=0时，命题就是Hall氏定理，当然正确。假设max-d(U)=d>0。我们先证明，如果max-d(U)=d，G的最大匹配的规模为n–d。因为存在集合BU使得|B|-|R(B)|=d，那么在任何匹配M中，B中的顶点最多可与W中|R(B)|个顶点相匹配，而其余|B|-|R(B)|=d个顶点不可能被匹配。因此|M|£n–d。我们只需证明|M|³n–d即可。如书上第11.4节，我们只需证明，图G(U,W,E)对应的单分支网络G’(U,W,E’,s,t)中，从源点s到汇点t的最大流至少是n–d。根据最大流最小割定理，我们只需证明，G’(U,W,E’,s,t)中，任何一个割(S,T)的容量大于等于n–d。设V=UW。(S,T)为G’的任意一个割，SV，T=V–S，sS，tT。假设集合AU是集合U中属于T的顶点，B=U-A是集合U中属于S的顶点。如下图所示，R(B)W是B的映象集合。设|A|=k，因此有BÍS，|B|=n–k。显然，每条从源点s到A中点的边(s,ui)(uiÎA)，都是穿越这个割的边，一共k条。现在让我们检查R(B)中每个点w。假设w与点bÎB相邻，那么如果wÎS，那么边(w,t)穿越这个割，否则边(b,w)穿越这个割。总之，对R(B)中每个顶点w，都有至少一条关联于w的穿越边。因为这些穿越边都不相同，所以这些穿越边的个数至少是|R(B)|。因为d(B)=|B|-|R(B)|£d，我们有|R(B)|³|B|-d=(n–k)–d。加上从源点s到A中点的k条穿越边，割(S,T)的容量至少是c(S,T)(n-k–d)+k=n–d。所以G的最大匹配的规模为n–d。我们再证明，如果G的最大匹配M的规模为n–d，那么有max-d(U)=d。因为任何子集BU中的点最多有d个点在M中未被匹配，所以|B|-|R(B)|d。所以有max-d(U)=maxB⊆Ud(B)d。但是max-d(U)不会小于d。这是因为，如果max-d(U)=d’<d，那么，由(A)部分的证明，G的最大匹配M的规模为n–d’>n–d，产生矛盾。所以必有max-d(U)=假设一个n´n矩阵A={aij}中每个元素是非负整数aij0(1£i,j£n)，但不是双随机矩阵。我们希望增加某些元素的值（正整数）使其成为一个双随机矩阵B。我们要求增加的总数最少。在下面的例子中，增加的总数为3+2+1+(1+2)+(1+3)=13。A=01101请把这个问题建模为一个网络流问题解出。解：首先，我们计算矩阵A中各行和各列的元素和：ARi=j=1naij(i=1,2,…,n)，ACj=i=1naij显然有i=1nARi=j=1n然后，计算最大的行或列的元素和：k=max1≤i≤n这个k值是双随机矩阵B中最小可能的行或列的元素和。我们的目标是双随机矩阵B中每行和每列的元素和为k。为此，我们计算A中各行和各列的元素和需要增加的总数，称为差距：DRi=k-ARi(i=1,2,…,n)，DCj=k-ACj(j=1,2,…,n)。因为有i=1nDRi=nk-i=1nARi和所以有 i=1nDRi现在，构造一个流网络G如下：构造一个加权有向二部图G(U,V,E)，其中U={u1,u2,…,un},代表矩阵A的n行，而V={v1,v2,…,vn}代表矩阵A的n列。另外，边的集合是E={(ui,vj)|DRi>0与DCj>0}，并赋以边(ui,vj)的容量为c(ui,vj)=¥。边(ui,vj)的含义是，如果有整数流f(ui,vj)通过，那么把aij增加一个整数f(ui,vj)，即bij=aij+f(ui,vj)。加上源点s和边(s,ui)并赋以容量c(s,ui)=DRi(i=1,2,…,n)。加上汇点t和边(vj,t)并赋以容量c(vj,t)=DCj(j=1,2,…,n)。让我们以题目中矩阵A为例构造这个流网络。容易看出k=5。每行每列的差距值如下：DR1=3,DR2=2,DR3=1,DR4=3,DR5=4，DC1=4,DC2=4,DC3=0,DC4=3,DC5=2。构造的网络如下图。为清楚起见，边的方向和一些无穷大的容量均略去。容易看出网络G的一个最小割是(S,T)，其中，S={s}，T=UV{t}，它的容量是c(S,T)=i=1nDRi。所以网络G的最大整数流f使所有从s出去的边饱和。因流量守恒，我们有f(s,ui)=c(s,ui)=DRi=j=1nf(ui,vj)(i=1,2,…,n)。因为有bij=aij+f(uij=1nbij=j=1naij=ARi+f(s,ui)=ARi+DRi=k。又因为i=1nDRi=j=1nDCj，所以这个整数流f也使得所有进入汇点t的边饱和。所以，对矩阵i=1nbij=i=1n(aij+f(ui,vj))=i=1n因此，B是一个双随机矩阵。因为增加的总量为i=1nj=1nf(ui,uu2u5u3u4v2v5v4st3/32/21/14/43/34/44/43/32/23/u1v1211213假设一个n´n矩阵A={aij}中每个元素是非负整数aij0(1£i,j£n)。它每行元素之和为ARi=j=1naij(i=1,2,…,n)，每列元素之和为ACj=i=1naij(j=1,2,…,n)，并有max1≤i≤n1≤j≤n{ARi,ACj}=k>0。现在我们希望把某些元素值减少一个整数后得到一个矩阵B={bij}使得B的每个元素仍然是非负整数bij0(1£i,j£n)，但是每行元素之和以及每列元素之和都小于或等于一个比k小的非负整数d(0d<k)，也就是使BRi=j=1nbijd(i=1,2,…,n)，和BCj=i=1nbijd(j=1,2,…,n)。另外，我们要求减少的总数最小。例如，如果A=01102001001001请用网络流的模型来为这个问题设计一个算法。解： 我们先做一些计算。首先，为每一行i(i=1,2,…,n)，计算ERi=max(ARi–d,0)，这里ARi=j=1naij。如果ERi>0，说明第i行的元素和大于d，我们必须把这行中某些元素减少，减少的总量至少是ERi，称为冗余量。然后，为每一列j(j=1,2,…,n)，计算ECj=max(ACj–d,0)，这里ACj=i=1naij。如果ECj>0，说明第j列的元素和大于d，我们必须把这列中某些元素减少，现在，由上面的计算，我们来构造一个流网络G如下：构造一个加权二部图G(U,V,E)，这里U={u1,u2,…,un}代表矩阵A的n行，V={v1,v2,…,vn}代表矩阵A的n列。另外，如果aij>0，则构造边(ui,vj)，并且赋以容量c(ui,vj)=aij。加入源点s以及到每个U中点ui的边(s,ui)(1£i£n)并赋以容量c(s,ui)=ERi。加入汇点t以及从每个V中点vj到t的边(vj,t)(1£i£n)并赋以容量c(vj,t)=ECj。我们用上面矩阵A作例子。先计算ER1=1，ER2=0，ER3=1，ER4=2，ER5=0，EC1=0，EC2=0，EC3=3，EC4=0，EC5=0。下图是对应的流网络。为清楚起见，每条边方向被省略。vv1u1u2u5u3u4v2v5v4st101020000v3223111111111流网络构造好以后，算法如下：Minimum-matrix-reduction(G,d)计算G的从s到t的最大整数流f构造nn矩阵C={cij}使得cij=f(ui,vj)(1£i,j£n)BA–Cfori=1ton BRij=1 ifBRi>d then j1 yBRi-d whiley>0 bijbij–min{y,bij} cijcij+min{y,bij} yy-min{y,bij} jj+1 endwhile endifendforforj=1ton BCji=1 ifBCj>d then i1 yBCj-d whiley>0 bijbij–min{y,bij} cijcij+min{y,bij} yy-min{y,bij} ii+1 endwhile endifendforEnd用上面图中网络为例，它的最大流如下图所示。为清楚起见，该图只显示有流经过的边。其对应的矩阵C显示在图下方。注意，从最大流获得对应的矩阵C后，B=A–C不一定能满要求。这时，要检查B中每一行和每一列，如果发现某行或某列的元素之和仍大于d，则须要在这一行中，或这一列中把一些元素减少使这个和正好为d。算法笫4行和第17行的两个for循环就是为此目的。uu1u3u4st1/11/11/2v31/23/31/11/1A=01102001001001注意，上面例子中的矩阵B的第4行不满足要求。算法笫4行的for循环把B中元素(4,2)减去1，而C中元素(4,2)加1。所以，最后的矩阵C和B如下：A=01102001001001算法的正确性证明如下。首先，算法笫4行和第17行的两个for循环保证得到的矩阵B是满足要求的。我们只需证明减去的总数最小。我们注意到，从行的角度看，我们必须减少的总的冗余量为i=1nERi，而从列的角度看，我们必须减少的总的冗余量为j=1nECj。两者之和为T=i=1nERi+j=1nECj。当我们计算了最大流以后，置cij=f(ui,vj)。所以，当我们从aij减去cij现在考虑任何一个解。在这个解中，有些元素的减少会同时减少行和列的冗余量，有些则只会减少行或列的冗余量但不同时减少两者。假设这个解把元素aij减少一个数时，同时减少了第i行的冗余量和第j列的冗余量。如果这个共同减少的部分是cij，那么我们可以在网络中给边(ui,vj)赋以流量f(ui,vj)=cij。然后，我们给边(s,ui)赋以流量f(s,ui)=j=1ncij，给边(vj,t)赋以流量f(vj,t)=i=1ncij。注意，流量f(s,ui)=j=1ncij不会大于容量c(s,ui)=ERi。这是因为，如果大于c(s,ui)=ERi，则必有元素aij，其减少的共同部分cij不正确，太大了，不会最优。同理，流量f(vj,t)=i=1ncij也不会大于容量c(vj,t)=假设这个解中减少的冗余量的其余部分是y，即这部分只减少行或列的冗余量但不同时减少两者。那么，我们有2x+y=i=1nERi+j=1nECj=T。因此，这个解从矩阵A减少的总数是x+y=T–x。这个值当假设f是网络G(V,E)的一个预流，而h是其高度函数。证明，如果剩余网络Gf中的某一顶点v有高度h(v)n，那么在Gf中，v以及v有路径到达的点都没有路径到t，而且在以后的任何时刻，他们也不会有路径到t。证明： 我们先用反证法证明在剩余图Gf中，顶点v以及v有路径到达的点没有路径到t。假设不是，则有一条从v到t的简单路径，v0,v1,…,vk，其中v=v0，t=vk，并有kn-1。那么根据高度函数的定义有：h(v0)h(v1)+1h(v2)+2…h(vk)+k=0+k=k。因为h(v)n，我们有nh(v0)kn-1。这不可能，所以v没有路径到t。显然，任何一个点u，如果有从v到u的路径，那么，一定没有从u到t的路径，否则就会有从v到t的路径而矛盾。现在用反证法证明，在以后的任何时刻，这些顶点也不会有路径到t。假设不是，则有点u(可以是v本身)，它在当前的Gf中有一条从v到u的简单路径，v0,v1,…,vk，其中v=v0，u=vk，而在以后某个时刻的剩余图Gf*中有一条从u到t的简单路径，u0,u1,…,uk*，其中u=u0，t=uk*。我们可假定在路径u0,u1,…,uk*中，除u=u0外，不含v0,v1,…,vk中任何一个点。否则的话，可以选取u0,u1,…,uk*中最右边一个出现在序列v0,v1,…,vk中的点取代u。根据高度函数的定义，在Gf*中有：h*(u)h*(u1)+1h*(u2)+2…h*(uk*)+k*=0+k*=k*。这里，h*表示在剩余图Gf*中的高度函数。而在原先Gf中有：nh(v0)h(v1)+1h(v2)+2…h(vk)+k=h(u)+k。因为顶点u的高度不减，h(u)≤h*(u)≤k*，所以有n≤k*+k。因为上面两个序列，v0,v1,…,vk，和u0,u1,…,uk*中一共有k+k*+1个不同顶点，那么网络中至少有n+1个顶点，这不可能。(a)在一个nn的棋盘上，我们用(i,j)表示在第i行，第j列的格子(1i,jn)。这些格子中，有一些格子不可用，其余可用。我们用B(i,j)=0表示格子(i,j)不可用，B(i,j)=1表示可用。我们的问题是，在可用的格子中找出最大的一组不同行和不同列的格子。也就是说，每一行最多可以选一个可用格子，每一列也最多可以选一个可用格子。请用下面图示的88棋盘的例子说明如何把这个问题建模为一个二部图的匹配问题。(b)为下面图示的88棋盘的例子找出最大的一组不同行和不同列的可用格子。11234567821348657阴影的格子表示不可用B(i,j)=0解： 我们构造一个二部图G(U,V,E)如下：U={u1,u2,…,un}，其中，ui代表棋盘的第i行(1≤i≤n)。V={v1,v2,…,vn}，其中，vj代表棋盘的第j列(1≤j≤n)。如果B(i,j)=1，格子(i,j)可用，则构造边(ui,vj)。也就是E={(ui,vj)|B(i,j)=1,1≤i,j≤n}。下面图(a)显示了由题中例子所构造的二部图。显然，二部图G(U,V,E)的最大匹配对应一组最大的不同行和不同列的可用格子，也就给出了本题的解。uu1u2u3u4u5v1v2v3v4v5u6u7u8v6v7v8(a)(b)下图(b)显示了上面二部图(a)的一个最大匹配。下图(c)显示的是对应于图(b)中最大匹配的一组最大的不同行和不同列的可用格子uu1

u2

u3u4u5v1

v2

v3v4v5u6u7u8v6v7v8(b)11234567821348657阴影的格子表示不可用B(i,j)=0黑色的格子表示选取的可用格子(c)假设图G(L,R,E)是一个二部图，其中LR是顶点的集合。E中任何一条边关联L中的一个点和R中的一个点。另外，集合L中的任何一个点u有度数d(u)≥5，而集合R中的任何一个点v有度数d(v)5。证明图G有完全匹配。证明： 我们证明这个二部图满足Hall氏定理，即集合L中的任何一个子集SL，都有|S|≤|R(S)|。让我们定义E’为集合S和R(S)之间的所有边的集合，再定义E’’为集合L和R(S)之间的所有边的集合。因为SL，所以有E’E’’，|E’||E’’|。下面的图显示了集合S和R(S)之间的关系。因为集合L中的任何一个点u有度数d(u)≥5，所以有5|S||E’|。又因为集合R(S)中的任何一个点v有度数d(v)5，所以有|E’’|5|R(S)|。把以上的不等式连起来，我们有：5|S||E’||E’’|5|R(S)|，也就是|S|≤|R(S)|。 SRSR(S)LR边的个数|E’|满足E’|≥5|S|边的个数|E’’|满足|E’||E’’|≤5|R(S)|假设有n个研究生，g1,g2,…,gn，参加不同项目的物理实验的竞赛，但每个研究生必须有两个本科生做助手，组成一个小组。又假设有2n个本科生可选，他们是u1,u2,…,u2n。但是，因为项目的不同，不是每个本科生都合格参加所有项目的竞赛。也就是说，每个本科生只能合格参加某几个项目的物理实验。换句话说，每个研究生只能从合格的本科生中选取两个与之组成一个小组。另外，因为所有项目的竞赛是在同一个时间进行，每个人只能参加一个项目的竞赛。我们的目标是把这n个研究生和2n个本科生组成正好n个竞赛小组。请用下面的例子來说明，怎样把这个问题建模为一个网络流的问题以确定是否可能。如果可能，输出这n个竞赛小组的组成。5个研究生是: g1,g2,g3,g4,g510个本科生是: u1,u2,u3,u4,u5,u6,u7,u8,u9,u10 可以与每个研究生配合的本科生集合如下：可与g1配合的本科生集合是:{u1,u3,u5,u9}可与g2配合的本科生集合是:{u1,u7,u8}可与g3配合的本科生集合是:{u2,u4,u5,u6,u10}可与g4配合的本科生集合是:{u3,u6,u8}可与g5配合的本科生集合是:{u2,u4,u5,u10}。解: 我们构造一个流网络如下：构造有向二部图G(L,R,E)，其中L={g1,g2,…,gn}代表n个研究生，R={u1,u2,…,u2n}代表2n个本科生。如果本科生uj可以与研究生gi配合，则在集合E中加上一条有向边(gi,uj)，容量为1。在图中加上一个源点s。从源点s到每一个L中点gi(1in)加上一条有向边(s,gi)，容量为2。在图中加上一个汇点t。从每一个R中点uj(1j2n)加上一条到汇点t的有向边(uj,t)，容量为1。下图显示的是由题中例子所构造的流网络。为清晰起见，容量是1的边不标注容量。uu10g1g2g3g4g5u1u2u3u4u5u6u7u8u9ts22222构造好流网络之后，计算它的最大整数流f。如果|f|=2n，那么，问题有解。这时，经过顶点gi(1in)的流必定是2。因为是整数流，必定有两条边，(gi,uj)和(gi,uk)，使得f(gi,uj)=1和f(gi,uk)=1(1j,k2n)，jk。我们可以把本科生uj和uk配给研究生gi。因为|f|=2n，经过顶点uj的流必定是1(1j2n)，所以，存在一个顶点gi(1in)，使得，f(gi,uj)=1和f(uj,t)=1。所以，每个本科生会配给正好1个研究生。下图显示的是对应题目中流网络的最大流以及问题的解。1/11/11/11/11/11/11/1u1

u10g1

g2

g3g4g5u2

u3u4u5u6u7u8u9ts2/22/22/22/22/21/11/11/11/11/11/11/11/11/11/11/11/11/11/11/11/1这5个竞赛小组是：{g1,u1,u9}{g2,u7,u8}{g3,u2,u4}{g4,u3,u6}{g5,u5,u10}给定一个图G(V,E)，如果V的子集V’V中任意两点之间没有边，那么V’称为是一个独立集。最大独立集问题就是要找出图G的一个最大的独立集，即含有最多顶点的独立集。如果G是一个树T，那么，这个最大独立集问题可以在O(n)时间内解决(见第8章习题19)。现在，假设G(V,E)是一个二部图，请设计一个O(n2.5)的算法为G找出一个最大独立集并证明其正确性。这里，n=|V|。解： 设顶点集合的两部分是L和R，V=LR，LR=，G(V,E)=G(L,R，E)算法的伪码如下。Maximum-Independent-Set-Bipartite-Graph(G(L,R，E),I) //属出最大的独立集I计算由G(L,R，E)构造的网络的最大流f，并得到L和R之间的最大匹配ML1{u|uL并且有边(u,v)M}R1{v|vR并且有边(u,v)M}L2L-L1R2R-R1L3{u|uL1并且u在二部图G中有路径可达L2中某一点}R3{v|vR1并且v在二部图G中有路径可达L2中某一点}L4{u|uL1并且u在二部图G中有路径可达R2中某