6.4.5以最短路为基础汇总网路上的流 ① 电路交换网 传输网 4 ④⑤ 在电路网中每两点之间都有中继电路群需求,但并不是任 两点都有物理传输链路 根据两点间最短传输路径将该两点间的电路需求量加载到 这条传输路径上去:设a25=10是节点2和5之间的电路需 求,节点2和5之间的最短传输路径为2-1-3-5,则加载过 程为:T2=T21+10,T3=T13+10,735=73+10;T是传输链路 ij上加载的电路数;当所有点间电路都加载完则算法结束
6.4.5 以最短路为基础汇总网路上的流 1 2 3 4 5 电路交换网 1 2 3 4 5 传输网 • 在电路网中每两点之间都有中继电路群需求，但并不是任 两点都有物理传输链路 • 根据两点间最短传输路径将该两点间的电路需求量加载到 这条传输路径上去：设 a25=10 是节点2 和 5 之间的电路需 求，节点2 和 5 之间的最短传输路径为 2−1−3−5，则加载过 程为: T21=T21+10, T13=T13+10, T35=T35+10； Tij 是传输链路 i−j 上加载的电路数；当所有点间电路都加载完则算法结束
6欧拉回路和中国邮递员问题 中国邮递员问题( Chinese postman problem,CPP)是由我国 管梅谷教授于1962年首先提出并发表的 问题是从邮局出发,走遍邮区的所有街道至少一次再回到 邮局,走什么路由才能使总的路程最短? 如果街区图是一个偶图,根据定理3,一定有欧拉回路 CPP问题也就迎刃而解了 若街区图不是偶图,则必然有一些街道要被重复走过才能 回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 E 匹配( minimum weighted mtch)-由 emmons给出 多项式算法(1965) B
6.5 欧拉回路和中国邮递员问题 • 中国邮递员问题(Chinese Postman Problem, CPP)是由我国 管梅谷教授于1962年首先提出并发表的 • 问题是从邮局出发，走遍邮区的所有街道至少一次再回到 邮局，走什么路由才能使总的路程最短？ • 如果街区图是一个偶图，根据定理 3，一定有欧拉回路， CPP 问题也就迎刃而解了 • 若街区图不是偶图，则必然有一些街道要被重复走过才能 回到原出发点 • 显然要在奇次点间加重复边 • 如何使所加的边长度最少 • 归结为求奇次点间的最小 匹配( minimum weighted match) — 由Edmons 给出 多项式算法(1965) A B C D
解中国邮递员问题的步骤 0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3、根据最小完全匹配和最短路径添加重复边 将悬挂点逐一恢复,并加重复边 5、根据得到的偶图,给出欧拉回路的若干种走法 ③2⑥4⑨ ①6④4⑦2@①
解中国邮递员问题的步骤 0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3、根据最小完全匹配和最短路径添加重复边 4、将悬挂点逐一恢复，并加重复边 5、根据得到的偶图，给出欧拉回路的若干种走法 1 3 2 4 5 9 8 7 6 0 5 5 4 3 4 4 2 4 6 6 2 1 3 2 4 5 9 8 7 6 5 5 4 3 4 4 2 4 6 6
解中国邮递员问题的步骤 2468 468 0107102 535 2468 07 55,7 0 870 468 5,9 最短距离矩阵 转接矩阵 ③264⑨添③6 3 加重 ⑤48复 ④8 找出所有基本 边 回 ①6447,0①40路
解中国邮递员问题的步骤 2 4 6 8 2 - 5 3 5 4 - 5 5,7 6 - 5,9 8 - 转接矩阵 2 4 6 8 2 0 1 0 7 1 0 4 0 7 8 6 0 7 8 0 最短距离矩阵 1 5 9 5 5 4 3 4 4 2 4 6 6 2 1 2 4 5 6 9 0 8 4 7 6 2 3 0 3 8 7 添 加 重 复 边 找 出 所 有 基 本 回 路
6.6哈密尔顿回路及旅行推销员问题 6.6,1哈密尔顿回路( Hamiltonian circuil) 连通图G(V,E中的回路称为哈密尔顿回路,若该回路包括图中 所有的点。显然哈密尔顿回路有且只有n条边,着n 连通图具有哈密尔顿回路的充分必要条件是什么?这个问题是 由爱尔兰数学家哈密尔顿1859年提出的,但至今仍未解决 欧拉回路是对边进行访问的问题,哈密尔顿回路是对点进行访 问的问题 ·搜索哈密尔顿回路的难度是NP- complete 任两点间都有边的图称为完全图(或全连接图) 完全图中有多少个不同的哈密尔顿回路?(m-1)!2 完全图中有多少个边不相交的哈密尔顿回路?(m-1)/2 最小哈密尔顿回路问题(NP- complete) 哈密尔顿路径:包含图中所有点的路径 为什么说找两点间的最长路是非常困难的问题?
6.6 哈密尔顿回路及旅行推销员问题 6.6.1 哈密尔顿回路( Hamiltonian circuit) • 连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中 所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=n • 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是 由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决 • 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访 问的问题 • 搜索哈密尔顿回路的难度是 NP-complete • 任两点间都有边的图称为完全图(或全连接图) • 完全图中有多少个不同的哈密尔顿回路？ • 完全图中有多少个边不相交的哈密尔顿回路？ • 最小哈密尔顿回路问题 (NP-complete) • 哈密尔顿路径：包含图中所有点的路径 • 为什么说找两点间的最长路是非常困难的问题？ (n−1)!/2 (n−1)/2