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

文档介绍：第八章图与网络优化
图的基本概念
网络最小费用流问题
网络最大流问题
最短路径问题
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