?0913?????104?7??W?2?0?1???0????5027????62805???7?2?20???0913?????10247??W??211051???1???5027????62805???71621020???091316????10247??W?211051???2????5027???762805???71621020???09132????10243??W??211051???3?7165027???462805???4132720???0913210???1024311?W?21105112??4??7165027???462705???4132720???081327???102438?W??270516??5?684027???462705???482720??
?023400???103050?R?100050??0??003056???023406???103450???023400???101150?R?110150??1??003056???023406???113150???023420???101150?R?110150??2??003056???223406???113150???023430???101130?R??110150??3?333056???323306???313350???023434???101134?R?110154??4??333056???323306???313350???053435???101135?R?150155??5??555056???323306???353350??第 21 页 共 33 页
(3)MaxWij?(8,8,7,8,7,8) 中心为V3或V5
5j?Wj5ij?(21,18,21,27,24,23) 中心为V2
补充习题：试计算完全图Kn的主树的数目。
解：设A为Kn的关联阵，那么主树的数目为：
n?1n?1N?dctA?AT?dct?1?1???1?110???n?1?dct???1??10n?1n?1n?11???11????1n1n00n0n?11n?2?dct??dct?n??n???n?0??0?1n0n证毕。
5.1求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。 解：
本题可以利用M算法，也可以使用最大流－
最小割简单计算可知：
X??vs,v3,v4?
X??v1,v2,vt?
CX,X?3?5?1?3?12
第 22 页 共 33 页
??可知：最大流为12，可以安排为fs1 = 3,，fs2 =5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。
5. 2试移动上图中的一条边，保持其容量不变，是否能增大fst？如果可以，求此时的最大值，但若所有转接端v1v2v3和v4的转接容量限制在4，则情况将如何？ 解：
依然按照最大流－最小割定理，若
22v14v1'6能依一边从X找到X内部至割
3v244v2'v3'Vt(X,X)中，自然可以增大流量，可以
Vs52v3将e34移去，改为：e41 或者e42均可，使总流量增至12＋2＝14。
64132v44v4'当vi(i = 1,...4)的转接容量限制到4
时，等效图为右图，对于3.11中的流量分配，在本题限制下，若将fs2由5改为4即得到一个流量为11的可行流。
但若X?vS,v3,v3v4,v4,v2， X?v1,v1,v2,vt 则C(X,X)?1?3?4?3?11，换句话说就是11已是最大流。
*?''?*?''?**第 23 页 共 33 页
5.3图5-12中的Vs和Vt间要求有总流量fst＝6，求最佳流量分配，图中边旁的两个数字前者为容量，后者为费用。 解：
本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs
出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。
6,3再考虑V0，进入V0的两条路径中优先满
5,7 3,2足费用为3的路径，得：图2，很容易得
Vt2 ,3Vs 3,2 1,124,到最后一个流量为fst=6的图3，边上的 数字为流量安排。总的费用为
3,4图1
L?3?2?3?2?1?3?2?4?1?1?2?3?4?2?2?7?52
易用负价环验证图4的流量分配为最佳流量分配。
12Vs 44 Vt3Vs 1VtVs34图 22图 3 2图 44 32 22 Vt 2
第 24 页 共 33 页
第 25 页 共 33 页