第六章(六)中国邮递员问题

且 G 1为欧拉图， C 1为 G 1的一条欧拉回路
v1
1
•
1
1
v2
1
•
1 1 1
v3
•
1
• v4
1
• v5
• v6
G1
对路线 C 2： v1 v 4 v 2 v 4 v 5 v 3 v 6 v 5 v 2 v 3 v 2 v1 重复边：（ 2，v4），（ 2，v3） v v
v1
1
•
1
1
v2
1
•
1 1 1
• v6
结论： 对任意一个含奇点的邮路图G，由于奇点的个
数为偶数个，把每两个配成一对，由于G为连 通图，每对奇点之间至少存在一条链，对该条 链上的每一条边增加一条重复边，可得一欧拉 图，该欧拉图对应一条投递路线 寻找最佳投递路线方法： 在原邮路图上增加一些重复边得一个欧拉图，， 在所得欧拉图上找出一条欧拉回路。计算重复边 的权和，重复边权和最小欧拉回路既为所求的最 佳投递路线 管梅谷——奇偶点图上作业法
• D
类似的问题：一笔画问题
图的一笔画： 可一笔画 不可一笔画
字的一笔画：如“中、日、口、串”等可一笔画 而：“田、目”等不能一笔画
6.6.1 欧拉图与中国邮递员问题
• 欧拉道路： 一笔画问题 设G是一个无向连通图，若 存在一条道路，经过 G中的 每一条边一次且仅一次 ，则称这条道路为欧拉 道路
v3
•
1
且 G 2 为欧拉图， C 2 为 G 2的一条欧拉回路
一条投递路线对应一个 欧拉图 且投递路线为该图的一 条欧拉回路
• v4
1
• v5
• v6
G2
反之，对邮路图G，
v1
1
•
1
1
v2
1
•
1 1 1
v3
•
1
任取奇点 v 4到v3的一条链
如： v 4 , v 5 , v 6 , v 3
• v4
例：设 G为邮路图，其中 v1为邮局 ∵ d ( v 3 ), d ( v 4 )为奇数 , G 不是欧拉图
∴ G 不存在欧拉回路，
v1
1
•
1
1
v2
1
•
1 1 1
v3
•
1
• v5 v 6 • • v4 即不存在每条街道走一次且只走一次的投递路线
1
路线 C 1： v1 v 2 v 3 v 6 v 5 v 4 v1 v 2 v 3 v 5 v 2 v 4 v1 路线 C 2： v1 v 4 v 2 v 4 v 5 v 3 v 6 v 5 v 2 v 3 v 2 v1
简单回路 C 3： 1 , e7 , v5 , e 4 , v 4 , e8 , v1 } {v
v6
e6
5
v1 e1 •
e8
e7
•e
e9
v2
•e
2
G G′ 把 C 3 从 C 2的 v1点处插入 C 2，得一简单回路 C，
•5 v
e10
e4
• v4
e3
v •3
e6
v1 e1 •
e8
e7
• • v4
v2
1
• v5
• v6
v2
1
G
对该链上的每一条边增加一条重复边 v1 G ′为欧拉图 , 即 G ′存在欧拉回路
即G ′对应一条投递路线 C
C： v1 v 2 v 3 v 6 v 3 v 5 v 6 v 5 v 2 v 4 v 5 v 4 v1
•
1
1
•
1 1 1
v3
•
1
1
• v4
1
投递路线
欧拉图
G′
• v5
5
v1 e1 •
e8
v6
•e
e9
v2
e6
2
v1 e1 •
e8 e7
• • v4
v2
•e
e7
v1
8
•e
e7
•5 v
e10
e4
G
• v4
e3
v •3 v6•
e5
•5 v
e10
e4
•5 v
G′
G′′
e4
• v4
简单回路C1： 3 , e3 , v 4 , e9 , v 2 , e2 , v3 } {v 简单回路 C 2： 2 , e10 , v5 , e5 , v 6 , e6 , v1 , e1 , v 2 } {v
v2
v35
5
•
6 9
•
v5 v4
4
• • 3 3
4
•4 • 4
v9
v8
•
G2
•
•
v1
G2是欧拉图， 重复边权和=21
v2
5
•
6 9
2
v6 v5
• • 3 3
4 4 4
v7
•
v35
2、使图中每个初等圈重复边的 权和不大于该圈权和的一半 G3是欧拉图， 重复边权和=17
v •3 e
3
2
G
任取一点，如 v 3， 找一个以 v 3为起点的一个简单回路 C1 简单回路C1： 3 , e3 , v 4 , e9 , v 2 , e2 , v3 } {v
记G′ = G − C1 = V ′，E′）， ′ = E − E1，V ′是E ′中边的端点 （ E 在G ′中，以G ′与C1的公共顶点v 2为起点取一个简单回路C 2 简单回路 C 2： 2 , e10 , v5 , e5 , v 6 , e6 , v1 , e1 , v 2 } {v
例：判断下图是否为欧拉图，若是，求出欧拉回路
e1
e6
v1
•
•
•5 v
v2 e2
e4
e5
v •3
e3
v •3
e7
• v4
•5 v
}
e4
• e5 v4
e7
C1 : {v1 , e1 , v 2 , e2 , v3 , e3 , v 4 , e6 , v1
C2 :
{ v3 , e7 , v4 , e5 , v5 , e4 , v3 }
则G ′中无奇点， 所以G ′存在欧拉回路C 去掉C中的边e， 即得以vi 为起点, v j 为终点的欧拉道路
必要性：设G有一条以vi 为起点, v j 为终点的欧拉道路L
在G上增加一条边e = (vi , v j ), 得连通图G ′， 把边 e加到 L中得 G ′的一条欧拉回路 C ，即G ′为欧拉图 ∴ d ( v )为偶数 , v ∈ G ′ 在G中，d ( v i ), d ( v j )为奇数 ,
证明：必要性 已知G=（V,E)为欧拉图，即存在一条欧拉回路C， C经过G的每一条边， 由于G为连通图， 所以G中的每个点至少在C中出现一次
对∀vi ∈ V
v 若 v i 是 C 的中间点，i 每出现一次，必关联两 条边 如 C ： 1 , e1 , v 2 , e 2 , v 3 ⋯ , v i −1 , e i −1 , v i , e i , v i + 1 , ⋯ , v 1 } {v ∴ d ( v i )为偶数，即 v i 为偶点
可一笔画
不可一笔画
不可一笔画
中 日 白 田 回
不连通
6.6.2 中国邮路问题
提出问题的人：管梅谷教授 时间：1962年 提出的问题： 一个邮递员从邮局出发分送邮件，要走完他负责 投递的所有街道，最后再返回邮局，应如何选择 投递路线，才能使所走的路线最短？ 邮路问题的图论描述： 在G上找一个圈， 取一无向赋权连通图G=（V，E） 该圈过每边至少 E中的每一条边对应一条街道 一次，且圈上所 每条边的非负权l(e)=街道的长度 有边的权和最小
v 若 v i 是 C 的起点，i 也是 C 的终点， i必关联两条边 v
∴ d ( v i )为偶数 ，即 v i 为偶点
充分性： 若无向连通图G=(V,E)中无奇点，则G为欧拉图 例： G 连通，d ( v i )为偶数
v1 e1 •
e8
v6
e6
5
•e
e9
v2
•e
e7
•5 v
e10
e4
• v4
欧拉回路 :
{v1 , e1 , v 2 , e2 , v3 , e7 , v4 , e5 , v5 , e4 , v3 , e3 , v4 , e6 , v1
}
推论 无向连通图G有欧拉道路的充要条件 是G中恰有两个奇点
证明：充分性：设vi , v j 是G的奇点， 在G上增加一条边e = (vi , v j ),
•
•
v9
•
有奇点： 把所有奇点两两配成一对，每对奇点找一条链， 在该条链上的每一条边增加一条重复边，得一 个欧拉图G1， 由G1所确定的欧拉回路即为一 个可行方案 G中有奇点：v2 ，v4 ，v6 ，v8 取v2到v4的一条链： v2v1v6v7v8v9v4 取v6到v8的一条链： v6v1v2v3v4v9v8
开 链
v1 e1 •
e5
•e
v2
2
v1
•
e1 e4
•
e2
v2 v •3 •3 v e
3
•5 v
e6
e4
• v4
e3
v •3
e2
v1
•
e1 e3
•
v2
• v4
•4 vΒιβλιοθήκη 存在 v 2到v 4的 一条欧拉道路：
存在 v 3到v 4的 任两点之间都不 一条欧拉道路： 存在欧拉道路
{v2 ,e1,v1,e5,v4 ,e3,v3,e2,v2,e6 ,v5,e4,v4}