最小费用与最大流问题 .ppt

定义6.6.1 设 G为连通图，若存在一条回路，经过每条 边一次且仅一次，称这条回路为欧拉回路。具有欧拉 回路的图称为欧拉图。 定理6.6.1 连通图G是欧拉图当且仅当 G中的点全为偶 点。 证明： 必要性。 设G为欧拉图， 故存在一条回路经过G中所有的边， 这条回路上， 边不重复但顶点可能重复。 对任一点 只要它在回路中出现一次， 必关联两条边。 故 可以 在回路中重复出现， 但点的次必为偶数。 充分性。 设G中的点全为偶点， 如从 出发， 经关联边到 而 为偶点， 故必经关联边到另一点 如此下去， 每条边仅取一次。 由于G的点数有限， 所以沿这条路 必可走回 得到一条回路 若 经过G中所有边， 则 即为欧拉回路。 否 则从G中去掉 后得到子图 则 中每个顶点 的次数仍为偶数， 因G为连通图， 故 与 至少有 一个顶点与 重合， 在 中从 出发， 重复 的 方法， 得到回路 把 和 组合在一起， 如果恰 为G， 则得到欧拉回路。 否则按构造 的方法构造 依此类推。 由于G中边数有限， 故最终可得一条过G中所有 边的回路， 即为欧拉回路。 证毕。 推论6.6.1 无向连通图G存在欧拉链当且仅当 G中恰 有两个奇点。 证明： 必要性。 无向连通图G存在欧拉链， 则G中必然有一个从 起点u出发， 通过其他中间点， 且过每条边一次且仅一 次， 到达终点v, 因为图G中间点都只能是过路的顶点， 离开该点的次数等于到达该点的次数。 因为要求不 能有重复的边， 故而每次到达和离去都选用不同的边。 所以中间顶点必然与偶数条边相关联， 即图G中间点 必然是偶顶点，只有起点 u和终点 v才为奇点。 充分性。 设G中恰有两个奇点 u，v， 在 G中增加一个新边 (u,v) （若u，v之间本来有边，则该边为其重复边）， 从而得新图 所以 点全为偶点， 由定理6.6.1知 存在一条欧拉回路 此时去掉 中的新增加的新边 (u,v), 即得G中的一条连接u，v的欧拉链。 证毕。 注1： 上述定理和推论为我们提供了识别一个图能否 一笔画出的较为简单的办法。 如七桥问题， 有四个奇点， 所以不是欧拉图， 故不 不能一笔画出。 即不可能一次连续走过这七座 桥回到原出发点，且每座桥只走一次。 一般地， 若连通多重图G中全为偶点， 则该图能一 笔画成， 且第一个顶点和最后一个顶点相同； 若连通多 重图G有两个奇顶点， 则该图也能一笔画成， 但第一个 点与最后一个点不同。 §6.5 最小费用最大流问题 §6.5.1 最小费用最大流问题的数学模型 设网络D=(V,A,W), 每条弧 除了容量 以 外， 还给出单位流量的费用 （简记为 ）。 这样，D就成为一个带费用的网络，记为D=(V,A,W,C), 其中,C称为费用函数。 设X为D上的一个可行流，称 （6.5.1） 为可行流X的费用。 最小费用最大流问题，即要求一个最大流X，使总 运输费用 （6.5.2） 达到最小值， 则有最小费用最大流问题的数学模型 （6.5.3） §6.5.2 最小费用最大流问题的算法 寻求最大流的方法 最小 费用 最小费用最大流 从某个可行流出发， 找到关于这个可行流 的一条增广链，沿着 该增广链调整X，对 新的可行流试图寻求 关于它的增广链，如 此反复直至最大流 设想： 当沿着一条关于可行流X的增广链 以 调整X， 得到新的可行流 且有 这里第三个等式只是因为对 之外的 来说 即费用均一样。 记 称 是沿增广链 当可行流增加单位流值时费 用的增量， 简称为增广链 的单位费用增量。 可以证明， 若X是流量为f(X)的所有可行流中费 用最小者， 而 是关于X的所有增广链中费用最小的 增广链， 则沿 去调整X， 得到的可行流 就是流量 为 的所有可行流中的最小费用流， 这样， 当 是最大流时， 即为最小费用最大流。 注意到 故X=0必是流量为 0的最小费用 流。 这样， 总可以从X=0开始。 一般地， 若X是流量 f(X)的最小费用流， 为了寻求关于X的最小费用增 广链， 构造一个赋权有向图D(X)， 它的顶点是原网 络D的顶点， 而把D中的每一条弧 变成两个 相反方向的弧 和 定义D(X) 中弧的 权 在D(X)中长度为 的弧可以略去。 故在网络D中寻找关于 X的最小费用增广链就 等价于在赋权有向图D(X)中， 寻找从 到 的最短 路。