离散数学第十章 几种图及介绍.ppt

10.6 图的实例分析 * 最短路径问题 * 10.6 图的实例分析 如果图G只有两个奇点x和y，则存在一条以x和y为端点的欧拉链，因此，由这条欧拉Euler链加x到y最短路即是所求的最优投递路线。 如果连通图G不是欧拉图也不是半欧拉Euler图，由于图G有偶数个奇点，对于任两个奇点x和y，在G中必有一条路连接它们。将这条路上的每条边改为二重边得到新图H1，则x和y就变为H1的偶点，在这条路上的其他顶点的度数均增加2，即奇偶数不变，于是H1的奇点个数比G的奇点个数少2。对H1重复上述过程得H2 ，再对H2重复上述过程得H3 ，…，经若干次后，可将G中所有顶点变成偶点，从而得到多重欧拉图 （在 中，若某两点u和v之间连接的边数多于2，则可去掉其中的偶数条多重边，最后剩下连接u与v的边仅有1或2条边，这样得到的图 仍是欧拉图）。这个欧拉欧拉图 的一条欧拉回路就相应于中国邮递员问题的一个可行解，且欧拉回路的长度等于G的所有边的长度加上由G到 所添加的边的长度之和。但怎样才能使这样的欧拉回路的长度最短呢？如此得到的图 中最短的欧拉Euler回路称为图G的最优环游。 * 中国邮递员问题 10.6 图的实例分析 定理10.19 设P是加权连通图G中一条包含G的所有边至少一次的闭链，则P最优（即具有最小长度）的充要条件是： （1）P中没有二重以上的边。 （2）在G的每个圈C中，重复边集E的长度之和不超过这个圈的长度的一半，即 * 中国邮递员问题 10.6 图的实例分析 根据上面的讨论及定理10.19，我们可以设计出求非欧拉带权非欧拉连通图G的最优环游的算法。此算法称为最优环游的奇偶点图上作业法。 （1）把G中所有奇点配成对，将每对奇点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中没有奇点，即G1为多重欧拉图。 （2）若G1中每一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接，得到图G2。 （3）检查G2的每一个圈C，若某一个圈C上重复边的权和超过此圈权和的一半，则将C中的重复边改为不重复，而将单边改为重复边。重复这一过程，直到对G2的所有圈，其重复边的权和不超此圈权和的一半，得到图G3。 （4）G3的Euler回路。 * 中国邮递员问题 10.6 图的实例分析 例10.19 求图10.51所示图G的最优环游。 解：图G中有6个奇点v2，v4，v5，v7，v9，v10，把它们配成三对：v2与v5，v4与v7，v9与v10。在图G中，取一条连接v2与v5的路v2v3v4v5，把边(v2，v3)，(v3，v4)，(v4，v5)作为重复边加入图中；再取v4与v7之间一条路v4v5 v6v7，把边(v4，v5)，(v5，v6)，(v6，v7)作为重复边加入图中，在v9和v10之间加一条重复边(v9，v10)，如图10.52所示，这个图没有奇点，是一个欧拉图。 图10.51-10.53 * 中国邮递员问题 10.6 图的实例分析 在图10.52中，顶点v4 与v5之间有3条重边，去掉其中2条，得图10.53所示的图，该图仍是一个欧拉图。 如图10.53中，圈v2v3v4v11v2的总权为24，而圈上重复边的权和为14，大于该圈总权的一半，于是去掉边(v2 ,v3)和(v3 ,v4)上的重复边，而在边(v2 ,v11)和(v4 ,v11)上加入重复边，此时重复边的权和为10，小于该圈总权的一半。同理，圈v5 v6v7v12v5的总权为25，而重复边权和为15，于是去掉边(v5, v6)和(v6 ,v7)上的重复边，在边(v5,v12)和(v7 ,v12)上加重复边，如图10.54所示。 图10.54-10.56 * 中国邮递员问题 10.6 图的实例分析 图10.54中，圈v4v5 v12v11v4的总权为15，而重复边的权和为8，从而调整为图10.55所示。 图10.55中，圈v1v2v11v12v7 v8v9v10v1的总权为36，而重复边的总权为20，继续调整为图10.56所示。 检查图10.56，可知定理的⑴和⑵均满足，故为最优方案，接着给出出图10.56所示图的Euler回路，即为图G的最优环游 由上例可知，对于比较大的图，要考察每个圈上重复边权和不大于该圈总权和的一半，确定每个圈的时间复杂性太大。1973年Edmonds和Johnson给出了一个更有效算法。 * 中国邮递员问题 10.6 图的实例分析 旅行售货员问题（Traveling Salesman Problem