运筹学图与网络分析{PPT}.ppt

第八章图与网络分析
引例
哥尼斯堡七桥问题
A
B
C
D
B
D
A
C
环球旅行问题:
环球旅行问题的解
第1节图与网络的基本知识
图可以用来做什么:
管理当中,事物及事物间的联系可以用图来描述
五只球队的比赛情况
甲
乙
丙
丁
戊
甲
乙
丙
丁
戊
A
B
C
D
工作分配问题
图已经应用于物质结构、交通、信息传递等的描述
图与网络的基本概念(1)
图:这里讨论的图由点以及点与点间的连线构成,与平面几何的图不同,这里只关心图中有多少个点,点与点间有无连线,至于点与点间的连线是直线还是曲线,点的相对位置,则是无关紧要的。
图与网络的基本概念(2)
定义1 一个图是由点集V={vi}和V中的元素的无序对的一个集合E={ek}所构成的二元组,记为G=(V, E),V中的元素vi叫做顶点,E中的元素ek叫做边
v2
v1
v5
v3
v4
e2
e1
e3
e4
e5
e6
V={v1,v2,v3,v4,v5}
E={e1,e2,e3,e4,e5,e6}
e1=(v1,v1), e2=(v1,v2)…
例
图与网络的基本概念(3)
相邻:图中的两点间存在连线(边),则称这两点相邻,并称它们是这条边的端点;若两条边有公共的端点,则称这两条边相邻,并称它们是其公共端点的关联边。
v2
v1
v5
v3
v4
e2
e1
e3
e4
e5
e6
相邻
相邻
边数:m(G)=|E|
顶点数:n(G)=|V|
图与网络的基本概念(4)
无向边与无向图:若图中任一条边的端点无序,即(vi, vj)与(vj, vi)是同一条边,则称它为无向边,此时图称为无向图。
有向图:若图中边(vi, vj)的端点是有序的,则称它是有向边(或弧),vi与vj分别称为这条有向边的始点和终点,相应的图称为有向图。
图与网络的基本概念(5)
v2
v1
v5
v3
v4
e2
e1
e3
e4
e5
e6
环(自回路)
多重边
定义2 不含环和多重边的图称为简单图。含多重边的图称为多重图。
简单图