求x34的检验数z34 -c34 闭回路法
b2=-2 c12=6 b1=5 1 c13=3 3 c35=2 5 b5=-6 2 c34=4 b4=3 4 c46=1 b6=-5 6 c56=4
b3=5 z34 -c34 =(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34进基
南京工业大学经济与管理学院 潘郁教授
2013-9-2
8.2 最小树问题



无圈的连通无向图称之为树 赋权无向图G=（V，E）上连接所有节点的各 边其权总和为最小的部分树称为最小支撑树 （最小树） 性质1：加边成圈。如果在一棵树中，两个不 相邻节点之间加上一条边，就会出现一个且仅 一个圈。 性质2：破圈成树。如果把上述圈中另一任意 边去掉，则可得到另一棵树。
2013-9-2
习题：p312－8.4，求最大流

给出任意可行流 找到一条增广链 调整可行流 注：’＝1，#＝1，$＝2，*=1 v2 v1 （1,1）
（3,2）’ v 3 （4,3）’ 2 vt vs （3,2）# 2 (0,+∞) （5,3）#* （8,3）#$* （10,4）$* （3,2）* , ） （4,3）’ （7,6）’ （
南京工业大学经济与管理学院 潘郁教授
2013-9-2
图的基本概念(续)

由点和边组成的图叫做无向图，记为G=（V，E） 由点和弧组成的图叫做有向图，记为D=（V，A） 例1. e1 v3 a8 v5 v1 e2 v2 v7 a1 a10 a4 a6 a9 e 3 e 4 a11 e5 v1 a3 v6 a2 a7 v4 e6 v3 v2 a5 v4
1600
4
1600
5
1600
6
2350 3100 4550
2013-9-2
南京工业大学经济与管理学院 潘郁教授
习题8-1

求最小树
2013-9-2
南京工业大学经济与管理学院 潘郁教授
习题8-2

求A到各点的最短路
2013-9-2
南京工业大学经济与管理学院 潘郁教授
8.4 最大流问题

引例：如下输水网络，南水北调工程， 从vs到vt送水，弧旁数字前者为管道容 量，后者为现行流量，如何调整输水最 多？ v2 v4 (4,3)
南京工业大学经济与管理学院 潘郁教授
2013-9-2
解水网最大流问题
. V2 (-v1,1) (3,3) vs (0, +∞) (5,1) V1 (vs,4)
2013-9-2 南京工业大学经济与管理学院 潘郁教授
(4,3)
V4 (v2,1) (5,3)
(1,1)
(1,1)
(3,0) (2,1)
Vt (v3,1)
变量x34进基，确定离基变量
b2=-2 x12=2 b1=5 1 x13=3 3 x35=8 5 b5=-6 2 x34=0 b4=3 4 x46=3 b6=-5 6 x56=2
b3=5 min{x56,x35}=min{2,8}=2, x56离基，调整流量，进行基变换
确定非基变量x24和x56
南京工业大学经济与管理学院 潘郁教授
8.1 图的基本概念


图是由点和线构成的。 点的集合V表示，V={vi} 不带箭头的连线叫做边(edge)，边的集 合记为E= { ej } ，一条边可以用两点 [ vi,vj ]表示,ej= [ vi,vj ]. 带箭头的连线叫做弧(arc),弧的集合记为 A，A= { ak },一条弧也是用两点表示， ak= [ vi,vj ],弧有方向：vi为始点，vj为终 点
1
2 4 3
■圈(Cycle)
起点和终点重合的链称为圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各条边方向不一定相同
1
2 4 3
■连通图
任意两个节点之间至少有一条 链的图称为连通图
■树(Tree)
无圈的连通图称为树 树中只与一条边关联的节点称 为悬挂节点
1
2
3 5 4
树的性质
南京工业大学经济与管理学院 潘郁教授
2013-9-2
破圈法

从圈上去掉一条最大权的边(无圈)
v2 6 v1 1 3 2 v3 2 v4 10 v6 1 6 v5 6 4 4 3 v8 4 v7
2013-9-2
南京工业大学经济与管理学院 潘郁教授
加边法

由短到长（最小）
v2 6 v1 1 3 2 v3 2 v4 10 v6 1 6 v5 6 4 4 3 v8 4 v7
2013-9-2
南京工业大学经济与管理学院 潘郁教授
(vs,3)
v4
（4,2）$
v5
第五章 网络优化
网络的基本概念 网络最小费用流问题 网络最大流问题 最短路径问题
网络的基本概念
■网络由节点和边组成
■
2 1 3 4
节点与（有向）边
每一条边和两个节点关联，一条 边可以用两个节点的标号表示 （i，j）
e7 无向图：点集、边集
2013-9-2点集、弧集
图的基本概念(续)


以点u为端点的边的条数，叫做点u的次 次为1的点叫做悬挂点；次为0的点叫做 孤立点；次为奇数则称奇点；次为偶数 则称偶点。 点弧交替序列称为链；闭合的链称为圈 首尾相接的链称为路；闭合的路称回路 任意两点之间都有边相连，称为连通图
第八章 图论及其应用

引论
哥尼斯堡七桥问题
A C B D
简捷表示事物之间的 本质联系，归纳事物 之间的一般规律
A D B
C
2013-9-2
南京工业大学经济与管理学院 潘郁教授
引论 图的用处
A、B、C、D、E 五支球队进行循环赛

A
总公司 C
某公司的 组织机构设置图 工厂或
分公司 办事处
B
D
E
2013-9-2
b2=-2 x12=2 b1=5 1 x13=3 3 b3=5 x35=6 5 b5=-6 2 x34=2 b4=3 4 x46=5 b6=-5 6
计算x24和x56的检验数z24 -c24 、z56-c56
b2=-2 c12=6 b1=5 1 c13=3 3 b3=5 c35=2 5 b5=-6 2 c24=5 b4=3 4 c46=1 b6=-5 6 c56=4
南京工业大学经济与管理学院 潘郁教授
2013-9-2
求最大流的方法


方法很简单：首先找到一条增广链，沿 此进行最大可能调整，再找增广链，再 调整，直到没有增广链。 寻找增广链的标号法：先给vs标号（0， +∞）,而后依次审查各条弧（vi,vj）：对 前向弧，饱和否？不饱和，给vj点标号 （vi，l(vj));对后向弧，可否减少？可， 给vj标号（-vi, l(vj) ）,直到给vt标上号， 就得到了增广链。
1 2 使用年数 年末的残值（万 1000 750 元） 年度操作费用（万元） 100 500
2013-9-2
3 500 1000
4 250 1200
5 0 1300
南京工业大学经济与管理学院 潘郁教授
例：设备更新问题
4550 3100 1850 2350 3600
6100
1
1100
2
1100
3
1850
v2 6 v1 1 3 2 v3 2 v4 10 v6 1 6 v5 6 4 10 4 3 v8 4 v7
2013-9-2
南京工业大学经济与管理学院 潘郁教授
破圈法（适用于无回路的有向网络）

从指定始点开始，逐步找圈、破圈直至 指定终点为止。（站在终点的立场上， 破圈）
v2 2 v3 2 v4 10 v6 1 6 v5 6 v1 1 3 6 4 4 3 v8 4 v7
(3,3) vs (5,1) v1 (2,2) v3 (1,1) (1,1) (3,0) (5,3)
vt
(2,1)
2013-9-2
南京工业大学经济与管理学院 潘郁教授
最大流问题的相关概念



网络：给定了弧的容量C（vi,vj）的有向图D= （V，A，C）叫做一个网络。 可行流：各点流入量=流出量，且vs的流出量 =vt的流入量，这样的流称之为可行流 截集：分离始点vs和终点vt的弧的集合，叫做 截集 截量：截集的容量叫做截量 增广链：一条从始点到终点的链，前向弧上可 增加，后向弧上可减少，则称此链为增广链
i j
2
■路径（Path）
前后相继并且方向相同的边序列
1 3
4
P={(1,2),(2,3),(3,4)}
■链（Chain）
前后相继并且方向不一定相同的边 序列称为链 C={(1,2),(3,2),(3,4)}
1
2 4 3
■回路（Circuit）
起点和终点重合的路径称为回路 μ={(1,2),(2,4),(4,1)} 回路中各条边方向相同
(2,2) V3 (-v2,1)
此题最大流图

沿增广链进行调整，前向弧增加l(vj)，后 向弧减少l(vj)
V2 (3,3) vs (0,+∞) (5,2) (1,0) (1,0) (3,0) (2,2) (2,2) V1南京工业大学经济与管理学院 V3 潘郁教授 (vs,3) (4,3) V4 (5,3) Vt
2013-9-2
南京工业大学经济与管理学院 潘郁教授
树逐步生长法

最短+无圈（连通）
v2 6 v1 1 3 2 v3 2 v4 10 v6 1 6 v5 6 4 4 3 v8 4 v7