文档介绍：图与网络优化 (Graph work Optimization)
图的基本概念
最小支撑树问题
最短路问题
网络最大流问题
中国邮递员问题
图的基本概念
引例
哥尼斯堡七桥问题
图论的开创者
(1707-1783)
引例: 阿富汗战后建设, 30个村庄要通电话, 已知两两距离,如何用最少的电
话线连通30个村庄?
图的基本概念
村庄1
村庄4
村庄3
村庄6
村庄2
村庄5
6
3
11
5
9
8
10
7
7
12
网络结构
DNS、内网WWW服务器
外网WWW服务器
楼层交换机
防火墙
网管工作站
OA骨干交换机
楼层交换机
用户工作站
CISCO 路由器
骨干交换机
PSTN
移动办公
DCN
其它部门
OA、EMAIL主机
图的基本概念
图的基本概念
1. 无向图(No-directed Graph)
例1 现有五个城镇A1,A2,
A3,A4,A5, 其中A1与
A3,A4有公路相联,A2与
A4,与A5有公路相联,A3
与A5有公路相联,试用图
形表示上述关系。
图上的点表示城镇,线表示城镇与城镇之间有公路相连。
A1
A5
A4
A2
A3
例2 P252 甲乙丙丁戊五个球队,用图表示他们之间比赛:
V1
V5
V4
V3
V2
图的基本概念
例3 P252 八种化学药品
有的不能够放在同一个库房里,
用图表示他们之间关系:
不能放在一起的加连线。
V8
V4
V3
V2
V1
V5
V6
V7
图的基本概念
无向图:图G中,若点与点之间的连
线是没有方向的,则这种连
线叫边。由点和边构成的图
叫无向图,记作G=[V,E]。
式中 V 为 G 的顶点的集合,
E 为 G 的边的集合;一条连
接 V 中两点 vi 和 vj 的边记作
e=[vi , vj ]或[vj ,vi ]。
环(ring):两个端点重合的边叫做环。
图的基本概念
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e6
e7
e8
e9
多重边(multiple edge):两个端点之间的边数超过 1 时叫做多重边。
简单图(simple graph):无环也无多重边的图叫做简单图。
V={v1, v2, v3, v4, v5}
E={e1, e2, e3, e4, e5 ,e6, e7, e8, e9}
图 G 中的
点数记为
p(G)或 p。
图 G 中的
边数记为
q(G)或 q。
链(chain):图G中,一个以顶点和边交错的序
列(vi1, ei1, vi2, ei2, …, ei k-1, vi k),如果
满足eit=[vi t, vi t+1](t=1,2,…,k-1),则
称之为G 中一条连接vi 1和 vi k的链,
简记为(vi1, vi2, …, vi k-1, vi k).
图的基本概念
初等链(elementary chain):若链中的顶点都不相同,则称此链为初等链。
简单链(simple chain):若链中所含的边都不相同,而顶点允许相同,
则称之为简单链。
v1
v2
v3
v4
v5
e1
e2
e9
e3
e7
e6
e8
e4
e5
v6
v7
e10
P’={v6, v7 , v3, v4, v1, v3, v2}
P={v6, v7 , v3, v4, v5, v1, v2}
圈(cycle):链(vi1, vi2, …, vi k-1, vi k)中,若 vi 1= vi k,则称之为一个圈,记为
(vi1, vi2, …, vi k-1, vi 1)。
图的基本概念
初等圈(elementary cycle):若圈中的顶点都不相同,则称此圈为初等圈。
简单圈(simple cycle):若圈中所含的边都不相同,而顶点允许相同,
则称之为简单圈。
连通图(connected graph):图 G 中任何两个顶点之间至少有一个链,
则称 G 为连通图。
v1
v2
v3
v4
v5
e1
e2
e4
e5
e6
e7
e8
e3
v7
v6