第5章图与网络分析.ppt

第5章图与网络分析( Graph Theory work Analysis )
图的基本概念与模型
树
最短路问题
网络的最大流
最小费用流
应用举例
近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥,要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。
第一节图的基本概念与模型
Königsberg桥对应的图
例1、有甲、乙、丙、丁、戊五个球队,
它们之间比赛的情况也可以用图表示出来。
V1
V2
V3
V4
V5
e5
e4
e1
e2
e3
e6
e7
一、图基本概念
例2 某单位储存八种化学药品,其中某些
药品是不能存放在同一个库房里的。为了反映
这个情况可以用点V1,V2,……V8分别代表这八
种药品,若药品Vi和药品Vj是不能存放在同
一个库房的,则在Vi和Vj之间连一条线。
• V1
V2
•
•V3
• V4
• V5
•·
V8
• V7
• V6
图的表示方法:
一般地,当用图论研究一个实际问题时,
常以顶点(Vertex)表示要研究的对象,以
它们之间的连线,表示某种关系,这种连线
称为边(Edge),目的是为了解决某个极值
问题。图中的点用v表示,边用e表示。对每
条边可用它所连接的点表示,
记作:e1=[v1,v1]; e2=[v1,v2];
运筹学中研究的图具有下列特征:
强调点与点之间的关联关系,不讲究图的比例大小与形状;
每条边上赋有一个权;
建立网络模型,求最大值或最小值。
下图可以提出很多极值问题
1
4
2
6
5
3
8
7
6 6
3
1
6
2 7 4
3
3
7
1
6
v3
e7
e4
e8
e5
e6
e1
e2
e3
v1
v2
v4
v5
端点,关联边,相邻
若有边e可表示为e=[vi,vj],称vi和vj是边e的端点,反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联,称点vi和vj相邻;若边ei和ej具有公共的端点,称边ei和ej相邻。
二、关于图的另外一些名称和术语:
环, 多重边, 简单图
如果边e的两个端点相重,称该边为环。如右图中边e1为环。如果两个点之间多于一条,称为多重边,如右图中的e4和e5,对无环、无多重边的图称作简单图。
v3
e7
e4
e8
e5
e6
e1
e2
e3
v1
v2
v4
v5
次,奇点,偶点,孤立点
与某一个点vi相关联的边的数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。
v3
e7
e4
e8
e5
e6
e1
e2
e3
v1
v2
v4
v5
图的次: 一个图的次等于各点的次之和。