▲如果链中所有的顶点v0，v1，…，vk也不相
e2 e 4
v2 e5
e1 v1 e3 v3
同，这样的链称初等链（或路）。 ▲如果链中各边e1,e2…,ek互不相同称为简单链。
▲当v0与vk重合时称为回路（或圈），如果边不
e6
v4
e7
e8
v5
重复称为简单回路，如果边不重复点也不重复 则称为初等回路。 图8－1中， μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5}是一条链，μ1中因顶 点v3重复出现，不能称作路。
运筹学
Operations Research
Chapter 8 图与网络分析
Graph and Network
1. 2. 3. 4. 图与网络的基本知识 树 最短路问题 最大流问题
E.Euler提出(1736年）：
引例：哥尼斯堡七桥问题
您能从A、B、C或D任意一点出发 走遍7座桥并且每座桥只走一次最 后回到原出发点吗？
5
e2 v2 e6 e3 v3 v4
e1 v1 e3 e4 e5 e7
v3 e8 v5
e6 v4
e8 v5
e6 v4
e7 图２－2(b) v5
图８－2(a)
定义8
网络（赋权图）：
设图G＝（V，E），对G的每一条边(vi,vj)相应的有一条数w
(vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为网络
一、图与网络的基本概念 如图8-1
V v1 , v2 ,, v5 , E e1 , e2 ,, e8
e2可记作： e2 [v1 , v2 ]
e2 e 4
e5
e1 v1 e3 v3
v2 定义1 端点，关联边，相邻 若有边 e 可表示为 e=[vi,vj], 称 vi 和 vj e6 是边e的端点，反之称边e为点vi或vj的关联 边。若点vi 、vj 与同一边关联，称点vi 和vj 相邻；若边ei和ej具有公共的端点，称边ei v4 和ej相邻。例如图8－1， v2和v4是边e6的端点，反之边e6是点v2、v4的 关联边。点v2、v4相邻；边e6与e5、 e4相邻。
e7
e8
v5
图8－1
定义2 环，多重边，简单图 如果边 e 的两个端点相重，称该边为 环。如图8－１中边e1为环。如果两个点之 间的边多于一条，称为多重边，如图 8 － １中的 e4 和 e5 ，对无环、无多重边的图称 作简单图。 定义3 次，奇点，偶点，孤立点 与某一个点 vi 相关联的边的数目称为 点vi 的次（也叫做度），记作d(vi) 。图６ －１中d(v1) ＝４,d(v3)=5,d(v5)=1。次为奇 数的点称作奇点，次为偶数的点称作偶 点，次为0的点称作孤立点。
图Ｇ可 定义为点和边的集合，记作
A
G V , E
C
D
其中V
B
式中Ｖ是点的集合，Ｅ是边的集合。注意上面定义的图Ｇ区别 于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等 都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连， 如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量 等，把这样的图称为网络图，记作Ｎ。图和网络分析的方法已广泛 应用于物理、化学、控制论、信息论、计算机科学和经济管理等各 个领域。
⑤
① ③ ④
⑥
定义7：子图、生成子图（支撑子图） 图G1={V1、E1}和图G2={V2，E2}如果 V1 V2和E1 E2 称G1是G2的一个子图。 若有 V1＝V2，E1 E2 则称 G1是G2的一 个支撑子图（部分图）。 图8-2（a）是图 6-1的一个子图，图8-2 （b）是图 8-1的支撑子图，注意支撑子图 e1 也是子图,子图不一定是支撑子图。 v1 e2 e4 v2 v3 v2 e
v1 v3 v2 配送 中心 v8 v4 v9 v6 v7
基本的网络最优化问题有4个，即最小树问题，
最短路问题、最大流问题、最小费用最大流问 题。这些问题的数学模型实际上大都是线性规 划问题，但使用线性规划的单纯形法去求解， 过程非常繁琐，本章介绍的网络分析方法能有 效的解决这些问题。
8.1图与网络的基本知识
定义5 混合图：
如何图G中部分边有方向则称为混合图
② ⑤
① ③
④
⑥
有向图
定义6 有向图中，以Vi为起始点的边数称为点Vi的出次， 用 d (vi ) 表示；有向图中，以Vi为终点的边数称为点Vi的 入次，用 d (vi ) 表示。
结论1： Vi点的出次与入次之和就是该点的次。 结论2：有向图中，所有顶点的入次之和等于所有顶点的 出次之和。 ②
A
C
D
A D C B
B
中国邮路问题：管梅谷（1962年）提出
一个邮递员，负责某一地区的信件投递。他每天 要从邮局出发，走遍该地区所有街道再返回邮局， 问应如何安排送信的路线可以使所走的总路程最 短？
2 5 6 5 9 4 4 3 3 4 4
4
我们在实际生活、生产和科研活动中经常看到
许多的网络，如互联网、通信网、公路网、管 道网、销售网等。对网络进行研究是希望解决 其中的一些优化问题，网络最优化能为人们管 理和控制这些网络系统提供一套有效的方法。
D
A
C
B

例 某家电配送中心需要为多个销售点送货，配送中心与销售 点以及销售点之间的相对位置和运输情况可以用图来表示。 其中，点v1，v2，…，v7代表销售点，边表示运输路线。若已 知每条路线行走所需的时间，请帮助配送中心管理人员设计 一条送货路线，使送货车辆用最短的时间送完货物，并回到 配送中心。 v5
e2 e 4 v2 e6 v4 e5 e7
e1 v1 e3 v3 e8 v5
定理1 任何图中，顶点次数的总和等于边数的2倍。
v1
v3 v2
定理2 任何图中，次为奇数的顶点必为偶数个。
e2 e 4 e1 v1 e3
v2
e6 v4
e5 e7
Байду номын сангаас
v3
e8 v5
定义4 有向图：
如果图的每条边都有一个方向则称为有向图
（赋权图）。 这里的权数可以是时间、费用、距离等，视不同背景代表不同 的含义。 15 ② 7 ⑤ 9 14 10 ④ ① 6 19 20 ⑥ ③ 25 赋权图
二、连通图 定义9 链、路、回路（圈） ▲无向图中有些点和边的交替序列
v0 , e1 , v1 ,, ek , vk
对任意vi,t－1 和vit(2≤t≤k)均相邻，称μ从v0到vk 的链。