下载此文档

运筹学8-图(天津理工大学经管系)技术方法.ppt

文档分类：高等教育 | 页数：约81页举报非法文档有奖

1/81

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/81 下载此文档

文档列表 文档介绍

第八章图与网络优化
图的基本概念
网络最小费用流问题
网络最大流问题
最短路径问题
Konigsberg(哥尼斯堡)七桥问题
问题:能否从河岸或小岛出发,通过每一座桥,而且仅仅通过一次回到原地。
图论简介
例:A、B、C、D四个班进行足球比赛,如图
简单图
在图中某个边的两个端点相同,则称之为环;若两点之间有多余一条的边,称之为多重边。
一个无环、无多重边的图称为简单图。一个无环、有多重边的图称为多重图。
v4
v2
v3
v1
路径(Path)
有向图中前后相继并且方向相同的边序列
P={(v1,v2),(v2,v3),(v3,v4)}
v1
v2
v3
v4
e1
e2
e7
e6
e5
e4
e3
例
回路(Circuit)
起点和终点重合的路径称为回路
μ={(1,2),(2,4),(4,1)}
回路中各条边方向相同
4
2
3
1
链(Chain)
无向图中前后相继的点边序列称为链
C={v1,e1,v2,e5,v3}
v1
v2
v3
v4
e2
e6
e5
e4
e3
e1
e7

运筹学8-图(天津理工大学经管系)技术方法来自淘豆网www.taodocs.com转载请标明出处.