运筹学图与网络分析补例4

第1页（共28页）运筹学图与网络分析补例1、证明下列序列不可能是某个简单图的次的序列（1）7，6，5，4，3，2；（2）6，6，5，4，3，2，1；（3）6，5，5，4，3，2，1证（1）已知定理2vVdvq，而在此序列中27vVdv为奇数，所以此序列不可能作为图的次的序列。或由已知定理：奇点的个数应为偶数，而在此序列里，奇点7、5、3为奇数个，，所以此序列不可能作为图的次的序列。（2）由已知定理：奇点的个数应为偶数，而在此序列里，奇点5、3、1为奇数个，，所以此序列不可能作为图的次的序列。（3）对于七个点的图，假定1276,5,1dvdvdv，并假设该图G为简单图，则1v存在于其它六个点的连线，2v与1v间存在边12e，而7v次为1，所以7v一定不与1v以外的其它点相连，因而2v与1v、7v以外的四个点个有一条线相连。由于假设G(V,E)为简单图，则余下的3456,,,vvvv中任意点（用iv表示）以确定存在12,iiee，无7ie。对于5idv的该点来说，必与除7v以外的每一点都有连线，设35dv。由此推得，456,,vvv都同时与123,,vvv，即456,,vvv的次数至少是3，这与62dv相矛盾。故假设“是某个简单图的次的序列”不成立，即该图可能有环或多重边，该序列不是某个简单图的次的序列。2、求最小支撑树（生成树）例求右图的最小树解1）用破圈法：取一圈1123321,,,,,,vevevev去掉2e，取一圈2658332,,,,,,vevevev去掉6e，取一圈2445332,,,,,,vevevev去掉3e，取一圈4758354,,,,,,vevevev去掉8e得到一棵支撑树**,12126TWT2）用避圈法：在12345678,,,,,,,eeeeeeee中取权值最小的边有15,ee，从中任取一条1e；在2345678,,,,,,eeeeeee中取权值最小的边5e；在234678,,,,,eeeeee中取权值最小的边有37,ee，从中任取一条3e；在24678,,,,eeeee中取权值最小的边7e；在2468,,,eeee中取权值最小的48,ee中任何一条，54313221e8e6e4e2e7e5e3e1v1v2v3v4v554313221e8e6e4e2e7e5e3e1v1v2v3v4v5第2页（共28页）都会与已知边构成圈，故停止。特点：破圈法始终连通，避圈法则是由可能不连通走向连通。3、已知世界6大城市：Pe，Pa，T，M，N，L。试在下表所示交通网络的数据中确定最小树。PeTPaMNLPe1351776850T1360706759Pa516057362M7770572055N6867362034L505925534解将题设中的表用图表示采用避圈法，寻找最小边的过程如下：[,][,][,][,][,]21320345012345|LPaPeTNMLNPeL最后找到的[,],[,],[,],[,],[,]LPaPeTNMLNPeL构成最小支撑树如图所示135034202NLMPaTPe213503420119WT4、求右图从点1v到各点的最短路经解首先在始点1v标以0,0，然后在3v标以1,2v，由于2112332min,,,lvlvwvvlvwvvmin01,2354114334min,,,min03,257lvlvwvvlvwvv所以在2v标以3,5v，在4v标以3,7v，然后在6v标以3,1v。821-53781-2-2-3-2-1v1v2v3v4v7v5v6v868552777067595136605720345013PeTPaMLN13503420576036515967707725568NLMPaTPe第3页（共28页）由于5225335665min,,,,,lvlvwvvlvwvvlvwvvmin52,22,1147667337447min,,,,,lvlvwvvlvwvvlvwvvmin11,22,725所以在5v标以3,4v，在7v标以4,5v，最后由于8558668778min,,,,,lvlvwvvlvwvvlvwvvmin48,17,583所以在终点8v处应标以7,3v。所有点度获得了标号，反向追踪得到1v到8v的最短路为13478vvvvv。长度为3。(v7,3)(v4,-5)(v3,-4)(v3,-1)(v3,-7)(v3,-5)(v1,-2)(0,0)-1-2-3-2-21873-5128v8v6v5v7v4v3v2v15、有9个城市129,,,vvv，其公路网如下图所示。弧旁边的数字是该段公路的长度，有一批货物从1v运到9v，问走哪条路最短？12.524233245333v1v2v3v9v6v5v7v4v8解以ijl表示iv到jv的弧上的距离权，则[v6/v4,7][v2,6][v2,5][v1,4][v7,9][v6,8.5][v2,6][v1,3][0,0]333542332422.51v8v4v7v5v6v9v3v2v1第4页（共28页）可以写出网络的距离矩阵ijLl，其中若iv到jv没有弧，则ijl。若网络是无向网络，则距离矩阵为对称矩阵。最短路问题可以这样描述：要找从1v到nv的通路，使全长为最短，即minijijeLl由题设，有0340323050303012.5022040L将其列入下表:jvj123456789初始值T0第1次迭代1iijPl0+30+0+40+0+0+0+0+T34第2次迭代2iijPl3+33+3+23+33+3+3+T6456第3次迭代4iijPl4+4+4+4+34+4+T6567第4次迭代5iijPl5+5+35+5+5+T667第5次迭代3iijPl6+6+6+6+5T6711第6次迭代ijPl6+16+6+2.5第5页（共28页）6iT78.5第7次迭代7iijPl7+27+2T98.5在表中的第一行是初始值,jTv表示jPv，对应距离矩阵的第一列。以后的ijPl行是由上一行中的iPv与ijl的和，T行是从上两行中对应的元素中取最小的一个，相当于min,jjiijTvTvPvl每次迭代在jTv行选最小的，用表示kPv，以后对应的列不再进行计算，相当于从S中去掉。根据上述迭代，得1v到9v的最短路为1269,,,vvvv，因为其总权值8.5可分解为1226698.562.5332.5,,,vvvvvv。6、用求右图中从1v到各点的最短路解计算过程如表所示12-2-344321223v6v3v5v4v2v1点ijw,tijdvv1v2v3v4v5v6v1t2t3t4t1v01200002v03411113v0-20514114v40-322225v230-1-1-112-2-344321223v6v3v5v4v2v1第6页（共28页）6v220以2t列为例（11t，含无穷仅写一个）计算：0min00,1,2，1min01,10,24,，4min0,13,2,，被加数不动，2min02,14,20,，1min0,1,23,。类推…..故1213141516,1,,1,,2,,1,,dvvdvvdvvdvvdvv用Warshall-Flod方法求该图任意两点间的最短路如下：开始（k=0）作距离矩阵00ijLl和序号矩阵00ij，其中p为网络的顶点数，00,,,,,1,2,,,,ijijijijijwvvAljijpvvA，ijw为弧上的权数，A为网络的弧集。第一步：1krrp时，kL中第k行和第k列元素保持与1kL相应元素相同，其它元素按下式计算，并填入kL中：111min,kkkkijijikkjllll，相应地k的元素按下式变化：1111,,kkkijijijkijkkkijijijllll第二步：若存在01kiilip，计算终止；否则，置1kk；第三步：当kp时，计算终止。若pijl表示不存在从iv到jv的路；否则，记pijijdl表示由iv到jv的最短路长，相应地，最短路线可由,1,2,,pijijp追溯找出。01010121234560341234562051123456L=L=,==403123456230123456220123456；22012124563412345620112356k=2,L=,=403124562342227012345622012023456；第7页（共28页）3352430300121246034123462112356k=3,L=,=40312456230134562422272020143335644030401212460341234620124222326k=4,L=,=4312456230134562013141723330641155141411302146034123462012326k=5,L=03043,=03145623134511443162223551360066141411302146034123462012326k=6,L=03043,=031456230134511443162522160353例如由于6121l为1v到2v的路径长，查6得(6)(6)(6)(6)124252324,5,3,2，从而1v到2v的最短路为14532vvvvv。7、求右图中从任意点到另外任一点的最短距离解1）从1v开始出发求最短路，先得距离矩阵表点ijw1v2v3v4v5v6v236732312v1v2v6v3v5v4213237632v5v3v6v2v1v4第8页（共28页