☞ 第一节 图的基本概念 ☞ 第二节 最短路径问题 ☞ 第三节 最大流问题 ☞ 第四节 最小费用流问题 ☞ 第五节 单、多回路运输路线问题
第六章 物流运输路径规划
图论是应用非常广泛的运筹学分支，它已 经广泛地应用于物理学控制论，信息论，工程 技术，交通运输，经济管理，电子计算机等各 项领域。对于科学研究，市场和社会生活中的 许多问题，可以同图论的理论和方法来加以解 决。例如，各种通信线路的架设，输油管道的 铺设，铁路或者公路交通网络的合理布局等问 题，都可以应用图论的方法，简便、快捷地加 以解决。
图6-4（a）
图6-4（b）
图6-4（c）
一、图的定义
子图与支撑子图：在图G=(V，E)中，若V1V，E1E，则 图G1=(V1、E1)称为G的子图，如图6-4中的(b)就是(a)的 子图。特别地：V1=V，E1E时，称G1是G的支撑子图 (生成子图）。如图6-4中(c)、(b)都是(a)的支撑图。
1736年瑞士科学家欧拉发表了关于图论方 面的第一篇科学论文《与位置几何有关的一个 问题的解 》，解决了著名的哥尼斯堡七座桥问 题。17世纪的东普鲁士有一座哥尼斯堡城（现 在叫加里宁格勒，在波罗的海南岸），城中有 一条普雷格尔河，河中有两个岛屿，河的两岸 和岛屿之间有七座桥相互连接，如下图所示。
第六章 物流运输路径规划
3. 网 络
一个图连同定义在其边集上的实函数一起称为一 个网络．网络一般是连通图．定义在边集上的实函数 称为边的权数记为
wij＝w (vi，vj)
它与边(vi，vj)具有一一对应关系，可以用以表达 网络上的各种有关性质，如路长、流量、费用等 等．网络的图解即在每条边旁标上相应的权数．
若一网络的每条边都是无向边，则称为无向网络，
例 有六支球队进行足球比赛，我们分别用点
v1…v6 表示这六支球队，它们之间的比赛情况，也可 以用图反映出来，已知v1 队战胜v2 队，v2 队战胜v3队 ，v3 队战胜v5 队，如此等等。这个胜负情况，可以用 下图所示的有向图反映出来。
第一节 图的基本概念
v2
v4
v1
v6
v3
v5
第一节 图的基本概念
图6-3
第一节 图的基本概念
v2
v4
v1
•有向图D（V，A）
•V为顶点集
•A（arc）为边或弧
v3
v6 v5
一、图的定义
关联边：和同一个顶点相
连的边，均称为该点的
关联边，如图6-4中的 e24、e34、e45均是v4的关 联边。
相邻点：一条边的两个顶
点，称为相邻点，如v2 与v4，v4与v5等是相邻 点，而v2与v5则不是。
画问题。即能否从某一点开始不重
复地一笔画出这个图形，最终回到
原点。欧拉在他的论文中证明了这
是不可能的，因为这个图形中每一
个顶点都与奇数条边相连接，不可
能将它一笔画出，这就是古典图论
中的第一个著名问题。
C
A D
C B
A
D
B
第六章 物流运输路径规划
第一节 图的基本概念
在实际的生产和生活中，人们为了反映事物之间的 关系，常常在纸上用点和线来画出各式各样的示意图。
怎么走，成本最低？应该先送哪一个商店？
现需要送20吨百货到A、B…等10个分店， 每个分店的需求都很零散， 至少需要多少什么型号的车辆？
每天各个分店都有部分百货要运回或转移到 其他分店，怎么运输车辆返空率最低，成本最低？
利客隆 超市分部图
总部
小李的答案类似解
太原 重庆
石家庄
北京 天津
塘沽
济南 青岛
第二节 最短路径问题
Dijkstra算法
设dij表示两个相邻点i——j点距离；如果不相邻dij
设Lsi表示不相邻的S-i之间的距离。 为了标志最短路的点，就对其标号。整个方法里面有 两种标号： （1）最短路上的点的标号，用P（permanent）表示; （2）不是最短路上的点的标号，用T(temporary)表示。
我们就把类似以上的几个例子中通过点和点之间 的线来反映实际生产和生活中的某些特定对象之间的 特定关系的所构成图形称为图（Graph）。一般来说， 通常用点表示研究对象,用点与点之间的线表示研究对 象之间的特定关系。由于在一般情况下，图中的相对 位置如何，点与点之间线的长短曲直，对于反映研究 对象之间的关系，显的并不重要，因此，图论中的图 与几何图，工程图等本质上是不同的。
v5 e45
一、图的定义
悬挂点与孤立点：
次为1的顶点称为
悬挂点，如v5。次为
0的顶点称为孤立点， v1
v2
如v6。
e12
e'13 e13
e24
e34
v3
v4
图图 56-.41
悬
e22
挂 点
v5
e45
孤 立
点
v6
一、图的定义
简单图：无环、无多重边的图称为简单图，如图6-4(a)、 (b)、(c)，后面如无特殊说明，均指简单图。
C
D
一、图的定义
定义1： 一个图是由点集V={vi }和V中元素的
无序对集E={ ek }所构成的二元组，记作：G = （V，E），其中 vi 称为顶点，ek 称为边。|V | 表 示顶点个数，|E | 表示边的个数。当V和E都是有 限集合时，G为有限图，否则，称为无限图。本 书只论及有限图。图中所有边都没有方向，称为 无向图，否则称为有向图。例如下面图6-3，即 为无向图.
图6-4（a）
图6-4（b）
图6-4（c）
一、图的定义
定理1 在任何图中顶点次数总和等于边数的2倍。 定理2 任何图中，次为奇数的顶点必有偶数个。
即奇顶点必有偶数个。
二、连通图
定义2 无向图G=(V，E)中，称某些点及其关联边的 交替序列{v1 e1 v2 e2 … en vn }为从v1到vn的一条链， v1、vn分别称为链的始点和终点，链长为n。 若一条链的始点与终点重合，则称为闭链(在 无向图中闭链又称为回路），否则，称为开链。 点边序列中若只有重复的点而无重复的边，则称 为简单链。点边序列中若既没有重复的点也无重 复的边，则称为初等链（也称为通路）。
6
政府的难题
政府想在7个小区准备共建一套医务所、邮局、 储蓄所等服务设施，应建于哪一居民小区，使 对居民总体来说感到方便。
电信部分拟将布设宽带到各个小区，应如何铺 设最为经济？
工作组组织考察，从小区①出发，经过各小区 （顺序不限），最后到小区⑦再离去，哪条路 最近？
第六章 物流运输路径规划
e22 v5
e45
一、图的定义
次：一个顶点v具有关联边的总数称为该顶点的次，
记作d(v)（每个环视作两条边），如图6-4。
d(v1)= 3，d(v2)= 4， d(v5)= 1。 把次为奇数的顶点称
e22
v1
v2
e12
为奇顶点，次为偶数 的顶点称为偶顶点。
e'13 e13
e24
e34
v3
v4
图图 66-.14
二、连通图
例如在图6-5中： S={v6 e6 v5 e7 v1 e8 v5 e7 v1 e9 v4 e4 v3}是一 条连接v6、v3的链，链长为6. S1={v6 e6 v5 e7 v1 e8 v5 e5 v4 e4 v3}是一条连接v6、v3的简单 链，链长为5.
S2={v6 e6 v5 e7 v1 e9 v4 e4 v3}
记为
N＝(G，w ) 或 N＝(V，E )
3. 网 络
若一网络的每条边都是有向边，则称为有向网络，
记为
N＝( D，w ) 或 N＝ ( V，A )
若一网络中既有无向边，也有有向边，则称为混合 网络．
所谓网络分析，即对网络进行定性和定量分析，以 便为实现某种优化目标而寻求最优方案．这方面的典型 问题有：最小树问题，最短路问题，中心问题，重心问 题，最大流问题，最小费用最大流问题，网络计划问题， 等等．
v1
v2
e12
e'13 e13
e24
e34
v3
v4
图图 66-.41
e22 v5
e45
一、图的定义
环与多重边： 两个顶点相同的 边称为环，如e22， 两个顶点之间的 边数≥2时,叫多 重边,如e13 ,e’13 就是二重边。
环
二重边
v1
v2
e12
e'13 e13
e24
e34
v3
v4
图图 66-.41
郑州
徐州 连云港
武汉
南京
上海
长途运输路线问题
长虹街道近年新建了11个居民小区，各小区的大致位 置及相互间的道路距离如图所示，单位（100m）， 各居住小区居民数为：①2000, ②3000, ③3500, ④ 3700, ⑤5000, ⑥2800, ⑦4500。
16
4
5
4
2
7
33
2
7
4
75
2
6
5
第一节 图的基本概念
一、图的定义
图论中所研究的图，是指反映或描述自然界或 人类社会中，大量的事物及事物之间关系的图形。 是由点和线组成的。点称为顶点，它的集合用V （Vertex）表示，顶点通常表示有形或无形的事物。 线称为边，它的集合用E（Edge）表示，边通常表 示事物与事物（点与点）之间的联系或特定的关系。
第六章 物流运输路径规划
随着科学技术的进步，特别是电子计算机技 术的发展，图论的理论获得了更进一步的发展， 应用更加广泛。如果将复杂的工程系统和管理问 题用图的理论加以描述，可以解决许多工程项目 和管理决策的最优问题。因此，图论越来越受到 工程技术人员和经营管理人员的重视。