V 1 1 2 4 4 y4 y. 图8.13 E’={(s,x)x∈Vn3U{(y,t)yeV23U{(x2y)xeV12y∈ V2,(x2y)∈E} 对任意xeV1,y∈V2,令c3x=c=1,对任意弧 (x,y),x∈V12yev2,令c3y=1,这个网络的发点是 收点是to三、二分图中的匹配 1.求最大匹配的算法 利用标号法求网络最大流。 对于给定二分图G(V1 ,V2 )，构造相应的网络 N(G)。 设G(V1 ,V2 )是二分图, 构造一个网络N(V',E',C) 又记为 N(G), 它 是 一 个 带 权 有向 图 , 其 中 V'=V1∪V2∪{s,t}, E'={(s,x)|xV1 }∪{(y,t)|yV2 }∪{(x,y)|xV1 ,y V2 , (x,y)E}。 对 任 意 xV1 , yV2 , 令 csx=cyt =1, 对 任 意 弧 (x,y),xV1 ,y V2 , 令cxy =1, 这个网络的发点是s, 收点是t