第11章 图与网络模型2008.ppt

第十一章 图与网络模型 网络的基本概念 最短路径问题 最小生成树问题 最大流问题 最小费用最大流问题 §1.图与网络的基本概念 图论中常用的名词 图 子图和生成子图 网络图 链、路、圈和回路 连通图 简单图 一、图：无向图 一、图：无向图 有向图 有向图: 二、子图与生成子图 三、网络图 各边赋予一定的物理量，例如距离，则叫做网络图。 所赋予的物理量叫做权。 权可以是：距离、时间、成本、容量等 四、链、圈、路、回路 初等链：在无向图中，顶点和边相互交替出现的点不重复序列。 圈：起点和终点相同的链叫做圈。 路：在有向图中，点弧交错，方向和链的走向一致的链。即前后相继并且方向相同的边序列 P={v1,(1,2),V2,(2,3),v3,(3,4)} 回路：起点和终点相同的路叫做回路。 五、连通图和简单图 连通图：在图中，任意两点之间至少有一条链相连，叫做连通图。否则是非连通图。 非连通图可以由几个连通图构成。 环、多重边 简单图：没有环和多重边的图是简单图。 不连通图 什么是树？ 构造生成树的方法 最小生成树问题 寻找最小生成树的方法 一、什么是树？ 树：无圈的连通图或 不含圈的连通图 一、什么是树？ 树的基本性质 任意两点之间有且只有一条链 若树有p个顶点，则共有q=p-1条边 若图是连通的，且q=p-1，则该图不含圈，因此是树 若图不含圈，且q=p-1，则该图连通的，因此是树。 二、求解最小生成树的破圈法 最小生成树:在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小. 二、求解最小生成树的破圈法 最小生成树:在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小. 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 二、求解最小生成树的破圈法 避圈法 三、应用举例 最小生成树的数学模型 四、寻找最小生成树的方法 Kruskal方法 破圈法 矩阵计算法 Kruskal方法 矩阵计算方法 矩阵计算方法 矩阵计算方法 矩阵计算方法 矩阵计算方法 矩阵计算方法 矩阵计算结果 习题 P. 253 第11章习题1、2。 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 已求得最大流 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 第4节 网络最大流问题 P233 第5题 找到所有的不饱和边，以及各边可以调整流量的方向 2 3 5 4 6 7 1 f=0 f=0 6 2 4 3 7 4 3 1 7 9 8 8 0 0 0 0 0 0 0 0 0 0 0 0 2 3 5 4 6 7 1 f=0 f=0 6 2 4 3 7 4 3 1 7 9 8 8 0 0 0 0 0 0 0 0 0 0 0 0 链的间隙为：? = min{8,6,9}=6 调整链的流量：xij’=xij+ ?; pf=0+6 ?=6 ?=9 ?=8 2 3 5 4 6 7 1 f=6 f=6 0 2 4 3 7 4 3 1 7 3 8 2 6 0 0 0 0 0 0 6 0 0 0 6 2 3 5 4 6 7 1 f=6 f=6 0 2 4 3 7 4 3 1 7 3 8 2 6 0 0 0 0 0 0 6 0 0 0 6 2 3 5 4 6 7 1 f=6 f=6 0 2 4 3 6 4 3 0 7 3 6 2 6 0 0 1 0 0 0 6 1 1 0 6 2 3 5 4 6 7 1 f=7 f=7 0 2 4 3 6 4 3 0 7 3 6 2 6 0 0 1 0 0 0 6 1 1 0 6 2 3 5 4 6 7 1 f=10 f=10 0 2 4 3 3 1 0 0 7 3 3 2 6 0 3 4 0 3 0 6 4