作业帮请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 19:43:22
请教一道与图论有关的问题.具体来说,是中国邮递员问题.中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.即一个可行解是最优解的充要
请教一道与图论有关的问题.
具体来说,是中国邮递员问题.
中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.
即一个可行解是最优解的充要条件是:
(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).