会计学第八章图与网络分析网络(wǎngluò)最大流问题问题(wèntí)的提出容量(róngliàng)发点（源）收点（汇）中间点容量(róngliàng)网络流网络(wǎngluò)最大流问题设是网络D=（V，A，C）的一个(yīɡè)可行流设是网络(wǎngluò)D=（V，A，C）的一个可行流链及可增广(zēnɡɡuǎnɡ)链割集和割集的容量(róngliàng)考虑(kǎolǜ)KK的不同画法基本(jīběn)定理(可行流与割集的关系)这样就得到(dédào)了一个寻求最大流的方法(算法思想)：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到(dédào)一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到(dédào)了最大流。同理，给标号调整(tiáozhěng)量为可令调整(tiáozhěng)量为f)下面检查与相邻接且未标号的点，同理，调整量：2）调整流量：从到所画出的红线即为可增广链。沿该可增广链，从倒推，标“＋”号的在实际流量上加上该调整量，标“－”符号的在实际流量上减去该调整量。完成调整过程。/当标到时，与，相邻接的点，，都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。网络从发点到收点的各通路中，由容量决定(juédìng)其通过能力，最小割则是这此路中的咽喉部分，或者叫瓶颈，其容量最小，它决定(juédìng)了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部份的通过能力。下图中，A,B,C,D,E,F分别表示陆地和岛屿，①，②，…，表示桥梁及其编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。在图中任给可行流，用标号法寻找(xúnzhǎo)网络最大流！设容量网络G有若干发点，若干个点，可以(kěyǐ)添加两个新点vs，vt，用容量为∞的有向边分别连结vs与发点，收点与vt，得到新的网络G'，G'为只有一个发点，一个收点的网络，求解G'的最大流问题即可得到G的解。设有5位待业者，5项工作，他们各自能胜任工作的情况如图所示，要求设计(shèjì)一个就业方案，使尽量多的人能就业。图中最大匹配问题(wèntí)，可以转化为最大流问题(wèntí)求解。在图中增加两个新点分别作为发点，收点。并用有向边把它们与原图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果上的流量为1，就让作工作，此即为最大匹配方案。第一次标号(biāohào)。第二次标号(biāohào)。第三次标号(biāohào)。调整(tiáozhěng)。第四次标号(biāohào)。调整(tiáozhěng)第五次标号(biāohào)。标号过程已无法再继续。流量(liúliàng)为1的画红线。工人(gōngrén)