图与网络模型.ppt

图与网络模型 图与网络的基本概念 图与网络用来反映一些对象之间的关系 图论中，图与网络结构由下面两个元素构成 节点 边 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。 图与网络的基本概念 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的 无向图：边是无向的 有向图：边是有向的 如：将上述例子中“相互认识”关系改为“认识” 如：family tree 一个图结构可记作G =（V，E） V为节点集合，E为边的集合 图与网络的基本概念 路：一个节点与边相互交错的序列（vi1, ei1, vi2, ei2, …, vik-1, eik-1, vik ），其中， 对于无向图，eit的两个端点是vit-1和vit 对于有向图，eit的起点是vit-1，终点是vit 路的起点为vi1 ，路的终点为vik 圈：起点和终点是同一个节点的路 连通图：对于无向图而言，如果图中的任意两个节点都有一条路将之连接，则这个图称为连通图。 图与网络的基本概念 赋权图：对一个G的每一条边(vi, vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi, vj)上的权。 网络：在赋权的有向图G中指定一点，称为发点（vs），指定另一点称为收点（vt），其它点称为中间点，并把G中的每一条边的赋权数称为边的容量，G就称为网络。 最短路问题 对一个赋权的有向图G中的指定的两个点vs和vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小 这条路被称之为从vs到vt的最短路。这条路上所有弧的权数的总和被称为从vs到vt的距离。 Dijkstra算法 适用范围：适用于每条边上的赋权数为非负值的情况 Dijkstra算法也称为双标号法 双标号：图中的每一个节点vj都赋予两个标号（lj, kj），其中lj表示从起点vs到vj的最短路长度， kj表示在vs到vj的最短路上vj前一个节点的下标。 Dijkstra算法的基本步骤 给出点v1以标号(0, s) 找出已标号的点的集合I，没标号的点的集合J以及边的集合 查看vt是否已标号 如果vt已标号（lt, kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs 而得到。 如果vt未标号，则 如果上述边的集合是空集，则计算结束，可以断言不存在从 vs到vt的有向路。 如果上述的弧的集合不是空集，则转下一步 对上述边的集合中的每一条边，计算 sij=li+wij。在所有的sij中，找到其值为最小的边。不妨设此边为（vc, vd），则给此边的终点以双标号（scd , c）,返回步骤2。 最短路问题的例子 求下图中v1到v6的最短路 最短路问题的应用 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 最短路问题的应用 无向图可以表示成为有向图 无向图的最短路问题同样可以使用Dijkstra算法求解 最短路问题的应用 设备更新问题：某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。设备每年年初的价格表和设备维修费如下。 最短路问题的应用 解：可以转化为最短路问题。 构造一个有向图，即图中的边皆为有向的。 用vi表示“第i年年初购进一台新设备”，边（vi, vj）表示第i年年初购进的设备一直使用到第j年年初。 最短路问题的应用 所有边上的权数表 最短路问题的应用 最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1 v3 v6和 v1 v4 v6 最小生成树问题 树：图论中的重要概念，即无圈的连通图。 最小生成树问题 生成子图：给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图 生成树：如果图G的一个生成子图还是一个树，则称这个生成子图为生成树 最小生成树问题 对于一个赋权的联通的无向图，下面的问题被称为最小生成树问题： 在这个赋权联通无向图中找到一个生成树，使得该生成树的所有边的权数之和最小 对于一个有n个节点，m条边的赋权联通无向图而言 其生成树中有n个节点，n-1条边 需要删去m-n+1条边 破圈算法 基本思想： 树结构不能存在圈，故将原图结构中的所有圈打破 打破圈的方式即消去圈中的一条边 一个圈可以在多处打破，故选择消去权数较大的边 步骤：