第十章 图与网络分析

第十章图与网络分析 2 图的基本概念最小支撑树最短路问题网络系统最大流问题网络系统中的最小费用最大流问题中国邮递员问题 3 一 图的基本概念 哥尼斯堡七桥问题 K nigsbergBridgeProblem LeonhardEuler 1707 1783 在1736年发表第一篇图论方面的论文 奠基了图论中的一些基本定理 4 图与网路的基本概念 图 Graph 节点和边的集合一般用G V E 表示点集V v1 v2 vn 边集E eij 5 无向图与有向图 边都没有方向的图称为无向图当边都有方向时 称为有向图 在有向图中 有向边又称为弧图中既有边又有弧 称为混合图 6 链 圈 路 回路相邻节点的序列 v1 v2 vn 构成一条链 link 首尾相连的链称为圈 loop 在有向图中 链中每条边的方向和链的方向一致 将该链称为路径 path 首尾相连的路称为回路 circuit 7 二 树与最小支撑树 树 无圈的连通图管理的指标体系 家谱 分类学 组织结构等都是典型的树图 8 图的支撑树 图 图的支撑树 9 避圈法 破圈法 A B C D E F 6 5 5 1 7 2 3 4 4 10 三 最短路问题 V1 V2 V3 V4 V6 V5 V7 8 2 6 2 3 8 6 3 9 5 4 11 狄克斯特拉算法 Dijkstraalgorithm 1959 计算两节点之间或一个节点到所有节点之间的最短路令dij表示vi到vj的直接距离 两点之间有边 若两点之间没有边 则令dij 若两点之间是有向边 则dji 令dii 0 s表示始点 t表示终点0 令始点Ts 0 并用 框住 所有其它节点临时标记Tj 1 从vs出发 对其相邻节点vj1进行临时标记 有Tj1 ds j1 2 在所有临时标记中找出最小者 并用 框住 设其为vr 若此时全部节点都永久标记 算法结束 否则到下一步 3 从新的永久标记节点vr出发 对其相邻的临时标记节点进行再标记 设vj2为其相邻节点 则Tj2 min Tj2 Tr dr j2 返回第2步 12 Dijkstra最短路算法的特点和适应范围 一种隐阶段的动态规划方法每次迭代只有一个节点获得永久标记 若有两个或两个以上节点的临时标记同时最小 可任选一个永久标记 总是从一个新的永久标记开始新一轮的临时标记 是一种深探法被框住的永久标记Tj表示vs到vj的最短路 因此要求dij 0 第k次迭代得到的永久标记 其最短路中最多有k条边 因此最多有n 1次迭代可以应用于简单有向图和混合图 在临时标记时 所谓相邻必须是箭头指向的节点 若第n 1次迭代后仍有节点的标记为 则表明vs到该节点无有向路径如果只求vs到vt的最短路 则当vt得到永久标记算法就结束了 但算法复杂度是一样的应用Dijkstra算法n 1次 可以求所有点间的最短路vs到所有点的最短路也是一棵生成树 但不是最小生成树 13 四 网络系统的最大流问题 网络系统最大流的概念定义网路上支路的容量为其最大通过能力 记为cij 支路上的实际流量记为fij容量限制条件 0 fij cij平衡条件 满足上述条件的网路流称为可行流 14 确定网路最大流的标号法 从任一个初始可行流出发 如0流基本算法 找一条从s到t点的增广链 augmentingpath 若在当前可行流下找不到增广链 则已得到最大流增广链中与s到t方向一致的弧称为前向弧 反之后向弧增广过程 前向弧f ij fij q 后向弧f ij fij q增广后仍是可行流 15 五 最小费用最大流 双权网路 每条弧不但有容量 还有单位流量的通过费用两种解法 一种基于最小费用路径算法 一种基于可行弧集的最大流算法基于最小费用路径算法 总是在当前找到的最小费用的路径上增广流 缺点是每次增广后要改变弧的费用 且出现负权值费用的弧基于可行弧集的最大流算法 从0费用弧集开始应用最大流算法 然后根据计算信息提高费用的限界P 使可行弧集增大 再应用最大流算法 直至所有弧都进入可行弧集 这种算法是一种主 对偶规划的解法 使用这种方法的还有运输问题 匹配问题 16 6 4 5以最短路为基础汇总网路上的流 在电路网中每两点之间都有中继电路群需求 但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去 设a25 10是节点2和5之间的电路需求 节点2和5之间的最短传输路径为2 1 3 5 则加载过程为 T21 T21 10 T13 T13 10 T35 T35 10 Tij是传输链路i j上加载的电路数 当所有点间电路都加载完则算法结束 17 6 5欧拉回路和中国邮递员问题 中国邮递员问题 ChinesePostmanProblem CPP 是由我国管梅谷教授于1962年首先提出并发表的问题是从邮局出发 走遍邮区的所有街道至少一次再回到邮局 走什么路由才能使总的路程最短 如果街区图是一个偶图 根据定理3 一定有欧拉回路 CPP问题也就迎刃而解了若街区图不是偶图 则必然有一些街道要被重复走过才能回到原出发点显然要在奇次点间加重复边如何使所加的边长度最少归结为求奇次点间的最小匹配 minimumweightedmatch 由Edmons给出多项式算法 1965 18 解中国邮递员问题的步骤 0 将图中的所有悬挂点依次摘去1 求所有奇次点间的最短距离和最短路径2 根据奇次点间的最短距离求最小完全匹配3 根据最小完全匹配和最短路径添加重复边4 将悬挂点逐一恢复 并加重复边5 根据得到的偶图 给出欧拉回路的若干种走法 19 解中国邮递员问题的步骤 20 6 6哈密尔顿回路及旅行推销员问题 6 6 1哈密尔顿回路 Hamiltoniancircuit 连通图G V E 中的回路称为哈密尔顿回路 若该回路包括图中所有的点 显然哈密尔顿回路有且只有n条边 若 V n连通图具有哈密尔顿回路的充分必要条件是什么 这个问题是由爱尔兰数学家哈密尔顿1859年提出的 但至今仍未解决欧拉回路是对边进行访问的问题 哈密尔顿回路是对点进行访问的问题搜索哈密尔顿回路的难度是NP complete任两点间都有边的图称为完全图 或全连接图 完全图中有多少个不同的哈密尔顿回路 完全图中有多少个边不相交的哈密尔顿回路 最小哈密尔顿回路问题 NP complete 哈密尔顿路径 包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题 n 1 2 n 1 2 21 6 6 2旅行推销员问题 TravelingSalesmanProblem 旅行推销员问题 TSP 设v1 v2 vn为n个已知城市 城市之间的旅程也是已知的 要求推销员从v1出发 走遍所有城市一次且仅一次又回到出发点 并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题一般旅行推销员问题 GTSP 允许点重复的TSP当网路边权满足三角不等式时 一般旅行推销员问题就等价于最小哈密尔顿回路问题当网路边权不满足三角不等式时 只要用两点间最短路的距离代替原来的边权 就可以满足三角不等式 在此基础上求最小哈密尔顿回路典型的应用 乡邮员的投递路线邮递员开邮箱取信的路线问题邮车到各支局的转趟问题 22 TSP的启发式算法 Heuristicalgorithm 穷举法 指数算法分支定界法 隐枚举法二交换法 two option Lin salgorithm 哈密尔顿回路可以用点的序列表示从任一个哈密尔顿回路 即任何一个序列 出发按照一定顺序试图交换相邻两个点的顺序 若路程减少则完成交换 继续下一个交换 若没有改善 则不进行本次交换 尝试下一个交换 若所有的相临交换都试过而不能改善 则算法结束 得到一个局部最优点模拟退火 SimulatedAnnealing 随机地采用二交换法当交换后没有使目标函数改善 也可能以玻尔兹曼分布概率被接受 但这种概率是随模拟的温度下降而减少的发挥了计算机的优点 尽量减少陷入局部极值点模拟物理机制 23 二交换法举例 初始解 1 2 3 4 5 1 3 2 4 5 1 3 2 4 5 1 3 4 2 5 1 3 4 2 5 1 3 4 5 2 5 3 4 2 1 3 1 4 2 5 24 算法复杂度 Prim算法i 1n 1次比较 最多n 1次赋值i 22 n 2 次比较 最多2 n 2 次赋值i kk n k 次比较 最多k n k 次赋值 Dijkstra算法i 1n 1次临时标记 永久标记n 1次比较和赋值i 2n 2次临时标记 永久标记n 2次比较和赋值i kn k次临时标记 永久标记n k次比较和赋值 25 Prim算法的改进 增加一个辅助记录型数组 用以记录当前V中各节点到V的最小边 minedge i cost记录该边的权值 minedge i vex记录该边V中的顶点 若minedge i cost0 and minedge j cost mi thenbegink j mi minedge j costend minedge k cost minedge k cost 找到k 将k加入集合V forj 2tondoif w k j minedge j cost thenbeginminedge j cost w k j minedge j vex k end end 该算法复杂度约为5n n 1 26 匹配问题 MatchingProblem 定义 图中一组边的集合 当图中的每个节点最多只与该集合中的一条边相关联 则该边集就成为匹配 1 两部图的匹配问题图中的节点可分为两个集合 X Y X与Y之间有边相连 但X内部和Y内部无关联边 称为两部图运输问题实际上是两部图的最小费用最大流问题任务分配问题实际上是两部图的最小完全匹配问题2 非两部图的匹配问题 1 最大基数匹配 maximumcardinalitymatching 2 最大权匹配 maximumweightmatching 3 最小完全匹配 minimumweightperfectmatching 4 最优分数匹配 optimalfractionalmatching 27 任务分配问题 匹配问题和TSP的关系 三个问题都有一个n n正权值的边权矩阵三个问题的解都可以用代数置换 permutation 表示 i1 i2 i3 i4 i5是1 2 3 4 5的任一排列 表示元素位置的交换轮换 全轮换 对换TSP的解必须是一个全轮换任务分配问题的解可以是任一个置换匹配的解必须是n 2个对换任务分配问题是匹配问题的松弛问题 28 6 7选址问题 使所选地址到最远的服务对象距离尽可能小 中心点使所选地址到各服务对象的总距离最小 中位点 有时间限制的多用中心点 如乡邮局总资源约束的多用中位点 如电话交换局6 7 1各点之间的距离节点到节点间的最短距离 称为节点 节点距离边上某点到节点的最短距离 称为点 节点距离节点到某边上最远一点的距离 称为节点 边距离边上一点到另一边上最远点的距离 称为点 边距离 29 1 边上某点到节点的最短距离dij代表vi与vj间的最短距离 ars代表边 r s 的边长 令h为边 r s 上一点的百分位 0 h 1边上对应h的一点到vj的最短距离为d h r s j min h ars drj 1 h ars dsj 2 节点到某边上最远一点的距离指定节点j 它到边 r s 上对应h百分位点有两条路 最远点必使两条路一样长 故有d j r s 0 5 djr djs ars 3 边上指定一点到其他边上最远点的距离h是边 r s