运筹学PPT 第五章图与网络分析课件.ppt

《运筹学PPT 第五章图与网络分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图与网络分析第一节图的基本概念第二节网络分析2021/9/14第一节图的基本概念1.图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4如G：简单图：无环、无多重边的图。2021/9/142.关联与相邻3.链与圈2021/9/144.有向图与无向图，圈，回路比较：2021/9/14v1v2v3v4v5链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：2021/9/145.树例1已知有5个城市，要在它们之间架设电话

2、线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4特点：连通、无圈。树：无圈的连通图，称为树，记为T。2021/9/14v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有m个顶点，则T有m-1条边。2021/9/146.图的部分（支撑）树若图G=（V，E）的子图T=（V，E’）是树，则称T为G的部分树或支撑树。特点——边少、点不少。性质：G连通，则G必有部分树。2021/9/

3、14第二节网络分析网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}，ci为边ei上的权（设ci）。网络分析主要内容最小部分树问题最短路问题最大流问题图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，E，C)。又称为网络。2021/9/14一.最小部分（支撑）树问题问题：求网络D的部分树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例1求如图网络的最小部分树。v5v1v3v6v4v2v72552335757112021/9/141.破圈法：在图

4、中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v53.57.54232021/9/141.破圈法：在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v53.54232021/9/141.破圈法：在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.54232021/9/141.破圈法：在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.5232021/9/14[例]今有煤气站

5、A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222254526345312021/9/14[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222224526345312021/9/1

6、4[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222526345312021/9/14[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531202

7、1/9/14[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS22222226345312021/9/14[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS2222222345312021/9

8、/14[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元2021/9/14案例分析：默登公司的联网问题默登（Modern）公