第七章图与网络模型02489(论文资料).ppt

第七章 图与网络模型 §1 图与网络的基本概念 §2 最小生成树问题 §3 最短路问题 §4 最大流问题 §1 图与网络的基本概念 一、图的三要素 顶点无序的图为无向图。 顶点有序的图为有向图。 二、链 一个由点和边的交替序列。 三、回路(圈) 若链的第一个点和最后一个点相同，则该路为回路(圈) 。 §1 图与网络的基本概念 四、连通图 对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。 五、子图及生成子图 1．子图 设无向图G=（V、E），若 2．生成子图 §1 图与网络的基本概念 六、赋权图 对一个无向图G的每一条边(Vi,Vj)，相应地有一个数Cij，则称图G为赋权图，Cij称为边(Vi,Vj)上的权。 七、网络 在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。 §2 最小生成树问题 一、 树的概念 １、树 　　一个无圈的连通图称为树。 　　在自然科学和社会科学中有广泛的应用。如组织结构、比赛图等。 ２、生成树 　　若T是无向图G的生成子图，且T又是树，称T为G的生成树 ３、最小生成树 (Minimum SpannirngTree) 　　　就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。 §2 最小生成树问题 二、求解最小生成树的破圈算法 算法步骤： 1、在给定的赋权的连通无向图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第１步。 §2 最小生成树问题 三、应用 例、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短(单位:百米)。 §2 最小生成树问题 例 用破圈算法求图（a）中的一个最小生成树 作业: 求下图的最小树 §3 最短路问题 一、最短路问题： 　　对一个赋权的有向图D(或无向图)中指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧(或边)的权数的总和最小，这条路被称之为从Vs到Vt的最短路。 在线路安排、管道铺设、设备更新和厂区布局中有广泛的应用。 §3 最短路问题 例1 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 三、基本方法 有两个方法 １、Dijkstra法 ( 1959提出 适用：Cij≥0） 解决两指定点间的最短路或指定点到任意点的最短路。 　　 　　Dijkstra，（1930年5月11日~2002年8月6日）荷兰人。 计算机科学家。 §3 最短路问题 Dijkstra算法： ①从起点标号，标号有两个内容（aj,bj），aj表示从起点到该点的最小距离，bj表示此最小距离链的紧前一个顶点的足标。起点的标号为（0、0）。 ②从已标号的顶点出发，找出与这些已标号的顶点紧邻的所有顶点的距离，并选最小值进行标号。直到所有顶点都标号完为止。 §3 最短路问题 §3 最短路问题 §3 最短路问题 　例4：求V１至各点的最短路 §3 最短路问题 2、逐次逼近法（适用某些Cij0） 解决指定点到任意点的最短路或两指定点间最短路。 算法： 1．先赋予起点标号（0、0）及与起点邻近点的标号（Cij、1），其它标号为（∞，1） 2．检查各顶点标号是否得到最小值，否则，逐个调整。 §3 最短路问题 例6.　求 V１至各点的最短路 §3 最短路问题 §3 最短路问题 循环，路长单调下降而趋向-∞，无结果。回路上的权值之和为正数或零，可求得结果。 回路上的权值之和为负数时，此法失效。 §3 最短路问题 四、应用举例 例７ 已知某地区的交通网络如下图所示,其中点代表居民小区,边表示公路,问区中心医院应建在哪个小区,可使离医院最远的小区居民就诊时所走的路程最短。 §3 最短路问题 §3 最短路问题 §4 最大流问题 在交通运输、物资供应中，经常会遇到人流、车流、信息流、物流、现金流，称“网络流理论”。二十世纪中叶以后， Ford和Fulkerson建立了网络流理论。 一、最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。 §4 最大流问