运筹学-图论

精品课件
哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点
C
A
B
D
精品课件
哥尼斯堡七橋問題可以看成是：对这样一个封闭
的图形C ，是否可以一笔画完成它并且回到原点
A
B
Dቤተ መጻሕፍቲ ባይዱ
数学家欧拉(Euler, 1707-1783) 于1736年严格地证明了上述哥尼斯 堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式
精品课件
Königsberg (Koenigsberg)
哥尼斯堡，原为东 普鲁士 (Prussia) 首府，现属俄罗斯 (飞地)，名为加里
宁格勒 (Kaliningrad)
精品课件
精品课件
哥尼斯堡七桥问題: 要如何走过每座桥 恰一次，再返回出发点？
精品课件
普瑞格爾河
哥尼斯堡七桥问题
C
A
B
D
如果一个图是由点和边所构成的，那么称为无向图，
记作G=(V，E)，其中V表示图G 的点集合，E表示图G的 边集合。连接点vi , vj V 的边记作[vi , vj]，或者 [vj , vi]。
如果一个图是由点和弧所构成的，那么称为它为
有向图，记作D=(V, A)，其中V表示有向图D的点集合， A表示有向图D的弧集合。一条方向从vi 指向vj 的弧，记 作(vi , vj)。
v2（3）
v3（3）
（2）
v5
v1（2） v4（4） 简单图
v2 （3） v3 （3）
第五章 图与网络分析 图论
精品课件
主要内容：
1 图的基本概念与基本定理 2 树和最小支撑树 3 最短路问题 4 最大流问题 5 最小费用流问题
精品课件
什么是图？
图论中所谓的图是由一些点(vertices)，和一 些连接兩点的边(edges)所形成的
精品课件
5.1 图的基本概念与基本定理
图论是应用非常广泛的运筹学分支，它已经广 泛地应用于物理学控制论、信息论、工程技术、交 通运输、经济管理、电子计算机等各项领域。对于 科学研究、市场和社会生活中的许多问题，可以同 图论的理论和方法来加以解决。例如：各种通信线 路的架设，输油管道的铺设，铁路或者公路交通网 络的合理布局等问题，都可以应用图论的方法，简 便、快捷地加以解决问题。
精品课件
图论应用举例
例如，在组织生产中，为完成某项任务，各工序之 间怎样衔接，才能使生产任务完成得既快又好。
一个邮递员送信，要走完他负责投递的全部街道， 完成任务后回到邮局，应该按照怎样的路线走，所 走的路程最短。
各种通信网络的合理架设 交通网络的合理分布等
精品课件
生 活 中 的 一 些 例 子
精品课件
关于图的第一篇论文是瑞士数学家欧拉（E. Euler） 在1736年发表的解决“哥尼斯堡” 七桥难题的论文。
德国的哥尼斯堡城有一条普雷格尔河，河中有 两个岛屿，河的两岸和岛屿之间有七座桥相互连接， 当地的居民热衷于这样一个问题：一个散步者如何 能够走过这七座桥，并且每座桥只能走过一次，最 终回到原出发地。尽管试验者很多，但是都没有成 功。为了寻找答案，1736年欧拉将这个问题抽象成 图所示图形的一笔画问题。
点v1 ，…，v6表示这六支球队，它们之间的比赛情 况，也可以用图反映出来，已知v1队战胜v2 队，v2 队战胜v3 队，v3 队战胜v5队，如此等等。这个胜负
情况，可以用图5.3所示的有向图反映出来
v2
v
v
4
v
1
6
v3
v5
精品课件
从以上的几个例子可以看出，我们用点和点 之间的线所构成的图，反映实际生产和生活中的
条边的两个端点是相同的，那么称为这条边是环，
如图5.4中的边[v3 ,v3]是环。
精品课件
图的基本概念
如果两个端点之间有两条以上的边，那
么 称 为 它 们 为 多 重 边 ， 如 图 5.4 中 的 边
[v1 ,v2] ,[v2 ,v1]。 v1
v2
v3 v4
精品课件
一个无环，无多重边的图称为简单图， 一个无环，有多重边的图称为多重图。
精品课件
台大网路架构图
精品课件
例5.1 图5.2是我国北京、上海、重庆等十四个城市之间
的铁路交通图，这里用点表示城市，用点与点之间的线表示 城市之间的铁路线。诸如此类还有城市中的市政管道图，民 用航空线图等等。
北京
太原
石家庄
天津 塘沽
郑州
济南 徐州
青岛 连云港
重庆
武汉 南京
上海
图5.3
精品课件
例5.2 有六支球队进行足球比赛，我们分别用
A={(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4
,v5),
v3
v5
v7
(v4 ,v6),(v5 ,v3),(v5 ,v4),
(vv51 ,v6),(v6 ,v7)}
v6
v2
v4
图 5.5
精品课件
图的基本概念
一个图G或有向图D中的点数，记作P(G)或P(D)， 简记作P；边数或者弧数，记作q(G)或者q(D)， 简记作q 。 如果边[vi ,vj] E ，那么称vi , vj 是边的 端点，或者vi ,vj是相邻的。如果一个图G中，一
精品课件
图5.4是一个无向图G=（V，
E），
v1
v2
其中V={v1 , v2 , v3 , v4}
E={[v1 , v2],[v2 ,v1],[v2 ,v3],
[v3 ,v4],[v1 ,v4],
[v2 ,v4], [v3 ,v3]} v4
v3
图 5.4
精品课件
图5.5 是一个有向图D=（V，A） 其中V={v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7}
精品课件
即能否从某一点开始不重复地一笔画出这个图形， 最终回到原点。欧拉在他的论文中证明了这是不可 能的，因为这个图形中每一个顶点都与奇数条边相 连接，不可能将它一笔画出，这就是古典图论中的 第一个著名问题。
在实际的生产和生活中，人们为了反映事物 之间的关系，常常在纸上用点和线来画出各式各样 的示意图。
某些特定对象之间的特定关系。通常用点表示研 究对象，用点与点之间的线表示研究对象之间
的特定关系。由于在一般情况下，图中对象的相 对位置如何，点与点之间线的长短曲直，对于反 映研究对象之间的关系，显的并不重要，因此， 图论中的图与几何图、工程图等本质上是不同的。
精品课件
图的基本概念
图论中的图是由点、点与点之间的线所组成的。 通常，我们把点与点之间不带箭头的线叫做边，带箭头 的线叫做弧。