C类运筹学 第5章 图和网络.pptVIP

6.1 图与网路的基本概念; 无向图与有向图; 端点，关联边，相邻，次;有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d– 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 定理 1：图中奇点的个数总是偶数个 链，圈，路径，回路，欧拉回路 相邻节点的序列 {v1? ,v2? ,…, vn?} 构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走 在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directed path) 首尾相连的路径称为回路(circuit)；;走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 2：偶图一定存在欧拉回路(一笔画定理) 设有两个图 G1(V1, E1), G2(V2, E2), 若V2 ?V1, E2 ?E1， 则 G2 是 G1 的子图 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( disconnected graph)；非连通图中的每个连通子图称为成分 (component) 链，圈，路径(简称路)，回路都是原图的子图;6.2 树图与最小生成树; 6.2.1 树的定义及其性质; 6.2.2 图的生成树; 6.2.3 最小生成树; 6.2.3 最小生成树; 6.2.3 最小生成树;通过一个网络的最短路径; 狄克斯特拉算法 (Dijkstra algorithm, 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步。;例狄克斯特拉算法; Dijkstra算法的特点和适应范围; Warshall-Floyd算法 (1962); Floyd-Warshall 算法 (1962);小结; 6.3.4 最短路应用举例——市话扩容 (实装率=0.8);最短路应用举例 —市话扩容;通过一个网络的最大流量;基本概念;网路的最大流-网路的最大流的概念; 6.4.2 截集与截集容量; 确定网路最大流的标号法; 最大流最小截的标号法步骤; 最大流最小截的标号法步骤;最大流最小截集的标号法举例;最大流最小截集的标号法举例; 最大流标号法的复杂度讨论; 多端网路问题; 最小费用最大流; 6.4.5 以最短路为基础汇总网路上的流;6.5 欧拉回路和中国邮递员问题; 解中国邮递员问题的步骤; 解中国邮递员问题的步骤;6.6 哈密尔顿回路及旅行推销员问题; 6.6.2 旅行推销员问题(Traveling Salesman Problem);6.7 选址问题;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)上指定的百分位点，另一边为(u, t) d[h(r, s), (u, t)]=min[h?ars+d[r, (u, t)], (1?h)?ars+d [s, (u, t)] ]; 6.7.2 中心的选择; 例6.7.1~6.7.2