A3 最大零售量 14 9 √ 8 √ 10 12

9.22某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从Ai仓库到Bj市场的运输能力如表9-6所示（表中“—”表示无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？

表9-6

市仓 库 场 B1 30 — 20 20 B2 10 — 10 20 B3 — 10 40 60 B4 40 50 5 20 存货量 A1 A2 A3 最大零售量 20 20 100

9.23 某单位招收懂俄、英、日、德、法文的翻译各一人，现有五人应聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这五个人是否都能被应聘？最多几个得到招聘，招聘后每人从事哪一方面的翻译工作？

9.24 用Floyd算法分别求图9-32所图中任意两点间的最短路径及长度。

v11275261142-58v4v1v3-252-2

v4v24-4v3 (a) (b)

图9-32

9.25 某公司在六个城市c1,c2,?,c6中有分公司，从ci到cj的直接航程票价如下述矩阵中的(i,j)位置上（?表示无直接航路）。请你设计一张任意两城市间票价最便宜的路线表。

?0?50?????40?25??10

402510?01520?25??150102020??

201001025??2010055??25?25550?33

50?§9.4习题解答

9.1 解：(1)错。图论中的图只反映了点边之间的关联关系，而与点的位置、边的形状和大小无关。

(2)对。在树图中，若删除其中任一边，则不连通，因此树图是G中边数最少的连通子图。

(3)错。首先，由于v1至各点都有最短路，此子图为连通的；其次，由于最短路的唯一性，此子图无圈，即为支撑树。但此子图不一定是最小支撑树。例如：

v2(v3,5)v1(?,0)v3(v1,1)v5(v6,9)v7(v5,13)v4(v3,3)v6(v3,6)v8(v6,14)

(a)

v244v2v11v32v5334v7v11v32v5334v768v4v6v8

v4v6v8

(b) (c)

图9-33

在图9-33(a)中，用Dijkstra标号法可求得v1至其余各点的最短路，可得支撑树如图9-33 (b)所示，权数和为25，而在图(a)中用破圈法可求得最小支撑树如图9-33 (c)所示，权数和为23。所以，图9-33 (b)不是最小支撑树。

(4)对。

9.2证明：由于G为一个简单图，因此G中不存在平行边。如果G中存在一

2个孤立点，则其余n?1个顶点之间最多有Cn?1?(n?1)(n?2)条边，由于G中边2数m?(n?1)(n?2)，故G中不存在孤立点。

29.3证明：将每个企业视为无向图中的一个顶点，两个企业之间有业务往来视为该图中的一条边，显然这个图是一个简单图。

34

(1)假设每个企业都只与奇数个企业有业务往来，因此，与每个顶点关联的边的数量均为奇数，对应的邻接矩阵B为一个奇数阶的对角元为0的对称矩阵，且每一行（列）只有奇数个元素为1，因此邻接矩阵B的为1的元素数量也必然为奇数，与B为对称矩阵矛盾，因此至少有一个企业与其他偶数个企业有业务往来。

(2)同样，如果有偶数个企业与其他偶数个企业有业务往来，其他奇数个企业只能与奇数个企业往来，那么邻接矩阵B中依然只有奇数个元素为1，与B为对称矩阵矛盾。不可能有偶数个企业与其他偶数个企业有业务往来。

9.4 证明：(1) 在简单图中，不存在只与一个顶点关联的边，每条边都恰与两个不同的顶点关联。显然与所有边关联的顶点的数量就是该图中所有顶点次的和，因此简单图中所有顶点次的和一定为偶数，且为图中边的数量的两倍。

(2) 如果在简单图中存在奇点，且只有奇数个奇点，那么所有顶点次的和就是奇数，矛盾，因此简单图中奇点的个数一定为偶数。

9.5证明：(1)G?(V,E)是一个简单图，即该图中无环，无平行边。已知

?(G)?2，假设G中无圈，则G可能为树或非连通图，该两种情况下均存在悬挂点，即?(G)?min{d(v)}?1，这与已知矛盾。故假设不成立，G必有圈。

v?V(2)若?(G)?2，设与?(G)对应的点为vk，即vk必与?(G)个端点相连。根据(1)的结论，G中必有圈（由于对圈中的连通图而言，vk至少与这?(G)个端点构成圈）。vi(i?1,2,?,?(G))的次至少为?(G)，也至少与?(G)个端点相连。如vk与

vi这?(G)?1个端点不构成圈，则在端点处必向外延伸（因次至少为?(G)，不与

其中某点相连，必与其外某点相连）经连通链而到另一端点，对该图而言，边数大于?(G)?1条，故G中必有包含至少?(G)?1条边的圈。

9.6 证明：因为G连通且不含奇点，则d(v)?2n，无悬挂点，根据习题9.5中的结论，G必有圈；又因为G是连通的，所以从G中去掉任一条边，例如在某一圈中，从圈中去掉任一条边，所得仍是连通图。

9.7 证明：根据寻求最大流的标号法，初始fij?0。

因为对弧(vi,vj)，vj标号，l(vj)?min{。对弧(vj,vi)，vj标号，l(vci),ij?fij}l(vj)?min{l(vi),fij。}依次类推，因为cij均为整数，所以最终得到调整量??l(ci)也为整数。

35

?fij???fij'??fij???f?ij(vi,vj)???(vi,vj)??? (vi,vj)??标号最终结果，得最大流f必为整数。

9.8 解：该图的关联矩阵为

e1A?1B??1C?0A??D?0E?0?F?0G??0e2e3e4e5e6e7e8e9e10e111010000000?1100000000??0101101000??0011010000?0000110001??0000001110?0000000011??

该图的邻接矩阵为

BCDEFGA201000?B010000??C101110?B??D010100?E011001??F010011?G000110??

9.9 解：该有向图的关联矩阵为

A?0?2??0??1?0??0?0?e1v1?1?A?v2?-1v3?0?v4?0v1v1?0?B?v2?0v3?1?v4?1e2-1010v21010v30000e3-1001e40-110e5010-1e60?0??1??-1?

该有向图的邻接矩阵为

v40?1??1??0?

9.10 解：这显然是一个最小支撑树问题。我们采用破圈法求解，逐步将网

36