《运筹学教程课件六 图与网路分析》由会员分享，可在线阅读，更多相关《运筹学教程课件六 图与网路分析（44页珍藏版）》请在金锄头文库上搜索。
1、第六章 图与网路分析,图是最直观的模型,1,图论 Graph Theory,哥尼斯堡七桥问题 (Knigsberg Bridge Problem) Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理 很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联,2,6.1 图与网路的基本概念,6.1.1图与网路 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V=v1,v
2、2, vn 边集E=eij ,网路 (Network) 边上具有表示连接强度的权值，如 wij 又称加权图(Weighted graph),3,6.1.2 无向图与有向图,边都没有方向的图称为无向图，如图6.1 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图,4,6.1.3 端点，关联边，相邻，次,图中可以只有点，而没有边；而有边必有点 若节点vi, vj 之间有一条边 eij，则称 vi, vj 是
3、 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge) 同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边 一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(parallel edges) 既没有自环也没有平行边的图称为简单图(simple graph) 在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph),6.1.3 端
4、点，关联边，相邻，次,有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 定理 1：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路 相邻节点的序列 v1 ,v2 , vn 构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走 在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directed path)
5、首尾相连的路径称为回路(circuit)；,6,6.1.4 链，圈，路径，回路，连通图,走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.4 连通图，子图，成分 设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1， 则 G2 是 G1 的子图 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分 (component) 链，圈，路径(简称路)，回路都是原图的子图 平面图(pla
6、nar graph)，若在平面上可以画出该图而没有任何边相交,7,6.2 树图与最小生成树,一般研究无向图 树图：倒置的树，根(root)在上，树叶(leaf)在下 多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图,8,6.2.1 树的定义及其性质,任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： 最少边的连通子图，树中必不存在回路 任何树必存在次数为 1 的点 具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点， n1 条边的连通图必是一棵树 6.2.2 图的生成树 树 T 是连通图 G 的生成树(spanning tree
7、)，若 T 是 G的子图且包含图 G 的所有的节点；包含图 G 中部分指定节点的树称为 steiner tree 每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeled tree) Caylay 定理：n (2)个节点，有nn2个不同的标记树,9,6.2.2 图的生成树,如何找到一棵生成树 深探法(depth first search)：任选一点标记为 0 点开始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从最新标记的点向下搜索，若从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退回到 i 1 点继
8、续搜索，直到所有点都被标记 广探法(breadth first search)：是一种有层级结构的搜索，一般得到的是树形图,10,6.2.3 最小生成树,有n 个乡村，各村间道路的长度是已知的，如何敷设光缆线路使 n 个乡村连通且总长度最短 显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法： Kruskal 算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n1 条边，则 T 是最小生成树 Kruskal 算法基于下述定理 定理 3 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，则关联边 eij 必
9、在某个最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。,11,6.2.3 最小生成树,选边法：将连通图中所有边权从小到大排列，在保证不构成回路的条件下，依次选所剩最小边，直到所有节点连通为止。 破圈法：将连通图中所有边权从大到小排列，在保证不破坏连通的条件下，依次去掉剩余最大边破圈，直到没有回路为止。 Prim 算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩阵上的 Prim 算法： 1、根据网路写出边权矩阵，两点间若没有边，则用表示； 2、从 v1 开始标
10、记，在第一行打 ，划去第一列； 3、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 ； 4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第 3 步。 该算法中，打 行对应的节点在 V1中，未划去的列在 V2中,12,6.2.3 最小生成树,Prim算法是多项式算法 Prim算法可以求最大生成树 网路的边权可以有多种解释，如效率,13,6.3 最短路问题,6.3.1 狄克斯特拉算法 (Dijkstra algorithm, 1959) 1、令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间没有边，则令
11、dij = ，若两点之间是有向边，则 dji = ；令 dii = 0，Li j表示节点vi到节点vj 的最短路径长，s 表示始点，t 表示终点； 2、从始点S出发，因为L S S =0，将0填入节点S旁的小方框内，表示节点S已标号，令SV，其余节点属于V，即其余节点均未标号； 3、找出与已标号节点相邻的所有未标号节点，在这些未标号节点中，选取一个与始点S距离最短的节点vj1，即计算,上式中，r为已标号节点下标，j为与已标号节点相邻的未标号节点的下标，j1为下一个要标号的节点下标。 4、将LS j1填入节点vj1旁的小方框内，表示节点vj1已标号，令vj1V，并从集合V中去掉节点vj1； 5、
12、重复步骤3、4，直到所有节点均已标号或标号无法进行下去为止。,14,例1 狄克斯特拉算法,按照Dijkstra算法，先将0填入节点S旁的小方框内，然后，依次选择与始点S距离最近的节点vj1进行标号，并把该距离LS j1填入节点vj1,旁的小方框内。依次选择离始点S最近的节点的顺序分别为v4, v2, v5, v3, v6, vt, 最短路径为S256t，长度为28。,准则1：每次选择离始点S最近的未标号节点进行标号； 准则2：每次将已标号节点做最小延伸，并比较取其中最小的一个延伸所到达的节点进行标号。 显然，准则1概念较清晰，而准则2较容易手工操作。,15,Dijkstra最短路算法的特点和适
13、应范围,一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij0，第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有n1 次迭代 可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标记为 ，则表明 vs 到该节点无有向路径 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束了；但算法复杂度是一样的 应用 D
14、ijkstra 算法 n1 次 ，可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树，但不是最小生成树,16,6.3.2 Warshall-Floyd算法 (1962),Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题; 基于思路：如果节点vS到节点vj的最短路径总是沿着某一特定的路径先到达节点vi,然后再沿边（vi，vj）到达节点vj，则这一特定路径肯定也是节点vS到节点vi的最短路径。 迭代公式,若对于所有节点vjV，均满足,则停止迭代，并通过反向追踪寻找vS到节点vj的最短路径。,17,例 6.3.2 求下图具有负权网络图始点v1到终点v 8的最短路径及其长
15、度。,18,19,6.3.4 最短路应用举例市话扩容 (实装率=0.8),20,最短路应用举例 市话扩容,21,小结,最短路有广泛的应用 (6.3.4节 市话局扩容方案) 最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，k-最短路等 当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活 若图是前向的，则Dijkstra算法也可以求两点间最长路 一般情况下，两点间最长路是 NP-complete，但最短路是 P算法 两点间k-最短路：分为边不相交的和边相交的 求边不相交的k-最短路非常容易：先求最短路，将该
16、最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推,22,6.4 网路的最大流和最小截,6.4.1 网路的最大流的概念 网路流一般在有向图上讨论 定义网路上支路的容量为其最大通过能力，记为 cij ，支路上的实际流量记为 fij 图中规定一个发点s，一个收点t 节点没有容量限制，流在节点不会存储 容量限制条件：0 fij cij 平衡条件：,满足上述条件的网路流称为可行流，总存在最大可行流 当支路上 fij = cij ，称为饱和弧 最大流问题也是一个线性规划问题,23,6.4.2 截集与截集容量,定义：把网路分割为两个成分的弧的最小集合，其中一 个成分包含 s 点，另一个包含 t 点 。 一般包含 s 点的成分中的节点集合用V表示，包含 t 点的成分中的节点集合用V 表示 截集容量是指截集中正向弧的容量之和,福特-富克森定理：网路的最大流等于最小截集容量,24,6.4.3 确定网路最大流
