运筹学8-图(天津理工大学经管系)复习课程.ppt

文档介绍：第八章图与网络优化
图的基本概念
网络最小费用流问题
网络最大流问题
最短路径问题
Konigsberg(哥尼斯堡)七桥问题
问题:能否从河岸或小岛出发,通过每一座桥,而且仅仅通过一次回到原地。
图论简介
例:A、B、C、D四个班进行足球比赛,如图
图的基本概念
节点与(有向)边
每一条边和两个节点关联,一条边可以用两个节点的标号表示:弧记为e=(vi ,vj);边记为e=[vi ,vj]。
称vi与vi相邻,e与vi,vj相关联。
vj
vi
v4
v2
v3
v1
图由节点和边组成:G=(V,E),
V是节点集合, E是边的集合。
若E中的边是无向边,称图为无向图;若E中的边是有向边(弧),称图为有向图。
图中不与任何结点相邻接的结点称为孤立结点;
仅由孤立结点组成的图称为零图;
仅含一个结点的零图称为平凡图;
含有n个结点、m条边的图称为(n,m)图;
简单图
在图中某个边的两个端点相同,则称之为环;若两点之间有多余一条的边,称之为多重边。
一个无环、无多重边的图称为简单图。一个无环、有多重边的图称为多重图。
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