S1图的基本概念s1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树16三、中国邮路问题
16 §1 图的基本概念 §1 图的基本概念 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树 三、中国邮路问题
S1图的基本概念三、中国邮路问题页1.问题描述二、中国邮路问题邮递员在投送报刊信件时，从邮局出发，一般每次都要走遍他所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择一条什么样的路线才能以尽可能少的路程走完所有的街道呢？这个问题是我国著名运筹学家管梅谷教授于1962年首先提出的，并给出了它的解法，因此国际上称为中国邮路问题。1.问题描述在一个赋权图上，求一个圈，该圈经过图中每条边至少一次，并使圈中各边权值的总和为最小。称经过每条边至少一次的圈为邮递员路线。中国邮路问题就是求最优的邮递员路线。如何理解最优邮递员路线？欧拉图：则以邮局为始终点的一个欧拉圈就是最优邮递员路线。非欧拉图：则邮路中的某些边必须重复，带有重复边且总权值最小的圈最优邮递员路线。能形成圈的重复边方案不止一个，这时的问题是重复哪些边最好。172.定理
17 §1 图的基本概念 三、中国邮路问题 1. 问题描述 二、 中国邮路问题 邮递员在投送报刊信件时，从邮局出发，一般每次都要走遍他所负责的全部街道，任务 完成后返回邮局。那么邮递员应该选择一条什么样的路线才能以尽可能少的路程走完所 有的街道呢？这个问题是我国著名运筹学家管梅谷教授于1962年首先提出的，并给出了 它的解法，因此国际上称为中国邮路问题。 在一个赋权图上，求一个圈，该圈经过图中每条边至少一 次，并使圈中各边权值的总和为最小。称经过每条边至少 一次的圈为邮递员路线。中国邮路问题就是求最优的邮递 员路线。 2. 定理 1. 问题描述 如何理解最优邮递员路线？ 欧拉图： 则以邮局为始终点的一个欧拉圈就是最优邮递员路线。 非欧拉图：则邮路中的某些边必须重复，带有重复边且总权值最小的圈最优邮递员路线。 能形成圈的重复边方案不止一个，这时的问题是重复哪些边最好
S1图的基本概念三、中国邮路问题2定理2.定理定理3-3（顶点度之和与边数的关系）：对于一个图G，其所有顶点度的和等于边数9的两倍。即Zd(v)= 2q。VEV说明：因为每条边与两个端点相关联，所以计算顶点的度时每条边均使用了两次，所以全部顶点度的和等于边数的两倍。18定理3-4
18 §1 图的基本概念 三、中国邮路问题 2. 定理 定理 3-4 2. 定理 因为每条边与两个端点相关联，所以计算顶点的度时， 每条边均使用了两次，所以全部顶点度的和等于边数 的两倍。 定理3-3（顶点度之和与边数的关系）： 说明：
S1图的基本概念三、中国邮路问题2定理定理3-4（奇点个数奇偶性）：对于任一个图G，奇点的个数必为偶数。（偶点个数更是偶数？）证明：（度之和为奇数？偶数？取决于奇V：奇点集合点个数的奇偶性）（1）点集分解：V=V,：偶点集合（度之和为奇数？偶数？当然偶数）Zd(v)= Z d(v)+ Z d(v)=2q（2）由定理3-3：VEVvEV,VEVZ. d(v)= 2q - Z. d(v)veV,VEV,偶数偶数(3)由于奇点集合中所有奇点的度之和为偶数，所以奇点集合中所有奇点的个数必为偶数。193.中国邮路问题的求解思路
19 §1 图的基本概念 三、中国邮路问题 2. 定理 3．中国邮路问题的求解思路 定理3-4（奇点个数奇偶性）： 证明： 对于任一个图G，奇点的个数必为偶数。（偶点个数更是偶数？） （1）点集分解： 偶点集合 奇点集合 ： ： 2 1 V V V （度之和为奇数？偶数？当然偶数） （度之和为奇数？偶数？取决于奇 点个数的奇偶性） （2）由定理3-3： dv dv dv q v V v V v V 2 1 2 1 2 2 v V v V d v q d v 偶数 偶数 （3） 由于奇点集合中所有奇点的度之和为偶数， 所以奇点集合中所有奇点的个数必为偶数
S1图的基本概念三中国邮路问题3中国邮路问题的求解思路3.中国邮路问题的求解思路两种情况：（1）不存在奇点为欧拉图，以邮局为始终点的欧拉圈即为所求为非欧拉图，为形成圈，必须须在某些边上重复一次或多次，(2)存在奇点：此时，为了减少重复路线的长度，则需要考虑图中各边的权值。重复边消除奇点方法1消除奇点方法2消除奇点方法3能消除奇点的方案很多，何为最佳？求解思路：在含有奇点的赋权连通图中，增加一些边，使得在新得到的图中不含奇点，并且使得增加边的权值总和最小。204.中国邮路问题的求解方法
20 §1 图的基本概念 三、中国邮路问题 3．中国邮路问题的求解思路 4．中国邮路问题的求解方法 3.中国邮路问题的求解思路 两种情况： （1）不存在奇点：为欧拉图，以邮局为始终点的欧拉圈即为所求 （2）存在奇点： 为非欧拉图，为形成圈，必须须在某些边上重复一次或多次。 此时，为了减少重复路线的长度，则需要考虑图中各边的权值。 ? ? 消除奇点方法1 消除奇点方法2 重复边 消除奇点方法3 能消除奇点的方案很多，何为最佳？ 求解思路： 在含有奇点的赋权连通图中，增加一些边，使得在 新得到的图中不含奇点，并且使得增加边的权值总 和最小