图与网络分析-(精选·公开·课件).pptVIP

第6章 图与网络分析 图与子图 图的连通性 树与支撑树 最小树问题 最短有向路 最大流问题 §6.1 图与子图 无向图基本概念 有向图基本概念 关联矩阵和邻接矩阵 主要结论 子图 1 树 例 已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。 v6 v3 v4 v2 v5 v1 v6 v3 v4 v2 v5 v1 1 树 树 连通且无回路的图称为树，用T表示。 T中次为1的点称为叶子，次数大于1的点称为分支点或内点。 1 树 森林 非连通且每个连通分支是树的图。 平凡图也是树称为平凡树。 2 树的基本性质 1、T是连通且无回路(即T是树)。 2、T无回路且m=n-1。 3、T连通且m=n-1。 4、T无回路,但增加一边 后得到且仅得一个回路。 5、T连通,但删去任一边后就不连通 。 6、每一对结点间有且仅有一条通路。 给定图T=V,E, |V|=n,|E|=m 。以下关于树的命题是等价的。 v6 v3 v4 v2 v5 v1 定理6.3.2 非平凡树至少有两个次为1的点。 如果T恰好有两个次为1的点，则其他的点的次必都为2，因此，T是一条路。 2 树的基本性质 3 支撑树 图G的一个支撑子图T如果是树，则称T为G的一个支撑树。 设T=(V,E’)是G=(V,E)的一个支撑树，称T*=G\T为G的反树。 v6 v5 v2 v3 v4 v1 图G中属于生成树的边称为树枝，不在生成树中的边称为弦。 v6 v5 v2 v3 v4 v1 给定图G，给出G的一个支撑树T？ 3 支撑树 4 支撑树的基本性质 支撑树存在定理 任何连通图G至少有一棵支撑树。 推论 ： 1、设n阶简单连通图G中有m条边，则m≥n-1。 2、设n阶无向连通图G中有m条边，T是G的一棵支撑树，T*是T的反树，则T*有m-n+1条边。 水源 某农场的水稻田用堤埂分割成很多小块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少条堤埂，才能使水浇灌到每小块稻田？ 4 支撑树的基本性质 §6.4 最小树问题 最小树问题 最小树问题的求解 1 最小树问题 设N=V, E, W是一带权连通图,G的支撑树T的权w(T)就是T的边上的权和. 最小树 在网络G的所有生成树中,权最小的那棵树称为G的最小生成树。 a b f d e c 2 2 4 2 5 6 3 4 5 最小树 2 最小树问题的求解 v3 v2 1 v4 2 v5 3 v6 4 v1 5 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 避圈法（Kruskal算法）：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。 2 最小树问题的求解 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。 2 最小树问题的求解 反圈法 Step 1 从图G中任取一点vi, 让vi?S, 其余各点均包含在S’=V\S中。 Step 2 从（S,S’)中选一条权最小的边e=vivj，加到T中。 Step 3 令S ? vj?S, S’\vj?S’，(将所选边的另一个顶点添加到S中）。 Step 4 重复2、3两步，直到图中所有点均包含在S中为止。 v1 v5 v4 v3 v2 1 2 2 4 3 2 4 4 v1 v5 v4 v3 v2 1 2 2 4 3 2 4 4 2 最小树问题的求解 2 最小树问题的求解 v1 v5 v4 v3 v2 1 2 2 4 3 2 4 4 v1 v5 v4 v3 v2 1 2 2 4 3 2 4 4 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 2 最小树问题的求解 练习：某工厂有6个车间，水管把它们连接起来，已知这6个车间的位置、可供铺设管线的地方及车间之间的距离如下图所示，问自来水管线怎样铺设才能使管线总长最省？ 6 1 5 2 7 8 2 4 4 2 最小树问题的求解 v3 v5 v1 v6 v2 v4 最短有向路问题 最短有向路问题的求解 §6.5 最短有向路问题 什么是最短有向路？ v6 v5 v3 v1 v4 v2 3 6 5 1 1 2 4 3 6 给定有向网络N=(V,A,W)，设P为G的一条有向路，令 在有向路P中的弧的权重的和 则称W(P)为P的权(或长)。 G中从点i到点j的权最小的有向路称为最短有向路。 1 最短有向路问题 2 最短有向路问题的求解 下面仅介绍在一个赋权有向图中寻求最短路的方法——Dijkstra算法，它是在1959年提出来的。目前公认，