第九章 图与网络分析.doc

第九章 图与网络优化9.1 重点、难点提要一、图与网络的基本概念1无向图设是一个有个顶点的非空集合：；是一个有条无向边的集合：，则称和这两个集合构成了一个无向图，记为。中任一条边若连接顶点和，则记该边为（或），并称与为无向边的两个端点，且边与顶点及相关联，顶点和顶点相邻。对于图，顶点集和无向边集也可以分别表示为和。一般用和表示图中顶点个数和边的条数。无向图中有平行边、简单图、完备图、子图、生成子图、导出子图、链、初等链、回路、连通图、割边、赋权连通图和网络等基本概念。其中赋权连通图是网络优化考虑的一个重要对象。根据实际问题的需要，每条边的权重可以是时间、距离、成本等相应的数值。2有向图设是一个有个顶点的非空集合：；是一个有条弧的集合：，则称和这两个集合构成了一个有向图，记为。有向图中有弧、入度、出度、平行边、孤立点、简单图、完备图、基本图、子图、导出子图、导出生成子图、同构图、链、初等链、路、路径、回路、赋权有向图和网络等基本概念。和赋权连通图一样，赋权有向图也是网络优化研究的一个重要对象。3图的矩阵表示(1) 无向图的关联矩阵和邻接矩阵设为一个无向图，其中，图的关联矩阵为，其中关联矩阵描述的是无向图顶点与边的关联状态。图的邻接矩阵为，其中邻接矩阵描述的是无向图顶点间的邻接状态。无向图的关联矩阵和邻接矩阵有如下特点：（i）无向图的关联矩阵的第行各元素之和为与顶点关联的边的数量，而的任何一列元素之和总是2；（ii）无向图的邻接矩阵为一个对称矩阵。(2) 有向图的关联矩阵和邻接矩阵设为一个有向图，其中，同样可以构造的一个关联矩阵和邻接矩阵，其中，为以顶点为起点，以顶点为终点的弧的数量,有向图的关联矩阵和邻接矩阵有如下特点：（i）有向图的关联矩阵的第行非零元素的个数为与顶点关联的弧的数量，而的任何一列元素之和总是0；（ii）有向图的邻接矩阵不一定对称；（iii）有向图的邻接矩阵的第行各元素之和为以顶点为起点的弧的数量，第列各元素之和为以顶点为终点的弧的数量。二、常见的网络优化问题1、最小支撑树问题树是图论中最简单但却十分重要的图。我们通常需要在一个网络中用最短的线路连通若干个固定顶点，例如铺设各种管道、规划交通网络、架设通讯线路等，这就是最小支撑树问题。最小支撑树在自然科学和管理科学中的许多领域有着广泛的应用。(1)树和有向树树是一种特殊的无向图，也称为无向树，要求图中无回路并且连通，树一般用表示。结论1：如果是一棵树，且，则下列命题等价。（1）连通且无回路；（2）无回路且只有条边，即；（3）连通且只有条边；（4）无回路，但在不相邻的任意两个顶点之间加上一条边，恰好得到一个回路；（5）连通，但去掉的任何一条边，将不再连通；（6）的任意两个顶点之间有且仅有一条初等链。(2)支撑树支撑树若是无向图的生成子图，并且同时又是树，则称是的支撑树，也称为生成树。结论2 图有支撑树的充分必要条件是为连通图。(3)最小支撑树给定一个网络，设是的支撑树，称中所有边的权数之和为树的权，记为，即 如果的支撑树满足 或则称为的最小支撑树，简称最小树。对于一个连通的网络，如何寻找或构造一个最小支撑树，通常称为最小支撑树问题。2、最短路问题最短路问题是网络优化中十分常见的，可以解决许多诸如管道铺设、线路安排、运费最小、运输时间最短等实际问题。对于一个赋权有向图，。若为一条顶点至的有向路径，则称为路径的长度。由于顶点至的有向路径不一定是唯一的，因此一定存在一条有向路径，使得我们称为顶点至的最短路径，为顶点至的最短路径的长度，并记为。 求一个赋权有向图中最短路径的问题称为最短路问题。根据不同的目的，求最短路通常使用Dijkstra算法、逐次逼近算法、Floyd算法等方法。3、最大流问题网络中的流量应用广泛，如交通系统中的车流、供水、供电系统中的水流、电流、经济中的现金流、供应链系统中的物流、控制系统中的信息流等问题都与网络中的流量有关。通常人们需要知道在一个既定网络中能通过的最大流量，这就构成了最大流问题。(1) 基本概念容量网络设为一个赋权有向连通图，每条弧的非负权重为该弧的最大流容量。如果中仅有一个入度为0的顶点和一个出度为0的顶点，则称为一个容量网络或运输网络。其中称为源，称为汇，称其余顶点为中间点。容量网络一般记为，其中为弧的最大流容量集合。由于在一个容量网络中，每条弧都有容量限制，因此在整个网络中的流必然受到一定限制，如果假设表示弧上的流量，则必须受到如下约束：（1）容量限制条件：对中的任意一条弧,；（2）平衡条件：对中的任意一个中间点,要求,即中间点的总流入量和总流出量相等,净流量(流出量与流入量之差)为零；对源和汇,要求,即从源发出的流量必须与汇接受到的流量相等。可行流满足以上两个条件的流量的集合称为一个可行流，记为。显然可行流一定存在。最大流问题就是在一个容量网络中寻找流量最大的可行流。饱和弧如果容量网络中某弧上的流量等于其容量限制，即，则称为的饱和弧。前向弧、后向弧假设为容量网络中从到的链，并且规定和为链的方向，链上与链的方向一致的弧称为前向弧，与链的方向相反的弧称为后向弧。前向弧集合用表示，后向弧集合用表示。可增广链假设是容量网络的一个可行流，如果满足则称为从到的（关于的）可增广链。割集容量网络,和为源和汇，若存在弧集，将网络分为两个子图和，其顶点集合分别为和，和为别属于和，则称弧集为的一个割集。割集容量为容量网络的一割集，称中所有弧的容量之和为的割集容量。最小割集容量网络一般有多个割集，其中割集容量最小的割集称为的最小割集，其割集容量称为的最小割集容量。(2) 最大流最小割定理定理9-1 设为网络的任一可行流，流量为，为分离到的一个割集，则有。定理9-2 （最大流最小割集定理）任意一个容量网络中，从源到汇的最大流的流量等于分离、的最小割集容量。推论 可行流是最大流的充要条件是不存在从到关于的可增广链。4、最小费用最大流问题 研究网络中的流时，需要注意流的可行性、高效性和经济性。实际网络中的流必须是可行流，其流量不能超过最大流的流量。网络以最小费用通过某一可行流的问题就是最小费用流问题，当网络中的流量达到最大时，就是最小费用最大流问题。赋权容量网络指在容量网络中，的每条弧上除了给出最大流容量外，还给出了单位流量的成本。赋权容量网络记为。最小费用流问题指求赋权容量网络的一个可行流，使得流量，且总费用达到最小。最小费用最大流问题指为最大流时的最小费用流问题。当是一个赋权容量网络，是上的一个可行流，是从源到汇的一条关于的可增广链，还有下列重要概念：链的费用称为的费用，记为，其中为的前向弧集合，为的后向弧集合。最小费用可增广链若是从源到汇所有可增广链中费用最小的链，则称为最小费用可增广链。定理9-3 若是流量为下的最小费用流，是关于的从源到汇的一条最小费用可增广链，则经过调整流量后得到的新可行流一定是流量为下的最小费用流。9.2 主要解题方法和典型例题分析题型I 求连通图的最小支撑树1、Kruskal法Kruskal算法的基本思想是先将网络中的边全部去除，然后逐步挑选备选边中权最小的边构成最小支撑树，并且确保与已经选好的边不产生回路。Kruskal算法也称为加边算法或避圈法。Kruskal算法步骤如下：第1步：将图的条边按权的递增顺序排列：第2步：令，循环变量赋值；第3步：设，若，转第6步，否则令；第4步：对满足的，令；第5步：若中的边的条数，算法终止，否则继续第6步；第6步：若，终止，图为非连通图，无支撑树，否则，令，转第3步。例9-1 用Kruskal算法构造图9-1的最小支撑树。图9-1解：根据Kruskal算法，不断选择权最小的边，同时新增边必须与已选边不构成回路，所选边顺序：，。具体步骤见图9-2(a)(g)。(a) (b)(c) (d)(e) (f)(g)图9-22、Prim算法Prim算法类似于Kruskal算法，不同的是每次加上的边必须与前面已经加上的边连通。对于赋权连通图，求的最小生成树的Prim算法步骤如下：第1步：在中任取一顶点，循环变量赋值；第2步：对于所有连接和的边，其中，如果不存在连接和的边，算法终止，无支撑树，否则继续第3步；第3步：取满足的边，其中，令，；第4步：如果，或者，得最小支撑树，算法终止，否则转第2步。例9-2 用Prim算法构造图9-1的最小支撑树。解：根据Prim算法，不断选择权最小的边，新增边必须与已选边连通且不构成回路，所选边顺序：，。具体步骤见图9-3(a)(g)。(a) (b)(c) (d)(e) (f)(g)图9-33、破圈法破圈法和Kruskal算法的方向相反，逐步将网络中权最大的边去除，直至网络形成支撑树。破圈法也称为破回路法。具体算法请读者仿照Kruskal算法或Prim算法建立。例9-3 用破圈法构造图9-1的最小支撑树。解：根据破圈法，不断将权最大的边剔除，每步剔除边时必须保证图的连通性，每步剔除的边分别为：，。具体步骤见图9-4(a)(e)。 (a) (b) (c) (d)(e)图9-4题型II 求网络的最短路问题1、Dijkstra算法Dijkstra算法是当前公认的求无负赋权有向图最短路径的最好算法，Dijkstra算法采用标号的方法，可求从顶点至其余顶点的最短路径。Dijkstra算法步骤如下：第1步：,取；取，,，；第2步：对于，令，取，；第3步：若，中至的路径不存在，算法终止，否则继续第4步；第4步：若，则输出最短路径的长度，算法终止，否则转第2步。上述Dijkstra算法可以给出最短路径长度是否存在及其长度，如果还要给出具体的最短路径，则要将每一步中的记录下来，同时记录其前列顶点。在比较简单的赋权有向图的实际计算中，常采用一种表格形式的Dijkstra算法。例9-4 用Dijkstra算法求图9-5所示网络中从顶点到其余顶点的最短路。图9-5解：采用表格形式的Dijkstra算法，步骤如下： ，； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点； ，因此到没有最短路。综合以上过程，得到顶点到其余各顶点的最短路径及其长度，如图9-6所示。图9-62、逐次逼近算法Dijkstra算法只能给出无负赋权有向图的最短路径，对于出现了负赋权弧的网络，通常使用逐次逼近算法。最短路性质：若序列是从到的最短路，则序列必为从到的最短路，序列也必为从到的最短路。如果令为到的最短路径长度，则为到最短路径长度，且 其中为边的长度，当与之间无边时，。上述方程可以构造逐次逼近法进行迭代，逐次逼近算法的基本步骤：第1步：输入，； 第2步：，；第3步：若时，迭代终止，并且 即是到的最短路径长度，否则，转第二步。例9-5 已知某地区的交通网络如图9-7所示，其中顶点代表村镇，边代表公路，为村镇间公路的距离（单位：公里），现该地区要建立一座中学，为了方便学生就学，问应该将学校建立在那个村镇，可使距离学校最远的村镇的学生上学时所经过的路程最近？图9-7解：本问题是一个选址问题，也可以归结为每点到各点的最短路问题。首先应该求出每个顶点到其余各顶点的最短路，然后再比较，最后选出符合要求的村镇建立学校。我们以顶点为例，求顶点到其余各顶点的最短路，使用逐次逼近法求解。初始条件为开始进行迭代，结果见表9-1。表9-1034.54.53031.51.51.51.520262.52.52.52.52031.81.81.81.86304.84.81.52.51.801.50001.501.51.51.5迭代到第3步时，迭代终止，顶点到的最短路径，长度在表9-1的最后一列。同样可以求出顶点到其余顶点的最短路，结果见表9-2。 表9-2村镇距离最远的村镇距离0356.39.34.569.33023.36.31.536.3520252.5456.33.32031.83.36.39.36.35304.86.39.34.51.52.51.84.801.54.8*6343.36.31.506.3 由于所有村镇到村镇的最长距离中4.8公里是最小的，因此应该在村镇建立学校，可使距离学校最远的村镇的学生上学时所经过的路程最近。3、Floyd算法Dijkstra算法和逐次逼近法可以给出网络从某一起始顶点到其他顶点的最短路，但是某些问题中，要求网络中任意两顶点间的最短路。Floyd算法不仅能求某一点到其他各点的最短路，还能求各点到某一点的最短路和任意两顶点间的最短路。在Floyd算法中权值正负不限。设是一个赋权有向图，其中,为弧的权重，当和间没有弧相连时。构造网络的权矩阵，其中Floyd算法基本步骤：第1步：输入权矩阵，对所有,；当，否则；。第2步：更新和。对所有，若，转第3步，否则，继续第3步。第3步：如果，转第2步。第4步：输出最短路距离矩阵，和最短路径矩阵。例9-6 用Floyd算法求图9-8所示网络中各顶点间的最短距离。图9-8解: 写出权矩阵和路径矩阵：,； ，； 由于，结束运算，求得各村之间的最短距离矩阵为，最短路径矩阵为。题型III 求网络的最大流问题求最大流的有效算法通常使用标号算法，从一个可行流开始，寻找一条从到的可增广链，直到找不到可增广链为止，最后的流量即为最大流。标号算法一般分为两个过程：第一是标号过程，通过标号来寻找可增广链，第二是调整过程，沿可增广链调整流以增加流量。标号算法的基本步骤：步骤1：标号过程（1）对于源，标号为；（2）选择每个已经标号的顶点，对于的所有未给标号的邻接点，作如下处理： 若，且，则令，并且将标号为。表示是的后续点。若，且，则令，并且将标号为。表示是的前列点。（3）重复步骤（2），直到汇被标号不再有顶点可被标号。若被标号，则得到一条可增广链，继续调整过程。若根据（2），不能获得标号，则说明已经是最大流。步骤2：调整过程调整一般反向进行，重新计算各条弧的流量。用表示调整后的弧的流量，令将调整后的流的标号全部去除，并重复步骤1和步骤2的标号和调整过程，对重新进行标号，直到不能再进行标号为止。例9-7 计算如图9-9所示的网络从到的最小割集和最大流。弧上记号表示相应弧的最大流容量。 图9-9 图9-10解：在图9-9中，弧上记号只有最大流容量，没有给出已知的可行流，为了采用标号法计算最大流，将可行流的所有流量计算为0，如图9-10所示,然后采取标号法计算最大流。步骤1：第一次标号过程将标号为，；检查的邻接点，满足，令 ，将标号为。检查的邻接点，满足，令 ，将标号为。检查的邻接点，满足，令 ，将标号为。得到可增广链，。步骤2：第一次调整过程由，得到第一次标号、调整的结果如图9-11(a)所示。依此类推，可以继续标号、调整过程，结果见图9-11中各图所示。(a) 第一次标号、调整()(b) 第二次标号、调整()(c)第三次标号、调整() (d)第四次标号、调整()(e)第五次标号、调整()图9-11经过5次标号调整，已经达到最大流容量限制，不再满足标号条件，标号过程无法继续。令，为最小割集，其容量即为网络的最大流量，。因此，该企业只要按照图9-11(e)的方式安排运输，即可获得从到的最大运输能力，最大运输能力为35。题型 求网络中的最小费用最大流问题 最小费用最大流问题主要使用对偶算法，其基本步骤：1、初始可行流取零流，即。2、若有可行流流量满足，构造长度网络。3、用Dijkstra算法求长度网络中从到的最短路。若不存在最短路，则即为最大流，不存在流量为的流，算法停止，否则继续第4步。4、在中与这条最短路相应的可增广链上，作，其中 此时的流量为，若则停止，否则令代替返回第2步。例9-8 某集团下有三个煤矿和三个火力发电厂,煤矿生产的煤供应给发电厂,有关煤矿的产能、发电厂的需求量以及相关运输费用见表9-3,要求尽可能多地生产煤供给给发电厂，建立网络模型使总费用最小，并求最小费用。表9-3单位运价发电厂产量煤矿16 13 2214 - 19 - 20 23506040最低需求量最高需求量70 0 3070 30 不限解：由于三个煤矿总产量为，三个发电厂最低需求量，不难知道发电厂的最高需求量。因此三个发电厂的最高需求量总和为因此为了平衡产销，我们虚拟一个煤矿，其产量为30。对于发电厂，由于其需求量在30至80之间，容量网络上很难直接反映该需求区间，因此将分拆为两个顶点和，其需求量分别为30和50，其中的需求必须得到满足，因此不能和虚拟煤矿关联。我们假设源和汇分别为、，则可得到运输容量网络，见图9-12,弧上参数分别为最大流容量和单位流成本。图9-12本问题的最大流显然是180，求最小运输成本归结为最小成本最大流问题。1、从初始可行流开始，作长度网络，见图9-13(a)，用Dijkstra算法求出的最短路为：。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-13(b)。(a) (b)图9-132、作长度网络如图9-14(a)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-14(b)。(a) (b)图9-143、作长度网络如图9-15(a)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-15(b)。(a) (b)图9-154、作长度网络如图9-16(a)，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-16(b)。(a) (b)图9-165、作长度网络如图9-17(a)，最短路为，的结果见图9-17(b)。(a) (b)图9-176、作长度网络如图9-18(a)，最短路为，的结果见图9-18(b)。(a) (b)图9-187、作长度网络如图9-19(a)，最短路为，的结果见图9-19(b)。(a) (b)图9-19由于，就是所求的最小费用最大流，最小费用为2520。9.3 习题9.1 判断下列说法是否正确：(1) 图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直都要严格注意。(2) 在任一连通图中，当点集确定后，树是中边数最少的连通子图。(3) 如果图中从至其他各点的最短路在去掉重复部分后，则恰好构成该图的最小支撑树。(4) 求网络最大流问题可归结为求解一个线性规划问题。9.2 证明：在一个简单图中，为顶点个数，为边的条数，如果，则中不存在孤立点。9.3 个企业之间，每个企业都与其它若干企业有业务往来，且为奇数。证明：(1) 至少有一个企业与其他偶数个企业有业务往来；(2) 不可能有偶数个企业与其他偶数个企业有业务往来。9.4简单图与某顶点关联的边的数量称为该顶点的次，次为奇数的顶点称为奇点。证明：(1) 简单图中所有顶点次的和一定为偶数，且为图中边的数量的2倍；(2) 简单图中奇点的个数一定为偶数。9.5 设是一个简单图，令（称为G的最小次）。证明：(1)若，则中必有圈；(2)若，则中必有包含至少+1条边的圈。9.6设是一个连通图，不含奇点。证明：中不含割边。9.7 设是一个有向网络，证明：如果中所有弧的容量都是整数，那么必存在一个最大流，使所有都是整数。9.8 求图 9-20所示的无向图的关联矩阵和邻接矩阵。图9-209.9求图9-21所示的有向图的关联矩阵和邻接矩阵。图9-219.10 已知图9-22表示某城市7个乡镇间拟修建一条能连接各个乡镇的通讯线路，每条边的权数表示两个乡镇之间通讯线路的建设费用。问应如何修建，才能使该线路的建设费用最低。图9-229.11 用Kruskal算法和破圈法求图9-23中各图的最小树。 (a) (b) (c) (d)图9-239.12 分别用Kruskal 算法和破圈法求图 9-24 的最小支撑树。图9-249.13 已知有六个城市：A、B、C、D、E、F，试由表9-4所示交通网络中的数据确定最小支撑树。表9-4 交通网络ABCDEFA6851501377B6836346720C513626057D503425955E1367605970F77205755709.14 有九个城市，其公路网如图9-25所示。弧上数字表示该段公路的长度，有一批货物从运到，求走哪条路最短？图9-259.15 用Dijkstra方法求图9-26中从到各点的最短路。图9-269.16 在如图9-27所示的网络中，用Dijkstra方法求从到各点的最短路径，并指出对来说哪些顶点是不可到达的。图9-279.17 在如图9-28所示的网络中，每条弧上的数字为，其中表示最大流容量，表示目前流量。(1) 确定所有的割集；(2) 求最小割集容量；(3) 证明图中标出的流就是该网络的最大流。图9-289.18 求如图9-29所示网络的最小费用流，弧上的数字为，其中表示最大流容量，表示单位流量成本。图9-299.19 求如图9-30所示网络的最小费用最大流。弧上的数字为，其中表示最大流容量，表示单位流量成本。图9-309.20 某车站拟在七个居民点中设置售票处，各点的距离如图9-31所示，边上的数字表示距离，单位：千米。(1)若要设置一个售票处，求设在哪个居民点可使最大服务距离为最小？(2)若要设置两个售票处，求设在哪两个居民点可使最大服务距离为最小？图9-319.21 某公司有3个仓库和4个零售店，各仓库可提供的货量及零售店的最大零售量见表9-5。表中打“”的方格表示公司指定该店可向相应的仓库取货。现在要求做一调运方案，使得各店从各仓库得到的总货量为最多。表9-5零售店仓库B1B2B3B4存货量A120A212A312最大零售量1498109.22某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从仓库到市场的运输能力如表9-6所示（表中“”表示无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？表9-6市场仓库B1B2B3B4存货量A130104020A2105020A32010405100最大零售量202060209.23 某单位招收懂俄、英、日、德、法文的翻译各一人，现有五人应聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这五个人是否都能被应聘？最多几个得到招聘，招聘后每人从事哪一方面的翻译工作？9.24 用Floyd算法分别求图9-32所图中任意两点间的最短路径及长度。 (a) (b)图9-329.25 某公司在六个城市中有分公司，从到的直接航程票价如下述矩阵中的位置上（表示无直接航路）。请你设计一张任意两城市间票价最便宜的路线表。9.4习题解答9.1 解：(1)错。图论中的图只反映了点边之间的关联关系，而与点的位置、边的形状和大小无关。(2)对。在树图中，若删除其中任一边，则不连通，因此树图是G中边数最少的连通子图。(3)错。首先，由于至各点都有最短路，此子图为连通的；其次，由于最短路的唯一性，此子图无圈，即为支撑树。但此子图不一定是最小支撑树。例如：(a) (b) (c)图9-33在图9-33(a)中，用Dijkstra标号法可求得至其余各点的最短路，可得支撑树如图9-33 (b)所示，权数和为25，而在图(a)中用破圈法可求得最小支撑树如图9-33 (c)所示，权数和为23。所以，图9-33 (b)不是最小支撑树。(4)对。9.2证明：由于为一个简单图，因此中不存在平行边。如果中存在一个孤立点，则其余个顶点之间最多有条边，由于中边数，故中不存在孤立点。9.3证明：将每个企业视为无向图中的一个顶点，两个企业之间有业务往来视为该图中的一条边，显然这个图是一个简单图。(1)假设每个企业都只与奇数个企业有业务往来，因此，与每个顶点关联的边的数量均为奇数，对应的邻接矩阵为一个奇数阶的对角元为0的对称矩阵，且每一行（列）只有奇数个元素为1，因此邻接矩阵的为1的元素数量也必然为奇数，与为对称矩阵矛盾，因此至少有一个企业与其他偶数个企业有业务往来。(2)同样，如果有偶数个企业与其他偶数个企业有业务往来，其他奇数个企业只能与奇数个企业往来，那么邻接矩阵中依然只有奇数个元素为1，与为对称矩阵矛盾。不可能有偶数个企业与其他偶数个企业有业务往来。9.4 证明：(1) 在简单图中，不存在只与一个顶点关联的边，每条边都恰与两个不同的顶点关联。显然与所有边关联的顶点的数量就是该图中所有顶点次的和，因此简单图中所有顶点次的和一定为偶数，且为图中边的数量的两倍。(2) 如果在简单图中存在奇点，且只有奇数个奇点，那么所有顶点次的和就是奇数，矛盾，因此简单图中奇点的个数一定为偶数。9.5证明：(1)是一个简单图，即该图中无环，无平行边。已知，假设中无圈，则可能为树或非连通图，该两种情况下均存在悬挂点，即，这与已知矛盾。故假设不成立，必有圈。(2)若，设与对应的点为，即必与个端点相连。根据(1)的结论，中必有圈（由于对圈中的连通图而言，至少与这个端点构成圈）。的次至少为，也至少与个端点相连。如与这个端点不构成圈，则在端点处必向外延伸（因次至少为，不与其中某点相连，必与其外某点相连）经连通链而到另一端点，对该图而言，边数大于条，故G中必有包含至少条边的圈。9.6 证明：因为连通且不含奇点，则，无悬挂点，根据习题9.5中的结论，必有圈；又因为是连通的，所以从中去掉任一条边，例如在某一圈中，从圈中去掉任一条边，所得仍是连通图。9.7 证明：根据寻求最大流的标号法，初始。因为对弧，标号，。对弧，标号，。依次类推，因为均为整数，所以最终得到调整量也为整数。标号最终结果，得最大流f必为整数。9.8 解：该图的关联矩阵为该图的邻接矩阵为9.9 解：该有向图的关联矩阵为该有向图的邻接矩阵为 9.10 解：这显然是一个最小支撑树问题。我们采用破圈法求解，逐步将网络中的权最大的边去除，过程如图9-34所示。图9-349.11 解： (a)用Kruskal 算法。从图中选取最小边GH=1，从未选边中选出AD=2,依次寻找下去，分别找出CG=2,GF=2,BG=3,AE=3,FE=4,以AD,AE, FE, GF,GH,CG,BG构成的图正好就是一颗最小支撑树，如图9-35所示。图9-35用破圈法。从ABC所构成的圈中去掉最大边AB=8，从ADBC所构成的圈中去掉最大边AC=7，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-36(a)和图9-36 (b)。(a) (b)图9-36(b) 用Kruskal 算法。从图中选取最小边AC=1，从未选边中选出BC=2与AC=1不构成圈，再从未选边中选出CE=2。依次寻找下去，分别找出EG=2,DE=2, EF=3,以AC,BC,CE,DE,EF,EG构成的图正好就是一个最小支撑树，如图9-37所示。图9-37用破圈法。从ABC所构成的圈中去掉最大边AB=3，从ADEC所构成的圈中去掉最大边AD=4，依次进行破圈，知道所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-38(a)和图9-38(b)所示 (a) (b)图9-38(c) 用Kruskal 算法。从图中选取最小边DE=1，从未选边中选出AB=2与DE=1不构成圈，从未选边中选出AC=2,依次寻找下去，分别找出BD=2,HJ=2,IJ=2,FH=2,GI=3,DF=3,以AC,AB,BD,DE,DF,FH,HJ,IJ,GI构成的图正好就是一个最小支撑树，如图9-39所示。图9-39用破圈法。从BDFH所构成的圈中去掉最大边BH=5，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-40(a)和图9-40(b)。(a) (b)图9-40(d) 用Kruskal 算法。从图中选取最小边EF=1，从未选边中选取DF=2与EF=1不构成圈，再从未选边中选出CG=3，依次寻找下去，分别找出AB=3, CD=4, BC=4,以AB,BC,CD,CG,DF,EF构成的图正好就是一个最小支撑树，如图9-41所示。图9-41用破圈法。从BCG所构成的圈中去掉最大边BG=7，从CEG所构成的圈中去掉最大边EG=6，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-42(a)和图9-42(b) (a) (b)图9-429.12 解: 用Kruskal 算法。从图中选取最小边CD=1,EF=1，从未选边中选取EF=1与CD不构成圈，再从未选边中选出AB=2,BC=2,CE=3,FG=4,以AB,BC,CD,CE,EF,FG构成的图正好就是一颗最小支撑树，如图9-43(a)所示。图9-43用破圈法。从EFG所构成的圈中去掉最大边EG=7，从BCF所构成的圈中去掉最大边BF=7，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-44(a)和图9-44(b)(a) (b)图9-449.13 解：把题中表用图的形式表示出来，如图9-45(a)所示。用Kruskal 算法。从图中选取最小边CD=2，从未选边中选取AE=13，与CD不构成圈，再从未选边中选出BF=20，BD=34，AD=50，以AE,AD,CD,BD,BF构成的图正好就是一个最小支撑树，如图9-45(c)所示。(a)(b) (c)图9-45 9.14 解：在图中没有负赋权，因此采用Dijkstra算法，步骤如下：，；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点。综合以上过程，得到顶点到最短路径为，长度为8.5。 9.15 解：在图中没有负赋权，采用Dijkstra算法，步骤如下：，；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点。，前列顶点。，前列顶点。，前列顶点。综合以上过程，得到顶点到其他各顶点的最短路径和长度分别为： 图9-46 9.16 解：采用Dijkstra算法，步骤如下：，；，前列顶点；，前列顶点；，前列顶点；，前列顶点；，前列顶点；已经无法继续，因此从无法到达和。到其他各顶点的最短路径和长分别为： 9.17 解：(1)首先确定所有的割集与对应的容量。 若，则其割集为，则该割集相应的容量为； 若，则其割集为，则该割集相应的容量为； 若，则其割集为，则该割集相应的容量为；若，则其割集为，则该割集相应的容量为；若，则其割集为，则该割集相应的容量为；若，则其割集为，则该割集相应的容量为；(2)上述各割集中，最小割集的容量为，此时最小割集为。(3)根据最大流量最小割集定理，在该网络中，其最大流的流量为。由于，所以图中标出的流就是最大流。 9.18 解：已知网络最大流为。只要求流量为11时的最小费用流即可。（1）从开始，作长度网络，见图9-47(a)，用Dijkstra算法求出的最短路为：。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-47 (b)。（2）作长度网络如图9-47 (c)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-47(d)。（3）作长度网络如图9-47(e)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-47(f)。（4）作长度网络如图9-47(g)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为。在网络中相应的可增广链上用最大流算法进行流的调整：，的结果见图9-47(h)。由于，就是所求的最小费用流，最小费用为。(a) (b) (c) (d) (e) (f) (g) (h) 图9-479.19 解：求解过程如图9-48所示。即为最大流，也为最小费用最大流。(a) (b) (c) (d) (e) (f) (g) (h) (i) 图9-489.20 解：首先用Floyd算法可求得各点之间的