请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/17 13:05:51
![请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要](/uploads/image/z/13894120-64-0.jpg?t=%E8%AF%B7%E6%95%99%E4%B8%80%E9%81%93%E4%B8%8E%E5%9B%BE%E8%AE%BA%E6%9C%89%E5%85%B3%E7%9A%84%E9%97%AE%E9%A2%98.%E5%85%B7%E4%BD%93%E6%9D%A5%E8%AF%B4%2C%E6%98%AF%E4%B8%AD%E5%9B%BD%E9%82%AE%E9%80%92%E5%91%98%E9%97%AE%E9%A2%98.%E4%B8%AD%E5%9B%BD%E9%82%AE%E9%80%92%E5%91%98%E9%97%AE%E9%A2%98%E7%9A%84%E7%AE%97%E6%B3%95%E4%B8%AD%E6%9C%89%E4%B8%80%E7%A7%8D%E5%8F%AB%E5%A5%87%E5%81%B6%E5%9B%BE%E4%B8%8A%E4%BD%9C%E4%B8%9A%E6%B3%95%E7%9A%84%E6%96%B9%E6%B3%95.%E8%BF%99%E7%A7%8D%E6%96%B9%E6%B3%95%E7%9A%84%E6%A0%B9%E6%8D%AE%E6%98%AF%E4%B8%80%E4%B8%AA%E5%B7%B2%E7%BB%8F%E5%BE%97%E5%88%B0%E8%AF%81%E6%98%8E%E7%9A%84%E5%AE%9A%E7%90%86.%E5%8D%B3%E4%B8%80%E4%B8%AA%E5%8F%AF%E8%A1%8C%E8%A7%A3%E6%98%AF%E6%9C%80%E4%BC%98%E8%A7%A3%E7%9A%84%E5%85%85%E8%A6%81)
请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要
请教一道与图论有关的问题.
具体来说,是中国邮递员问题.
中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.
即一个可行解是最优解的充要条件是:
(1)每条边至多重复一次
(2)任意回路中重复边的权数不大于该回路总权数的一半.
这个定理的证明我看过很多论文,必要性的证明我能看懂(即如果是最优解,则必然满足这两个条件),但充分性的证明我一直都糊里糊涂的.
所以想请各位高手给一个比较好懂的充分性的证明.在此谢过.
禁止复制黏贴,中国邮递员问题的论文我看的还是比较多的,是不是复制黏贴我一眼就可以看出来.
请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要
中国邮递员问题在证明最优解的充要条件时,我们通常都是把原问题化为在图上添加重边,使得原图变为欧拉图,然后使得添加的重边权数和最小.
在充分性证明时,假设最优图添加的重边集合是E1,对应图为G1.满足前面提到的两个充要条件的某种添加的重边集为E2,对应图为G2.那么我们的目标就是证明w(E1)=w(E2)
考虑边集E=E1∪E2\(E1∩E2).
那么如果E为空集,说明E1=E2,此时充分性成立.
如果E不为空集,则E生成的图G[E]中的各个顶点都为偶数.这是因为在G1和G2中,在某个顶点v上添加的边数的奇偶性和d(v)是相同的.(这条是证明重点,理解这条就能理解充分性的证明)
之后的问题就很简单,E中的顶点都为偶数,所以G[E]是若干个欧拉图的并. 又由于E1和E2中各自都不含圈(由E1,E2的定义可知). 所以G[E]中的圈都同时包含E1和E2中的边,又由充要条件2可以推得在G[E]的任何一个圈C中, E1和E2在其上的权重之和都等于w(C)的一半. 从而w(E1\(E1∩E2))=w(E2\(E1∩E2)),即w(E1)=w(E2).