*14521322632v3v1v2v4v5v614521322632v3v1v2v4v5v6取圈{v2,v3,v5,v6，v2}（粉红色的线组成），调整前的图G(1)调整后的图G(2)调整得G(2),有R(2)，总权是37。*逐圈检验。得G(2)=G*,其上任一个Euler圈皆为R*.14521322632v3v1v2v4v5v6最后的图例如可取：R*={v6,v2,v3,v4v1,v2,v3,v5v1,v6,v3,v5v1,v4,v5,v6}*练习题1.求解所给网络的中国邮递员问题，为邮局所在地。**第五章图论与网络优化*§5-1引论§5-2图论基本概念§5-3树及其优化问题§5-4最短路问题§5-5最大流问题§5-6中国邮递员问题*这是一个非常有趣的问题，该问题可描述为：一个邮递员从邮局出发，要走遍他所负责的每一条街道去送信，如图5-15所示。中国邮递员问题在物流配送中应用比较多，也经常作为其它问题的子问题。§5-6中国邮递员问题问应当如何选择适当的路线，可使所走的总路程最短。5v3v8v7v6v5v4v2v1v9v13v12v11v10?31111112223336445图5-15*由于这个问题是我国学者菅梅谷于1962年首先提出来的，因此国际上称它为中国邮递员问题。本问题用图的语言来描述，就是给定一个连通图G，在每条边上有一个非负的权，要寻求一个圈，经过G的每条边至少一次，并且圈的权数最小。相关的游戏题：“田”字是否可以一笔画成？“日”字是否可以一笔画成？“目”字是否可以一笔画成？这些问题称为一笔画问题，也称为遍历问题，是很有实际意义的问题。*一．Euler(欧拉)图【定义17】设图G连通，若G中存在含所有边的简单链C，经过G的每条边一次且仅一次，则C称为Euler链，若C为圈，则称为Euler圈，当G存在Euler圈时。G称为Euler图。由此定义可知：一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链；G有非闭Euler链，则G可一笔画成。始点与终点必不相同；G有封闭Euler圈，做一笔画时，始点与终点一定重合。*【定理9】图G是欧拉图的充分必要条件是G连通且无奇点。此定理提供了一个判断Euler图的有效方法。对于非闭Euler链，则有下述同样明确的结论：【定理10】图G有非闭欧拉链的充分必要条件是G连通有且仅有两个奇点。由于要求邮递员送完邮件后必须返回邮局，其投递路线就成为一个圈，从而中国邮递员问题与Euler图势必发生密切的关系。事实上，若所走街巷恰是一个Euler图时，则此Euler图所对应的Euler圈显然是一条不走一步回头路的最优投递路线。所以，如何判断一个图为Euler图就十分重要了。*CADB哥尼斯堡七桥问题可抽象为下图所示形状：因为有4个奇点，所以该图不是Euler圈，一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。而在图5-16中：因为仅有两个奇点，所以存在一个非闭的Euler链，可以一笔画出。v5v6v4v2v1v3图5-16*二.最优性条件对于所走街巷图正好是Euler图的问题，找出Euler圈就是最优的投递路线。此时，街巷图与路线图是重合的。而当遇到街巷图不是Euler图时，又如何定出最优的投递路线呢?这就是下述一般的优化问题：设有连通非负赋权图G=(V,E,W)，R为含E中所有边的圈。求圈R*，使其满足：即要求一个含E中所有边且总权为最小的圈。*当G中无奇点，问题已获解。今设G有奇点，故而任一蕴含E的R必含重复边。此时，邮递员难免要在某些街巷上走回头路（回头路，即重复边。目的是为了改变点的度，使所有点的度都为偶数）。因此，问题的目标就是使得重复边的总权最小。此目标达到与否的一种判别方法由下述定理给出。【定理11】设连通非负赋权图G=(V,E,W)，R为包含E的圈。R有最小总权的充分必要条件为：(1)每边最多重复一次；(2)在G的每个初等圈(圈中各点不相同)上，重复边总权不超过圈总权的一半。*三.图上作业法从一笔画问题的讨论可知，一个邮递员在他所负责投递的街道范围内，如果街道构成的图中没有奇点，那