30.网络的最大流：网络中从发点到收点之间允许通过的最大流量。 31.流：加在网络各条弧上的一组负载量。记32.零流：若网络上所有的
fij
fij=0，这个流称为零流。
33.割：指将容量网络中的发点和收点分割开，并使s?t的流中断的一组弧的集合。 34．割的容量：是组成它的集合中的各弧的容量之和，用c(V,V)表示。
35.增广链：如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 s→t 的弧（称前向弧，记作μ+），存在f < c (非饱和)；所有指向为 t →s 的弧（称后向弧，记为μ-），存在f > 0(非零)，这样的链称增广链。 36.悬挂点：次为1的点为悬挂点。
37.悬挂边：与悬挂点关联的边称为悬挂边。
四、简答 2.
2. 一些重要的网络不能按数的结构设计，这是为什么。
答：由于数图是无圈的连通图，即数图的任意两个点之间有一条且仅有一条唯一通路。因此数图是最脆弱的连通图，只要从树图中取走任一条边，图就不连通，因此一些重要的网络不能按数的结构设计。
3.避圈法一在求最小部分树的步骤：
1. 从图中任选一点 vi ，让 vi ∈V ，图中其余点均包含在V 中；
2. 从 V 与 V 的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为[vi , vj]将其加粗，标记为最小部分树中的边。 3. 令 V∪vj→V， - vj→ V ；
4.重复2、3两步，一直到图中所有点均包含在 V 中
4.破圈法一求最小部分树的步骤
1. 从图 N 中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图 N1。 2. 从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图； 3. 重复第 2 步，直到图中不再含有回路为止。
5Dijkstra 算法的基本思路 答：如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路径，则 v1→ v2→ v3 一定是 v1→ v3 的最短路径。 v2→ v3→ v4 一定是 v2→ v4 的最短路径。
????6可行流需要满足的条件
(1) 容量限制条件: 对所有弧有0?f( (2) 中间点平衡条件：
7.求最小费用流步骤
第一步：从零流
v,v)?c(v,v)
ijijij?f(v,v)??f(v,v)?0,(i?s,t)
ijf0开始，
kf0是可行流，也是相应的流量为零时费用最小的；
第二步：对可行流1.对0<用
f构造加权网络W（
fk），方法是
fbij <
cij的当其为正向弧时，通过单位流的费用为
bij，为反向弧时，相应费
bji=-ijij，故在i和j点间分别给出弧（i，j）和（j，i），其权数分别为
bij和-
bji
2.对（
fk=
cij的弧（i，j），因该弧流量已饱和，在增广链中只能作为反向弧，故在W
f）中只画出弧（i，j），其权数值为-ijbij
3.对
f=0的弧（i，j），在增广链中该弧只能为正向弧，故在W（
fk）中只给出弧
（i，j）其权数值为
bij
第三步 在加权网络W（
fk）中，寻找费用最小的增广链，也即求从s→t 的最短，并
将该增广链上流量调理至允许的最大值，得到一个新的流量第四步 重复第2，3两步，一直到在网络W（
fk?1 (>
fk)
fk?m 找不到增广链（也即找不到最短
路）时，
fk?m即为要寻找的最小费用最大流
8.树的性质说明什么？
1）树是无圈连通图中边数最多的，树中只要任意再加一条边，必出现圈。
2）树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。 9.避圈法二在求最小部分树的步骤：
1）在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；
2）在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边； 3）重复进行第二步，直到找到第 n-1 条边为止。（因为有 n 个顶点的树中一定有 n-1 条边）
10. 破圈法二求最小部分树的步骤
1）从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否
则不再考虑此边；
2）重复上述步骤，直到剩余边数为 n-1 为止。 11.最小部分树的求解注意事项
1）一个图的最小部分树不唯一，如题中用几种解法得到的结果都是相同的，是特殊情况； 2）不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小 12. Dijkstra 算法步骤：
1）对起始点s，因 Lss?0，将0标注在s旁的小方框内，表示s点已标号；
2）从点s出发，找出与s相邻的点中距离最小的一个，设为r，将Lsr?Lss?dsr的值标注在r旁的小方框内，表明点r也已标号；
3）从已标号的点出发，找出与这些点相邻的所有未标号点p，若有
Lsp?min?Lss?dsp,Lsr?drp?，则对p点标号，并将Lsp的值标注在p点旁的小方框内；
4）重复第3步，直到t点得到标号为止。 13. 求网络最大流的标号算法的步骤 第一步：首先给发点s标号?0,?(s)?。 第二步：列出与已标号点相邻的所有未标号点
1)考虑从标号点i出发的弧?i,j?，如果有fij?cij，不给点j标号；若fij?cij，则对j 标号，记为?i,?(j)?，其中?(j)?min??(i),(cij?fij)?；
2)考虑所有指向标号点i的弧?h,i?，如果有fhi?0，对h不标号， 若fhi?0，则对h点标号，记为?i,?(h)?，其中?(h)?min??(i),fhi?；
3)如果某未标号点k有两个以上相邻的标号点，可按(1),(2)中所述规则分别计算出?(k)的值，并取其中的最大的一个标记。 第三步：重复第二步 第四步：修改流量。 设原图中可行流为f，令
?f??(t),对增广链上所有前向弧?f???f??(t),对增广链上所有后向弧
?f,所有非增广链上的弧?这样得到网络上的一个新的可行流f?。
第五步：抹掉图上所有标号，重复第一到第四步。 14.求最小费用流的步骤：
第一步：从零流f0开始，f0是可行流，也是相应的流量为零时费用最小的；
第二步：对可行流fk构造加权网络W(fk)，方法是
1)对0?fij?cij的当其为正向弧时，通过单位流的费用为bij，为反向弧时，相应费用
bji??bij，故在i和j点间分别给出弧?i,j?和?j,i?，其权数分别为bij和?bji；
2)对fij?cij的弧?i,j?，因该弧流量已饱和，在增广链中只能作为反向弧，故在W(fk)中只画出弧?i,j?，其权数值为?bij；
3)对fij?0的弧?i,j?，在增广链中该弧只能为正向弧，故在W(fk)中只给出弧?i,j?其权数值为bij。
第三步 在加权网络W(fk)中，寻找费用最小的增广链，也即求从s?t的最短路，并将该增广链上流量调理至允许的最大值，得到一个新的流量fk?1?fk。
第四步 重复第2，3两步，一直到在网络W(fk?m)找不到增广链（也即找不到最短路）时，
fk?m即为要寻找的最小费用最大流。
15.标号法求最大流时，出现的两个结果是什么。
1)标号过程中断，t得不到标号，说明该网络中不存在增广链，给定流量即为最大流量。记已标号点集为V，未标号点集为V，V,V为网络的最小割；
2)t得到标号，这时可用反向追踪法在网络中找到一条从s?t的有标号点以及相应的弧连接而成的增长链。
16.树的性质
性质1. 任何树中必存在次为1 的点。
性质2. 具有 n 个顶点的树恰有（n-1）条边。 性质3. 任何具有n 个点、(n - 1)条边连通图是树。 17.最小部分树的定理及推论
定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最近的，则边 [ i , j ] 一定包含在该图的最小部分树中。
推论. 把图的所有点分成 V 和 V 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。
五、计算
???1.求最小部分树（第一题用破圈法，第二题用避圈法）
（1） （7分） （2）（7分）
6725144341375213
45536843754312
答
（a）最小部分数为15 （7分）
233151
（b）最小部分树为18 （7分）
21333132
2. 已知有6个村子，相互间道路的距离如图所示，拟合建一所小学，已知A处有学生50人，B处40人，C 处有60人，D处有20人，E处有70人，F处有90人，问小学应建在哪一个村子，使学生上学最方便（走的总路程最短）
B2A7C4186D61F3E3
3. 1. 十名研究生参加六门课程的考试，由于选修的课程不同，考试门数也不一样，如下表给出了每个研究生应参加考试的课程（打▲号的），规定考试应在三天内结束，每天上下午各安排一门，研究生们提出希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考