运筹说第82期 | 算法介绍之图与网络分析（二）

本文主要是介绍运筹说第82期 | 算法介绍之图与网络分析（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本期我们继续进行运筹学之图与网络分析算法的讲解，我们将对图与网络分析的基础知识进行一个简单的回顾，并介绍求解最大流问题和最小费用最大流的MATLAB和Python相关代码，以帮助大家利用工具快速求解最大流问题和最小费用最大流问题，做到事半功倍。由于篇幅有限，小编接下来只展示部分代码，小伙伴们可以关注“运筹说”公众号→后台回复“算法介绍之图与网络分析（二）”获取完整代码。话不多说，我们一起来看看吧！

一、基础知识

1、最大流问题

★ 最大流有关概念

(1) 可行流：对任一G中的边(vi, vj)有流量fij，称集合f={fij}为网络G上的一个流。且称满足容量限制条件和平衡条件的流f为可行流。

①容量限制条件：对G中每条边(vi, vj)，有0≤fij≤cij；

②平衡条件：对中间点vi有∑j fij =∑k fki，即物资的输入量与输出量相等。

(2)总流量：对收、发点vt，vs，有∑i fsi =∑j fjt=W，W为网络流的总流量。

(3)可增广链：容量网络G，若μ为网络中从vs，vt的一条链，给μ定向为从vs到vt，μ上的边凡与μ同向称为前向边，凡与μ反向称为后向边，其集合分别用μ+和μ-表示，f是一个可行流，如果满足

$\begin{cases}0\le f_{ij}<c_{ij}\cdot(v_i,v_j)\in\mu^+\\ c_{ij}\ge f_{ij}>0\cdot(v_i,v_j)\in\mu^-\end{cases}$

则称μ为从vs到vt的(关于f的)可增广链。

(4) 可增广链的意义:沿着这条链从发点到收点输送的流，还有潜力可挖。

★ 最大流-最小割定理

(1) 割集：容量网络G=(V，E，C)，vs，vt为发、收点，若有边集E’为E的子集，将G分为两个子图G1，G2，其顶点集合分别记S，S’，S∪S’=V，S∩S’=∅，vs，vt分属S，S’，满足：①G(V，E- E’)不连通；②E’’为E’的真子集，而G(V，E- E’’)仍连通，则称E为G的割集，记E’=(S，S’)。

(2) 割集容量：割集(S，S’)中所有始点在S，终点在S’的边的容量之和，称为(S，S’)的割集容量,记为C(S，S’)。容量网络G的割集有多个，其中割集容量最小者称为网络G的最小割集容量（简称最小割）。

(3) 最大流-最小割定理：任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。

(4) 最小割的意义：网络从发点到收点的各通路中，由容量决定其通过能力，最小割则是这些路中的咽喉部分，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部分的通过能力。

★ 问题描述

求网络中一个可行流，使其流量达到最大，这种流称为最大流，这个问题称为（网络）最大流问题。

★ 算法流程