--- tags: - 离散数学 返回目录: '[[数学系/离散数学/离散数学|离散数学]]' abstract: '图论模型与网络优化' finished: false --- # 图与网络优化建模 ## 图论概述 - 图论是应用广泛的运筹学分支，在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。 - 欧拉七桥问题 欧拉回路：从图中任意一点出发，经过图中所有边一次且仅一次的回路 ![|700x255](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczAuYmRzdGF0aWMuY29tLzcwY0Z1SFNoX1ExWW54R2twb1dLMUhGNmhoeS9pdC91PTIyNTEzODY4MTMsMzQwMzI0MjMzNSZmbT0yNiZncD0wLmpwZw) 18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如右上图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的充要条件是：奇点的数目不是0 个就是2 个（连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端）。1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新一分支---图论。 - 环球旅行问题(哈密尔顿圈问题) ![](https://img-blog.csdnimg.cn/img_convert/4f7fce9b20f25413eaeacf9ca63160eb.png) *正十二面体* 哈密顿回路：从图中任意一点出发，经过图中所有顶点一次且仅一次的回路 经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。 TSP的研究历史很久，最早的描述是1759年欧拉研究的骑士环游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1954年，Geo~eDanzig等人用线性规划的方法取得了旅行商问题的历史性的突破——解决了美国49个城市的巡回问题。 - 中国邮递员问题 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 ![|477x190](https://ts2.tc.mm.bing.net/th/id/OIP-C.OHa0SJYMUZnrOPJCU-moyAHaC9?r=0&rs=1&pid=ImgDetMain&o=7&rm=3) 中国邮递员问题是邮递员在某一地区的信件投递路程问题。邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短。这个问题由中国学者管梅谷在 1960 年首先提出，并给出了解法——“奇偶点图上作业法”，被国际上统称为“中国邮递员问题”。用图论的语言描述，给定一个连通图 G，每边 e 有非负权)，要求一条回路经过每条边至少一次，且满足总权最小。 管梅谷（Mei-KO KWAN），1934 年出生，上海人，教授。1957 年毕业于华东师范大学数学系。 管梅谷教授自 1957 年至 1990 年在山东师范大学工作。1984 年至 1990 年担任山东师范大学校长，1990 年至 1995 年任复旦大学运筹学系主任。1995 年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员，国际项目办公室高级顾问及复旦大学管理学院兼职教授。 ## 图的基本概念 ** ** **图论中的图是由点以及点与点之间的连线组成的示意图。** **用点代表所研究的对象，用连线代表两个对象之间的特定关系。** **无向图G = (V, E)** **有向图D= (V, A)** ![[图论1]] V = {v1,v2,v3,v4} E = {e1,e2,e3,e4, e5,e6,e7} e1=[v1,v2] ![[图论2]] V = {v1,v2,v3,v4,v5,v6,v7} A = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10} a1=(v1,v2) **点数p** **边数q** **邻接、关联** **环** **多重边** **多重图：无环，但允许有多重边的图** **简单图：无环，无多重边的图** **点的次数 (或 度数) d(v)：点的关联边的条数** **注意** **奇点: 度为奇数** **有环时，在计算度数时需要算两次。** **偶点: 度为偶数** **悬挂点: 度为1的顶点** **孤立点: 度为0的顶点** **悬挂边: 与悬挂点关联的边** **关于点的次数(度数)的两个定理：** **[定理1] 任一图中，所有点的次数之和是边数的两倍。** $\sum_{v \in V_1} d(v)=2q$ **[定理2] 任一图中，奇点的个数为偶数。** $\sum_{v \in V_1} d(v)+\sum_{v \in V_{2}}d(v)=\sum_{v \in V}d(v)=2q$ ![[图论3]] **链：图G=(V,E)中一个点、边交错序列** (v1，e4，v4，e3，v3，e7，v6，e8，v7，e9，v5) **中间点：除了两个端点以外的点** **圈：两个端点相同的链** **简单链：所有边均不相同的链** **初等链：所有点均不相同的链** (v1，e1，v2，e2，v3，e3，v4，e5，v5，e6，v3，e7，v6，e8，v7) **连通图：任何两个点之间，至少有一条链相连的图** **不连通图** **连通分支：若G不是连通图，它的每一个极大连通子图。** **支撑子图：给定连通图G＝(V,E)，如果 $G'=(V',E')$ 满足 $V'=V$ 及 $E' \subseteq E$ ，且G′也是连通的，则称G′为G的一个支撑子图。** **注意** **支撑子图仍是连通的** ## 二、重要的图类概念 **1、完全（完备）图** **2、二部（二分）图、完备二部图** **3、正则图（含立方图）** **4、平面图与非平面图** **5、完美图、可分图、森林、树、……** ## 有向图的一些基本概念 **基础图G(D)：从有向图D中去掉所有弧的箭头得到的无向图。** 弧a = (u, v) ```mermaid graph LR u --a--> v ``` **起点 u、终点 v** **无向图：链、圈、初等链、初等圈、简单链、简单圈** **路：一条按照弧方向前进的链。** (v1，a1，v2，a3，v3，a5，v4，a9，v6，a10，v7) ![[图论2]] **回路：起、终点相同。** **初等路：各顶点不相同的路。** **初等回路** ## 三、最小支撑树问题 **例4 某工厂在6个车间之间的道路网如图所示，每条道路的距离已知。** **问：如何沿道路架设电话线网，才能使电话线的总长最小？** ![[图论4]] ## 三、最小支撑树问题 **1、树的定义** **树：一个无圈的连通图** ## 三、最小支撑树问题 ## **2、树的6个等价性质：** **设图 T = (V, E)是一个树，其中点数为p、边数q。** - **（1）T为无圈的连通图；** - **（2）T无圈，且q＝p-1；** - **（3）T连通，且q＝p-1** **；** - **（4）T无圈，但增加一条边，可得到一个且仅一个圈；** - **（5） T连通，但舍弃一条边，图便不连通；** - **（6）T中任意两个顶点之间恰有一条链。** ## 三、最小支撑树问题 **3、支撑树** **支撑树：若T=(V,E′)是G=(V,E)的子图，且T是一个树，则T为G的一个支撑树。** 图G有支撑树的充要条件是图G是连通的。 - **证明：必要性是显然的。** - **充分性 设G是连通图，若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。若G含圈，任取一个圈，从圈中去掉任意一条边，得到G的一个支撑子图G1。若G1不含圈，则G1是G的一个支撑树；否则继续上述破圈操作，直到没有圈为止，最终找到一个支撑子图，它不含圈，是G的一个支撑树。** ## 三、最小支撑(生成）树问题 #### 1.加权图和最小生成树 **1.1.加权图定义** 加权图是一种为每条边关联一个权值的图模型，权值可代表举例或成本。 **1.2.最小生成树定义** 图的生成树是一颗含有所有顶点的五环连通子图，一幅加权图的最小生成树（minimum spanning tree,MST）是它的一棵权值最小的生成树。 如下所示是一幅加权无向图和它的最小生成树。 #### 1.3.加权无向图数据类型 **加权边的 API** ![62954ab1436b484f81327594dcf5e70a.png](https://i-blog.csdnimg.cn/blog_migrate/d4618ce1862de25968f5d6f688dd2030.png) **加权无向图 API** ![1a328ac33077ba39e7c091e5e62803d9.png](https://i-blog.csdnimg.cn/blog_migrate/6e58f4402189e5ec78335e2b368ad4d5.png) **加权无向图表示** ![56c71b483fa727a4dddee46737f49e0e.png|324x24](https://i-blog.csdnimg.cn/blog_migrate/96a5a7c6092544074ed884f208e7eb0b.jpeg) **实现** 权重边实现 ```java public class Edge implements Comparable { private final int v; private final int w; private final double weight; public Edge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } public double weight() { return weight; } public int either() { return v; } public int other(int vertex) { return vertext == v ? w : v; } public int compareTo(Edge that) { if (this.weight() < that.weight()) return -1; else if (this.weight() > that.weight()) return 1; else return 0; } } ``` 加权无向图实现 ```java public class EdgeWeightedGraph { private final int V; // 顶点数 private int E; // 边数 private Bag[] adj; // 邻接表 public EdgeWeightedGraph(int V) { this.V = V; this.E = 0; adj = (Bag[])new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag(); } public int V() { return V; } public int E() { return E; } public void addEdge(Edge e) { int v = e.either(); int w = e.oter(v); adj[v].add(e); adj[w].add(e); } public Iterable adj(v) { return adj[v]; } public Iterable edges() { Bag list = new Bag(); for (int v = 0; v < V; v++) { int selfLoops = 0; for (Edge e : adj(v)) { if (e.other(v) > v) { list.add(e); } // add only one copy of each self loop (self loops will be consecutive) else if (e.other(v) == v) { if (selfLoops % 2 == 0) list.add(e); selfLoops++; } } } return list; } } ``` ## **3、支撑树** 寻找支撑树的方法：“破圈法”和“避圈法” #### 2.最小生成树算法实现 最小生成树的两种经典算法是：Prim 算法和 Kruskal 算法。下面我们来研究研究。 研究之前我们先学习一下切分定理，这是两种算法的基础。 **2.1.切分定理与贪心算法** **图的切分** 图的切分是将图的所有顶点分成两个非空且不重叠的集合。其中横切边是一条连接两个属于不同集合顶点的边。 **切分定理** 在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。 如下图所示。 ![6733d0581b0401f86b2154a0de5a7b96.png](https://i-blog.csdnimg.cn/blog_migrate/53e74adccdf0dcddda8fe5bb4749c8e3.png) **贪心算法** 适用于**最优化问题**的算法往往包含一系列步骤，每一步都有一组**选择**。贪心算法是使所作出的选择看起来都是当前最佳的，期望通过所做的**局部最优选择**来产生一个**全局最优解。** **最小生成树的贪心算法** 将含有 V 个顶点的任意加权连通图中属于最小生成树的边标记为黑色，初始状态下所有边均为灰色，找到一种切分，需要保证它产生的横切边均不为黑色，然后将权重最小的横切边标记为黑色。如此反复，直到标记了 V-1 条黑色边为止。 这类最小生成树算法满足了局部最优全局最优的贪心算法特点。 #### 2.2.Prim 算法 **最小生成树 API** ![28f3a85bb443db5dd8639a3ae6ea5d32.png](https://i-blog.csdnimg.cn/blog_migrate/0bc0a9c7157782ffe0208958f1916fbf.png) **Prim 算法数据结构** Prim 算法能够得到任意加权连通图的最小生成树。下面我们来构造一下算法的数据结构： 1. marked[]，即使用一个顶点索引的 boolean 数组，若顶点 v 在数组，则 marked[v] = true。【顶点】 2. 最小生成树边集合，可以通过一个队列来保证最小生成树的边，或一个 edgeTo[]数组，在《深度优先算法和广度优先算法》一文中咱们有说过。【边】 3. 使用一个优先队列 MinPQ\来根据权重比较所有边，优先队列即堆排序的数据结构，以后有机会我们讲讲，目前只需要知道它可以用来获取队列中的最小值。【横切边】 ![](https://i-blog.csdnimg.cn/blog_migrate/eeca7457f4b69bbdcc68dec948c84f3d.png) **Prim 算法实现** 惰性实现 ```java public class LazyPrimMST { private boolean[] marked; // 最小生成树的顶点，也是图的顶点 private MinPQ pq; // 横切边 private Queue mst; // 最小生成树的边，即用于保存结果 private double weight; // 最小生成树权重 public LazyPrimMST(EdgeWeightedGraph G) { marked = new boolean[G.V()]; mst = new Queue(); pq = new MinPQ(); visit(G, 0); while (!pq.isEmpty()) { Edge e = pq.delMin(); int v = e.either(), w = e.other(v); if (marked[v] && marked[w]) continue; mst.enqueue(e); weight += e.weight(); if (!marked[v]) visit(G, v); if (!marked[w]) visit(G, w); } } private void visit(EdgeWeightedGraph G, int v) { marked[v] = true; for (Edge e : G.adj(v)) if (!marked[e.other(v)]) pq.insert(e); } public Iterable edges() { return mst; } public double weight() { return weight; } } ``` #### 2.3.Kruskal 算法 (避圈法) Kruskal 算法的思想是按照边的权重顺序从小到大处理他们，将边加入最小生成树中（加入的边不要保证不会与已经加入的边构成环），直到树中含有 V-1 条边为止。 Kruskal 算法轨迹如下所示. ![c26aef34b9b3c3e5a61f299d66f617fe.png](https://i-blog.csdnimg.cn/blog_migrate/3d7db3c10cefe817eb5cad95cf191b79.jpeg) 将边按照权重从小到大排序，会形成环的边为无效边。 算法实现： ```java public class KruskalMST { private Queue mst; // edges of mst private double weight; // weight of MST public KruskalMST(EdgeWeightedGraph G) { mst = new Queue(); MinPQ pq = new MinPQ<>(); // 边从小到大排序（堆排序） for (Edge e : G.edges()) pq.insert(e); UF uf = new UF(G.V()); while (!pq.isEmpty() && mst.size() < G.V() - 1) { Edge e = pq.delMin(); int v = e.either(), w = e.other(v); if (uf.find(v) != uf.find(w)) { // v-w does not create a cycle uf.union(v, w); // merge v and w components mst.enqueue(e); // add edge e to mst weight += e.weight(); } } public Iterable edges() { return mst; } public double weight() { return weight; } } } ``` 注：UF 是判断两点的动态连通性算法，我们以后有机会单拎出来讨论。 ### 三、破圈法   设 _G=_是无向连通带权图，_C_ 是_ G_ 中任意一个圈，_e’_是_ C_ 中带权最大的边，则 _G-e’_中的最小生成树也是 _G_ 中的最小生成树。 破圈法是“见圈破圈”，即如果看到图中有一个圈，就将这个圈的最大权边去掉一条，直至图中再无一圈为止。 1. 把原图的所有边按**权重从大到小**排序 2. 从权重最大的边开始，逐个检查： - 如果删掉这条边**不会导致图不连通**（即它在一个环上），就删掉它 - 如果删掉会导致图断开，就保留它 3. 重复直到剩下 n-1 条边（n 为顶点数） **核心逻辑**：环上最大的边不可能出现在最小生成树中，因为可以用环上其他更小的边替代它。 ## **4、赋权图** 给图*G*＝(*V*,*E*)，对*G*中的每一条边[*vi*, *vj*]，相应地有一个数*wij*，则称这样的图*G*为赋权图，*wij*称为边[*vi*, *vj*]上的权。 ## 三、最小支撑树问题 ## **5、最小支撑树** *T* = (*V*, *E*′)是*G*的一个支撑树，*T*中所有边的权之和为支撑树的权*w*(*T*)。如果*T*\*的权*w*(*T\**)是*G*的所有支撑树的权中最小者，则称为*G*的最小支撑树（最小树）。 ## 三、最小支撑树问题 ## **6、最小树问题** **例4 某工厂在6个车间之间的道路网如图所示，每条道路的距离已知。** **问：如何沿道路架设电话线网，才能使电话线的总长最小？** ![[图论4]] **最小树问题就是在赋权图上求最小支撑树的问题** ## 三、最小支撑树问题 ## **6、最小支撑树问题** **求最小树的方法：“破圈法”和“避圈法”** - **破圈法：“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。** - **步骤如下：** - **在图中找一个回路;** - **去掉该回路中权值最大的边;** - **反复此过程，直至图中再无回路，得到最小支撑树。** - **避圈法：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。**（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。 ## 三、最小支撑树问题 ## **6、最小支撑树问题** **求最小树的方法：“破圈法”和“避圈法”** v3 ## 思考 **练习：已知世界6大城市：（Pe），（T），（Pa），（M），（N），（L）之间的交通网络的数据，确定最小树。**
城市 Pe T Pa M N L
Pe
T 13
Pa 51 60
M 77 70 57
N 68 67 36 20
L 50 59 2 55 34
## 四、最短路问题 1、问题的提出 ![[图论6.png]] **例5 如图所示的单行线交通网，通过每条单行线的费用已知。** - 求：从v1到v8总费用最小的旅行线？ **最短路问题是在赋权有向图中寻求最短路的问题** ## 四、最短路问题 2、求解方法：Dijkstra算法 艾兹格·W·迪杰斯特拉（Edsger Wybe Dijkstra，1930年5月11日\~2002年8月6日）荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。 ## 四、最短路问题 2、求解方法：Dijkstra算法 适用范围：正费用网络（wij ≥ 0） **表述方式：** **P(vi)** P标号 **永久性标号（Permanent）** **最短距离** **T(vi)** T标号 临时性标号（Temporary ） **最短距离** **的上界** ## 四、最短路问题 2、求解方法：Dijkstra算法 **基本步骤：** **令Si为第i步具有P标号点的集合，P(v)表示从vs点到v点的最短距离，T(v)表示从vs点到v点的最短距离的上界，λ(v)表示从vs点到v点最短路上前一个点的标号。** **初始化：令S0 = {vs}, P(vs) =0, λ(vs) = 0; 对于v≠vs，令T(v) = +∞, λ(v) = M，令k = s，即当前检查点。** **步骤1: 如果Si=V, 算法停止，则对于每个v∈Si来说，P(v)为点vs到v的最短路路长(最短路可以通过λ(v)所记录的信息反向追踪获得)；否则继续步骤2。** ## 四、最短路问题 2、求解方法：Dijkstra算法 **步骤2: 以vk为检查点，考察每个以vk为始点且属于T标号点的点vj。如果T(vj)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，且令λ(vj) = k；否则转入步骤3。** **步骤3: 从所有T标号点中找出T(vj)最小的点，若T(vj)<+∞，则把vj的T标号换成P标号P(vj)=T(vj)，且令 Si+1=Si+{vj}, k=j，i=i+1，转入步骤1。** ## 四、最短路问题 **例5 最短路问题** ![[图论6.png]] **最短路为：** $\boldsymbol{\mathit{v}}_{\mathbf{1}}\rightarrow \boldsymbol{\mathit{v}}_{\mathbf{3}}\rightarrow \boldsymbol{\mathit{v}}_{\mathbf{2}}\rightarrow \boldsymbol{\mathit{v}}_{\mathbf{5}}\rightarrow \boldsymbol{\mathit{v}}_{\mathbf{8}}$ **路权和：12** ## 四、最短路问题 练习:9个城市的公路网如图所示。弧上权值为两个城市之间的距离。现有一批货物从*v*1运到*v*9，问哪条路最短？ ![[图论5.png]] 四、最短路问题 **Dijkstra算法只适用于所有wij ≥ 0的情形，当赋权有向图中有负权时，则算法失效。** ```mermaid graph LR v1 --1-->v2 v1 --2-->v3 v3-- -3 -->v2 ``` ## **如何处理具有负权的最短路问题？** ## 四、最短路问题 **当赋权有向图中有负权时，求最短路的方法。** **设从任一点vi到任一个点vj都有一条弧（如果在D中， $（v_i,v_j ）\notin A$ ，则添加弧（vi,vj），且wij=+∞）。** **重要的性质：如果P是从vs到vj的最短路，vi是P中的一个点，那么vs沿P到vi的路是从vs到vi的最短路。** $$\left\{ d\left( v_s,v_j \right) =\min_i \left\{ d\left( v_s,v_i \right) +w_{ij} \right\} \right\} $$ ![[图论5]] 四、最短路问题 当赋权有向图中有负权时，求最短路的方法。 利用如下递推公式： $$d^{(1)}(\nu_s,\nu_j)=w_{sj}$$ 对于 t=2,...,3, $$d^{(t)}(\nu_s,\nu_j)=\min_i\left\{d^{(t-1)}(\nu_s,\nu_i)+w_{ij}\right\}$$ 若进行到某一步，对于所有点 $j$,有 $$d^{(k)}(v_s,v_j)=d^{(k-1)}(v_s,v_j)$$ 算法终止，$d^{(k)}(\nu_s,\nu_j)$ 即为 $\nu_s$ 到各点的最短距离。 ## 6.4 最短路问题 **负回路：D是赋权有向图，C是D中的一个回路，如果C的权W(C)小于0，则C是D中的一个负回路。** **若D中存在负回路，则vs到vj的路的权没有下界。** ## 应用举例——设备更新问题 **某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个五年之内的设备更新计划，使得总的支付费用最少。若已知该种设备在各年年初的价格如表1所示。还已知使用不同时间（年）的设备维修费用如表2所示。** **表1**
第1年 第2年 第3年 第4年 第5年
11 11 12 12 13
**表2**
使用年数 0~1 1~2 2~3 3~4 4~5
维修费用 5 6 8 11 18
## 应用举例——设备更新问题 **把问题化为最短路问题** ![[图论7.png]] 点vi表示“第i年年初购进一台新设备”这种状态。 **弧（vi,vj）表示“在第i年年初购进的新设备一直使用到第j年的年初”。弧上的权值表示总费用。** **制定最优的设备更新计划就等价于寻求从v1到v6的最短路问题。** 大学生涯中的电脑购买计划（最短路问题和动态规划问题） 刚刚收到某高校录取通知书的小明同学打算在4年学习生涯中认真地学习和使用计算机。小明原本计划在开学初买一部新电脑，并使用4年后在二手市场卖掉。这个计划在小明拿到如表所示的电脑行情表时产生了动摇。 除了购置成本，小明预测自己在使用计算机的过程中会有维修、软件维护、硬件升级等额外支出。按照经验，一部电脑使用一年额外支出是100元，连续使用2年是300元，连续使用3年是500元。一部连续使用4年的电脑，额外支出高达1000元。 假设小明购买新电脑或者出售旧电脑的时刻总是在学年交接的时点。请问小明4年大学生涯中，如何安排购买计划，使得支出总额最小。
年级 当年初预测价格 当年末二手价格
第1学年 9900 7500
第2学年 7000 6000
第3学年 6000 4000
第4学年 5000 3500
## 五、网络最大流问题 1.问题的提出 **例6 交通网** ![[图论9.png]] 要求制定一个运输方案使从v1到v6运输的产品数量最多? **快递（货物）运输** ## 五、网络最大流问题 1.问题的提出 ## 五、网络最大流问题 2.基本概念 **网络** **给定一个有向图D = (V,A)，在V中指定一点为发点（始点），记为vs，而另一点为收点（终点），记为vt，其余点为中间点。对于每一个弧(vi,vj) ∈A ，对应有一个c(vi,vj)≥0，简写为cij，称为弧的容量。这样的D叫做一个网络，记为D = (V, A, C) 。** ## 五、网络最大流问题 2.基本概念 **流** **所谓网络上的流是指定义在弧集合A上的一个函数f = {f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)的流量，简称fij 。** ## 五、网络最大流问题 2.基本概念 **可行流** 满足下述两个条件的流f称为可行流： ① 容量限制条件：对于每一条弧(vi,vj) ∈A 0 ≤ fij ≤ cij **② 平衡条件：** - 对于中间点：流出量＝流入量，即对每个i ≠ s,t有 $$ \sum f_{ij}-\sum f_{ji}=0 $$ - 对于发点vs，记 $$ \sum f_{ij}-\sum f_{ji}=v(f) $$ - **对于收点vt，记** $$ \sum f_{ij}-\sum f_{ji}=-v(f) $$ v(f)为可行流f的流量，即发点的净输出量或收点的净输入量。 ## 五、网络最大流问题 2.基本概念 **可行流** ![[图片1.png]] 五、网络最大流问题 2.基本概念 **零流** **令所有弧的流量fij=0,就得到一个零流，其流量v(f)=0** **最大流** **使流量v(f)最大的可行流。** ## 五、网络最大流问题 2.基本概念 **最大流问题的数学模型：** $$\max v(f)$$ $$ s.t. \begin{cases} 0 \leq f_{ij} \leq c_{ij} \\ \sum f_{ij} - \sum f_{ji} = \begin{cases} v(f) & \text{发点} \\ 0 & \text{中间点} \\ -v(f) & \text{始点} \end{cases} \end{cases} $$ 五、网络最大流问题 2.基本概念 **（非）饱和弧、（非）零流弧** **若给定一个可行流f，把网络中使fij = cij的弧称为饱和弧，使fij < cij的弧称为非饱和弧，把fij = 0的弧称为零流弧，fij > 0的弧称为非零流弧。** 五、网络最大流问题 2.基本概念 前向弧u＋、后向弧u－ **若u是联结发点vs和收点vt的一条链，定义链的方向是从vs到vt，则链上的弧分为两类：** **一类是弧的方向与链的方向一致，叫做前向弧，全体记为u＋；** **另一类是弧的方向与链的方向相反，叫做后向弧，全体记为u－。** 五、网络最大流问题 2.基本概念 前向弧u＋、后向弧u－ ![[图论8]] ## 五、网络最大流问题 2.基本概念 **增广链** **设f是一可行流，u是从vs到vt的一条链，若u满足：** **u＋中每一个弧是非饱和弧，即0≤fij|"c_ij=5, f_ij=5"| j ``` 流量调整量为 $\theta_{ij}=c_{ij}-f_{ij}=0$ ```mermaid flowchart LR i -->|"c_ij=5"| j i -->|" f_ij=3"| j ``` 流量调整量为 $\theta_{ij}=c_{ij}-f_{ij}=2$ 增广链后向弧的流量调整为 $\theta = min_{u^-}\left\{ c_{ij} - f_{ij}\right\}$ **流量调整量** ```mermaid flowchart LR i -->|"c_ij=5, f_ij=0"| j ``` **流量调整量为θji = 0** ```mermaid flowchart LR i -->|"c_ij=5"| j j -->|" f_ij=3"| i ``` 流量调整量为θji = fij= 3 **增广链后向弧的流量调整量为** $\theta = min_{u^-} \left\{ f_{ij}\right\}$ 增广过程： 前向弧 $f'_{ij} = f_{ij} + \theta$， 后向弧 $f'_{ij} = f_{ij} - \theta$ 增广后仍然是可行流 ![[图论8]] ![[图片3.png]] 增广链上的前向弧增量 $\theta = \min \left\{ 10-5,5-1,17-2 \right\}=3$ 增广链上的反向弧增量 $\theta = min{f_{ij}} = 3$ ## 五、网络最大流问题 2.基本概念 **截集** 网络 $D=(V,A,C)$,若点集 $V$ 被剖分为两个非空集合 $V_1$ 和 $\overline{V}_1$,使得 $\nu _s\in V_1, \nu _t\in \overline {V}_1\textbf{, 则 把 弧 集 }( V_1, \overline {V}_1) \textbf{称 为 }$分离 $\nu_s,\nu_t$ 的截集。 ![[图论10]] $V_{1}=\{\nu_{1},\nu_{2},\nu_{3}\} \overline V_{1}=\{\nu_{4},\nu_{5},\nu_{6}\}(V_{1},\overline{V}_{1})=\{(\nu_{2},\nu_{4}),(\nu_{3},\nu_{4}),(\nu_{2},\nu_{5}),(\nu_{3},\nu_{5})\}$ ![[图论11]] $$V_1,\bar{V}_1,(V_1,\bar{V}_1)?$$ 截集是从 $\nu_\mathrm{s}$ 到 $\nu_t$ 的必经之路。 截集中所有(前向)弧的容量之和，记为 $c(V_1,\overline{V}_1)$。 $$c(V_1,\overline{V}_1)=\sum_{(v_i,v_j)\in(V_1,\overline{V}_1)}c_{ij}$$ $C(V_1,\bar{V}_1)?$ **最小截集** **容量最小的截集。** 对于任一可行流的流量v(f)都不会超过任一截集的容量。即 $\begin{aligned}&\nu(f)\leq c(V_{1},\bar{V}_{1})\\&\boxed{\nu(f^{*})(最大流)=c(V_{1}^{*},\bar{V}_{1}^{*})(最小截集)}\end{aligned}$ ## 五、网络最大流问题 3.基本定理 **最大流量最小截集定理** **任意网络 D 中，从 vs 到 vt 的最大流的流量等于分离 vs，vt 的最小截集的容量。** $\begin{aligned}\boxed{\nu(f^{*})(最大流)=c(V_{1}^{*},\bar{V}_{1}^{*})(最小截集)}\end{aligned}$ ## 五、网络最大流问题 3.基本定理 证明 $f^* \textbf{是 最 大 流 , }D$ 中不存在关于 $f^* \textbf{增 广 链 。 }$ 反证法：若存在增广链 $u$,令 $\theta=\min\left\{\min_{x^+}\{c_{ij}-f_{ij}^*\},\min_{x--}\{f_{ij}^*\}\right\}$, 由增广链的定义可知，$\theta>0$,令 $$\begin{aligned}&f_{ij}^{**}=\begin{cases}f_{ij}^{*}+\theta&(v_{i},v_{j})\in u^{+}\\f_{ij}^{*}-\theta&(v_{i},v_{j})\in u^{-}\\f_{ij}^{*}&(v_{i},v_{j})\not\in u\end{cases}\\\end{aligned}$$ 则可以得到是一个可行流，且 $v(f^{**})=v(f^*)+\theta>v(f^*)$ 这与 $f^*$ 是最大流的假设矛盾。 ## 五、网络最大流问题 3.基本定理 **可行流 f\*是最大流，当且仅当不存在关于 f\*增广链。** **② 证明 D 中不存在关于 f\*的增广链，则 f\*是最大流。** ②证明 D 中不存在关于 f \*的增广链，则 f* 是最大流。 定义 V₁*，令 vₛ∈V₁* 若 vᵢ∈V₁\*且 fᵧ < cᵧ，则令 vⱼ∈V₁* 若 vᵢ∈V₁\*且 fⱼᵢ > 0，则令 vⱼ∈V₁* 因为不存在 f \*的增广链，故 vₜ∉V₁* 记 $\overline{V}_1^* = V \setminus V_1^*$，得到一个截集 $(V_1^*, \overline{V}_1^*)$，则必有 $f_y^* = \begin{cases} c_y & (v_i, v_j) \in (V_1^*, \overline{V}_1^*) \\ 0 & (v_i, v_j) \in (\overline{V}_1^*, V_1^*) \end{cases}$ 所以 $v(f^*) = c(V_1^*, \overline{V}_1^*)$，则 f* 是最大流。 五、网络最大流问题 3.基本定理 **可行流 f\*是最大流，当且仅当不存在关于 f\*增广链。** 该定理的证明提供了寻求最大流的一个方法。若一个可行流f存在增广链，按照定理前部分证明的方法改进f，增加流量，若没有增广链，则得到最大流；利用定理后部分证明定义 V 1\*的办法，可以判断D中是否有f的增广链。 ## 五、网络最大流问题 4. 寻求最大流的方法－标号法 **基本思想** **用给顶点标号的方法定义 V 1* ，在标号过程中，有标号的顶点表示是 V 1* 的点，一旦 vt 有了标号，表明找到一条增广链；若标号过程进行不下去，而 vt 未标号，则说明不存在增广链，该流即为最大流，同时可以得到一个最小截集。** ## 五、网络最大流问题 4. 寻求最大流的方法－标号法 **基本思想** ```mermaid graph LR A[标号过程（寻找增广链）]-->B[调整过程（调整增广链）] B-->A ``` **寻找增广链** **标号过程** **调整过程** **调整增广链** ## 五、网络最大流问题 4. 寻求最大流的方法－标号法 （1）标号过程 **表示该标号的前一步是从哪一点得来的，以便找出增广链。**（第一标号） **(第一标号，第二标号)** **用来确定增广链的调整流量θ，改进 f 用的。**（第二标号） ## 五、网络最大流问题 4. 寻求最大流的方法－标号法 （1）标号过程 **首先，给出发点 vs 以标号(0，+∞)；** **选择一个已经标号的点 vi，对于 vi 的所有未给标号的邻接点 vj 按下列规则处理：** ① 若弧(vi, vj) ∈A，且fij < cij,则令θ = cij - fij，并给vj以(+vi, θ); **② 若弧(vj, vi) ∈A，且 fji > 0,则令θ = fji，并给 vj 以(-vi, θ)。** **重复上述步骤，直至收点 v t 被标号，表明找到一条从 vs 到 vt 的增广链，转入调整过程。否则，当标号过程进行不下去时，则算法结束，当前可行流即是最大流。** 五、网络最大流问题 4. 寻求最大流的方法－标号法 （2）调整过程 首先，按 $v_{i}$ 及其他点的第一个标号，利用反向追踪的办法找出增广链 $u$，然后沿着增广链调整 $f$ 以增加流量，得到新的可行流 $f'$，调整方法如下： $$\theta = \min\left\{ \min_{u^+} \{c_{ij} - f_{ij}\}, \min_{u^-} \{f_{ij}\} \right\} \to f'_{ij} = \begin{cases} f_{ij} + \theta & (v_i, v_j) \in u^+ \\ f_{ij} - \theta & (v_i, v_j) \in u^- \\ f_{ij} & (v_i, v_j) \not\in u \end{cases}$$ 调整以后去掉所有标号，回到标号过程，对可行流 $f'$ 重新标号。 ## 五、网络最大流问题 **用标号法求例 6 所示网络的最大流。弧旁数字表示（cij, fij）** ## **（1）标号过程** ![[图论12]] **① 给 vs 标号(0,+∞)** ② 检查vs，在弧(vs,v2)，f12 = c12，不满足标号条件；弧(vs,v1)，fs1 0，则给v2 标号(-v1,1)。 ④ 检查v2，弧(v2,v4)，f24 < c24,则给v4 标号(v2,1)。弧(v3,v2)，f32 大于 0，则给v3 标号(-v2,1)。 ![[图论13]] ⑤ 选v3 为检查点，弧(v3,vt)，f3t 当前可行流为最大流，最大流量为v(f)＝ 25 应用举例 1. 某城市有 7 个供水加压站，分别用节点 1，节点 2，……，节点 7 表示。见下图。其中节点 l 为水厂，各泵站间现有的管网用相应节点间的边表示。现规划在节点 7 处建一个开发区，经对现有管网调查，各段管网尚可增加的供水能力(万吨／日)如下图中各边上的数值所示。依照现有管网状况，从水厂(源点)到开发区(汇点)，每日最多可增加多少供水量? ![[图片8.png]] 现在某部队进行实战演习，红军侦获了蓝军的物资供给线上的一条河流的工事地图，如图所示。在河流 A 岸和 F 岸之间的江面上有 B、C、D 和 E 四块洲岛，蓝军借助地势搭建了 1 至 13 号浮桥。红军指挥员决定由空对地制导轰炸浮桥的方式，彻底切断蓝军的供给线。请帮助红军制定出最有效的轰炸方案，以破坏最少的浮桥达到该战术目的。 ![[图片9.png]] ![[图片10.png]] ## 六、最小费用最大流问题 - **在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。** - 最小费用最大流问题的一般提法是：在一个给定的网络 D = (V,A,C,B)的每一条弧上，除了给出容量 cij之外，还给出了每一弧上单位流量的费用 bij，求一个最大流 f，使流量 f的总费用 - $b(f)=\sum_{(\nu_i,\nu_j)\in A}b_{ij}f_{ij}$ **达到最小。** ## 六、最小费用最大流问题 $$ \begin{align} b(f')-b(f) &=\sum_{\mu^{+}}b_{ij}(f_{ij}'-f_{ij})-\sum_{\mu^{-}}b_{ij}(f_{ij}-f_{ij}') \\ &=\sum_{\mu^{+}}b_{ij}-\sum_{\mu^{-}}b_{ij} \end{align} $$ 我们将 $\sum_{\mu^{+}}b_{ij}-\sum_{\mu^{-}}b_{ij}$ 叫做这条增广链的费用。 ![[图片11.png]]] $\boldsymbol{\mathit{b}}(\boldsymbol{\mathit{u}})=(\mathbf{3}+\mathbf{1}+\mathbf{4})-(\mathbf{5})=\mathbf{3}$ ## 六、最小费用最大流问题 - 可以证明 ：如果可行流 f在流量为v(f)的所有可行流中的费用最小，并且μ是关于f的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的新可行流f ’ ，也是流量为v(f ’)的所有可行流中的最小费用流。依次类推，当 f ’ 是最大流时，就是所要求的最小费用最大流。 ## 六、最小费用最大流问题 - 求解思路：零流f = 0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f ={0}开始。下面的问题是：若已知f是流量v(f)的最小费用流，余下的问题是如何去寻找关于f的最小费用增广链。为此，可构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而把D中每一条弧(vi,vj)变成两个相反方向的弧(vi,vj)和(vj,vi)。定义W(f)中弧的权wij为 $w_{ij}=\begin{cases}b_{ij}&\text{,当}f_{ij}0\\+\infty&\text{,当}f_{ij}=0&\end{cases}$ **并且将权为+∞的边去掉。** 于是，在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中，寻求从vs到vt的最短路。 ## 六、最小费用最大流问题 **求解算法如下：** （1）取零流f (0) = 0。 （2）如果在第k-1步得到最小费用流f (k-1) , 则构造赋权有向图W(f (k-1)) 。 （3） 在赋权有向图W(f (k-1))中，寻求从vs到vt的最短路。如果不存在最短路，则f (k-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应的增广链μ。 （4）在D中与这条最短路相应的增广链μ上，对f (k–1)进行调整，取调整量 **令：** $$\theta=\min\left\{\min_{\mu^{+}}\left(c_{ij}-f_{ij}^{(k-1)}\right),\min_{\mu^{-}}\left(f_{ij}^{(k-1)}\right)\right\} \ f_{ij}^{(k)}=\begin{cases}f_{ij}^{(k-1)}+\theta\text{,在}\mu^+\text{上}\\f_{ij}^{(k-1)}-\theta\text{,在}\mu^-\text{上}\\\text{其它不变}&\end{cases}$$ **得到新的可行流f(k)，再对f(k)重复上述步骤。** ## 六、最小费用最大流问题 例7 求图所示网络中的流量为10的最小费用流，弧旁的权是（ cij , bij ）。 ![[图片13.png]] ![[图片14.png]] ![[图片15.png]] ![[图片2.png]] 图 j $W（f^{(4)}）$ ![[图片16.png]] **图 i** **f (4),v ( f(4)) =11** **b( f (4))=3\*4+8\*1+4\*2+ 4\*3+ 4\*2+ 7\*1=55** ## ***应用案例——预搅拌混凝土公司的物料运送方案*** **某混凝土公司负责提供一个建筑工地的预搅拌混凝土，运送方式以整车配送。由于运输的混凝土是粉尘污染物质，所以有关部门规定了该公司在路段上每天的最高运输往返辆次。每车每个往返计算流量1车。搅拌站与施工地点之间的运输网络以及各条的路径的容量（车/天）和单车成本（百元）见下图。请为该公司制定以下运输方案：** **（1）公司的最小费用最大流是多少？最小费用是多少？如何安排运输路线？** **（2）公司如果必须运送10车，则此时最小费用是多少？如何安排运输路线？** ![[图片17.png]] ## 七、中国邮递员问题 - 中国邮递员问题的图论表达：给定一个连通图，在每边*ei*上赋予一个非负权值*w*(*ei*)，要求一个圈（未必是简单圈），过每边至少一次，并使圈的总权最小。 管梅谷 华罗庚 ## 七、中国邮递员问题 - **欧拉链：给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这个链为欧拉链。** - **欧拉圈：若存在一个简单圈，过每边一次，且仅一次，则称这个圈为欧拉圈。** - **欧拉图：一个图若有欧拉圈，则为欧拉图。** - **显然，一个图若能一笔画出，这个图必是欧拉图**。 ## 七、中国邮递员问题 - **定理：连通多重图G有欧拉圈，当且仅当G中无奇点。** - **推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点。** ## 七、中国邮递员问题 - **若中国邮递员问题所给出的街道图没有奇点，那么沿着欧拉回路走，肯定是每条街道走过一次且仅一次，他走的路程就是一条最短路线。** - **若有奇点，则必须在某些街道上重复一次或多次。** - **中国邮递员问题可以叙述为在一个有奇点的图中，要求增加一些多重边，使新图不含奇点，并且所加多重边的总权最小。** ## 七、中国邮递员问题 - **中国邮递员问题的求解方法：奇偶点图上作业法** - **第一步：确定第一个可行方案** - **根据任何一个图中，奇点个数必为偶数。我们可以将图中的奇点配成对。对每一对奇点之间的链上增加多重边，可使新图中必无奇点。** ![[图片19.png]] ## 七、中国邮递员问题 - **第二步：调整可行方案，使重复边总权下降** - **（1）在最优方案中，图的每一边上最多有一条重复边。** - **（2）在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半。** ![[图片20.png]] ## 七、中国邮递员问题 - **第三步：判断最优方案** - **若每一可行方案满足上述（1）和（2），则该方案即为最优方案；否则，对方案继续调整，直到（1）和（2）满足为止。** ## 七、中国邮递员问题 - 中国邮递员问题的求解方法：奇偶点图上作业法 ![[图片21.png]] ## 七、中国邮递员问题 - **问题：如果已知图G是可以一笔画出的，怎么一笔画出来呢？（Fleury法－欧拉回路生成算法）** **（1）找到一个出发点V0(若图中有两个奇点，任取其一)** **（2）找一条与v0相连的边，伸展欧拉路（链）（选边的时候应注意，最后再选割边）** **（3）将选取的边所连的另一个点为当前顶点，去掉该边，重复步（2），直至经过所有边为止。** ![[图片31.png]] > [!proof]- 证明状态 > 本笔记含数学结论；已保留原文。未给出证明的结论将在后续按定义、引理和推导链补证。