作业帮请教一道与图论有关的问题.
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/24 12:52:47
请教一道与图论有关的问题.
具体来说,是中国邮递员问题.
中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.
即一个可行解是最优解的充要条件是:
(1)每条边至多重复一次
(2)任意回路中重复边的权数不大于该回路总权数的一半.
这个定理的证明我看过很多论文,必要性的证明我能看懂(即如果是最优解,则必然满足这两个条件),但充分性的证明我一直都糊里糊涂的.
所以想请各位高手给一个比较好懂的充分性的证明.在此谢过.
禁止复制黏贴,中国邮递员问题的论文我看的还是比较多的,是不是复制黏贴我一眼就可以看出来.
具体来说,是中国邮递员问题.
中国邮递员问题的算法中有一种叫奇偶图上作业法的方法.这种方法的根据是一个已经得到证明的定理.
即一个可行解是最优解的充要条件是:
(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).
再问： 又由充要条件2可以推得在G[E]的任何一个圈C中, E1和E2在其上的权重之和都等于w(C)的一半.
————————————————————————————-
这句话不理解,不是说不大于一半吗,或者说为什么可以由G[E]中的回路同时包含E1与E2的边可以推得E1和E2的权之和都等于w(C)的一半？
再答： 由于两者权和都≤w(C)/2
但是两者求和=w(C)
所以可推得E1和E2的权之和都等于w(C)的一半
再问： 由于E1和E2中各自都不含圈(由E1,E2的定义可知).
————————————————————-——
这句话也不理解.或者说看的有点怪怪的…E1是一个集合,当然不可能含有回路了.您应该想表达的是G1吧？但如果是G1的话,G1既然是由E1生成的图,怎么会没有回路呢？
再答： 哦,我想表达的意思就是把E1这些边看作一个图,就是说为了让图变成欧拉图而加的那些边是不构成圈的
再问： 啊,不好意思,我还想再问几个问题,请见谅.
我突然在想,这套证明的大体思路就是先找出E1和E2的非公共部分,然后将这些公共部分合成一个图E.因为E1和E2各自不构成回路,所以E中任意一条回路都是由E1和E2的边组成的.然后再根据条件2推得w(E1)=w(E2).
所以我想问的是,证明图E是欧拉图那一步有什么作用？您看上面的思路中就跳过了证明欧拉图那一步,但似乎也能自圆其说.
再答： 是欧拉图才必定有遍历所有点的圈,否则未必能找到圈C
再问： 哦…那么,证明图E是欧拉图的那一步可以再讲的仔细点吗？
比如这句话我就看不大懂:这是因为在G1和G2中,在某个顶点v上添加的边数的奇偶性和d(v)是相同的
再答： 好的,首先记号上不是图E,是图G[E].E只是边集,G[E]才代表由E生成的图.
然后是后面这句话的解释.由于G1和G2都是欧拉图,所以他们的所有点都是偶度的,考虑他们的原图,我们知道G1和G2都是由一个非欧拉图添加一些重边得到的,不妨设在G2某一点v处添加了若干条边,并且点v在初始的非欧拉图中度为d(v).那么每添加1条边,v的度就增加1,如果总共在v上添加了K条边,那么在G2中v点的度就变为d(v)+K.由d(v)+K为偶数可知d(v)和K的奇偶性相同.
再问： 原谅我一下脑子转不过弯来…待会肯定给您附加分.
您的解说我是看懂了,确实,d(v)与K的奇偶性必然相同.但问题是,为什么可以由d(v)与K的奇偶性相同推得G[E]是欧拉图？
再答： 分倒是无所谓,我搞图论的,难得看到个专业问题也蛮开心的.
按照d(v)的奇偶性来讨论
如果d(v)为奇数,那么G1,G2的原图在v上都添加了奇数条边,所以在G[E]中v点的度就是偶数(如果G1G2中添加的边不重复,则奇数+奇数=偶数,如果重复了p条边,那么奇数+奇数-2p=偶数)
如果d(v)为偶数,同理可得.
由此可知G[E]中所有的点都是偶度的.
再问： 原来您是研究图论的啊……难怪这么专业.
对了,我还有一个问题想请教.
这个问题比较长,这里打不下,所以我私信给您.请注意接收.
再问： 原来您是研究图论的啊……难怪这么专业.
对了,我还有一个问题想请教.
这个问题比较长,这里打不下,所以我私信给您.请注意接收.
在充分性证明时,假设最优图添加的重边集合是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).
再问： 又由充要条件2可以推得在G[E]的任何一个圈C中, E1和E2在其上的权重之和都等于w(C)的一半.
————————————————————————————-
这句话不理解,不是说不大于一半吗,或者说为什么可以由G[E]中的回路同时包含E1与E2的边可以推得E1和E2的权之和都等于w(C)的一半？
再答： 由于两者权和都≤w(C)/2
但是两者求和=w(C)
所以可推得E1和E2的权之和都等于w(C)的一半
再问： 由于E1和E2中各自都不含圈(由E1,E2的定义可知).
————————————————————-——
这句话也不理解.或者说看的有点怪怪的…E1是一个集合,当然不可能含有回路了.您应该想表达的是G1吧？但如果是G1的话,G1既然是由E1生成的图,怎么会没有回路呢？
再答： 哦,我想表达的意思就是把E1这些边看作一个图,就是说为了让图变成欧拉图而加的那些边是不构成圈的
再问： 啊,不好意思,我还想再问几个问题,请见谅.
我突然在想,这套证明的大体思路就是先找出E1和E2的非公共部分,然后将这些公共部分合成一个图E.因为E1和E2各自不构成回路,所以E中任意一条回路都是由E1和E2的边组成的.然后再根据条件2推得w(E1)=w(E2).
所以我想问的是,证明图E是欧拉图那一步有什么作用？您看上面的思路中就跳过了证明欧拉图那一步,但似乎也能自圆其说.
再答： 是欧拉图才必定有遍历所有点的圈,否则未必能找到圈C
再问： 哦…那么,证明图E是欧拉图的那一步可以再讲的仔细点吗？
比如这句话我就看不大懂:这是因为在G1和G2中,在某个顶点v上添加的边数的奇偶性和d(v)是相同的
再答： 好的,首先记号上不是图E,是图G[E].E只是边集,G[E]才代表由E生成的图.
然后是后面这句话的解释.由于G1和G2都是欧拉图,所以他们的所有点都是偶度的,考虑他们的原图,我们知道G1和G2都是由一个非欧拉图添加一些重边得到的,不妨设在G2某一点v处添加了若干条边,并且点v在初始的非欧拉图中度为d(v).那么每添加1条边,v的度就增加1,如果总共在v上添加了K条边,那么在G2中v点的度就变为d(v)+K.由d(v)+K为偶数可知d(v)和K的奇偶性相同.
再问： 原谅我一下脑子转不过弯来…待会肯定给您附加分.
您的解说我是看懂了,确实,d(v)与K的奇偶性必然相同.但问题是,为什么可以由d(v)与K的奇偶性相同推得G[E]是欧拉图？
再答： 分倒是无所谓,我搞图论的,难得看到个专业问题也蛮开心的.
按照d(v)的奇偶性来讨论
如果d(v)为奇数,那么G1,G2的原图在v上都添加了奇数条边,所以在G[E]中v点的度就是偶数(如果G1G2中添加的边不重复,则奇数+奇数=偶数,如果重复了p条边,那么奇数+奇数-2p=偶数)
如果d(v)为偶数,同理可得.
由此可知G[E]中所有的点都是偶度的.
再问： 原来您是研究图论的啊……难怪这么专业.
对了,我还有一个问题想请教.
这个问题比较长,这里打不下,所以我私信给您.请注意接收.
再问： 原来您是研究图论的啊……难怪这么专业.
对了,我还有一个问题想请教.
这个问题比较长,这里打不下,所以我私信给您.请注意接收.