建议先看上一篇基本概念篇 https://blog.csdn.net/weixin_45755332/article/details/106899147

最小生成树

基本概念和方法

树：没有圈的连通图
图一是，图二有圈，图三灭有连通

生成子图：对于无向图 G =(V,E) ,保留G的所有点，而删掉G的边或者保留部分 G 的边，所获得的图称为 G 的生成子图。
如左图去了那两条边，剩下的那个图就是生成子图

生成树：若图 G 的一个生成子图是一个树，则称这个生成子图为生成树。上面右图就是一个最小生成树

最小生成树问题：在一个赋权的连通的无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。

最小生成树的常用方法：

1. 破圈法：任取一圈，去掉圈中最长边，直到无圈。

• 把这些圈的权值最大的去掉，剩下的那个生成树就是最小生成树
• 注：当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一 条边。最小生成树有可能不唯一，但最小生成树的长度相同

2. 加边法（避圈法）：2.加边法(避圈法) ：取图G的n个孤立点｛v1，v2，…， vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）

• 开始是六个顶点，然后根据那张赋权图，按权值从小到大的顺序来进行连接
  

连接完第四条线时，v1→v2和v3→v6权值都是5，但v1→v2连接的话就是圈了，所以只能是v3→v6

3. prim算法构造最小生成树：
   设置两个集合P和Q,其中P用于存放的最小生成树G中的顶点，集合Q存放的最小生成树G中的边。令集合P的初值为
   $P={v_1}$

   P=v1​ （假设构造最小生成树时从顶点
   $v_1$

   v1​ 出发），集合Q的初值为
   $Q=theta$

   Q=θ 。
   prim算法的思想是，从所有
   $pin P,v in V-P$

   p∈P,v∈V−P ,的边中，选取具有最小权值的边 pv ，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到 P=V 时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。

下面用代码来解下面最小生成树
用result 3*n 的第一、二、三行分别表示生成树边的起点、终点、权集合。

clc;clear; a=zeros(7); a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;  a=a+a';a(a==0)=inf; result=[];p=1;tb=2:length(a); while size(result,2)~=length(a)-1    temp=a(p,tb);temp=temp(:);    d=min(temp); [jb,kb]=find(a(p,tb)==d,1); %找第1个最小值    j=p(jb);k=tb(kb);   result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result     result = 1 2 5 4 4 7 2 5 4 6 7 3 50 40 50 30 42 45 

下面用避圈算法的MATLAB程序计算上题，结果一样

clc;clear; a(1,[2,3])=[50,60]; a(2,[4,5])=[65,40]; %这里给出邻接矩阵的另外一种输入方式 a(3,[4,7])=[52,45]; a(4,[5,6])=[50,30]; a(4,7)=42; a(5,6)=70; [i,j,b]=find(a); data=[i';j';b'];index=data(1:2,:); loop=length(a)-1; result=[]; while length(result)<loop    temp=min(data(3,:));    flag=find(data(3,:)==temp);    flag=flag(1);    v1=index(1,flag);v2=index(2,flag); if v1~=v2       result=[result,data(:,flag)];    end    index(find(index==v2))=v1; data(:,flag)=[]; index(:,flag)=[]; end result  result = 4 2 4 3 1 4 6 5 7 7 2 5 30 40 42 45 50 50 

某大学准备对其所属的7各学院办公室计算机联网，这个网络的可能联通的途径如图11- -14所示，图中V1,——,V7表示7个学院办公室，图中的边为可能联网的途径，边上所赋的权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。

注：这是一个最小生成树问题，不是最短路问题，因为他所有的都要连接上。

clc;clear; a=zeros(7); a(1,7)=3; a(1,6)=10; a(2,7)=3; a(2,3)=1; a(3,4)=7; a(3,5)=2;a(3,7)=4; a(4,5)=8; a(5,6)=4; a(5,7)=5; a(6,7)=3; a=a+a';a(a==0)=inf; result=[];p=1;tb=2:length(a); while size(result,2)~=length(a)-1    temp=a(p,tb);temp=temp(:);    d=min(temp); [jb,kb]=find(a(p,tb)==d,1); %找第1个最小值    j=p(jb);k=tb(kb);   result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[ ]; end result   result = 1 7 2 3 7 3 7 2 3 5 6 4 3 3 1 2 3 7 

最大流问题

基本概念

最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。
如图所示的网络图中定义了一个发点v1，定义了一个收点v7，其余点v2，v3，…，v6为中间点，称为转运点。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。

设
$c_{ij}$

cij​为弧（i，j）的容量，
$f_{ij}$

fij​为弧（i，j）的流量。
容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合
$f={f_{ij}}$

f=fij​称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。
注意：流量只是发出点的发出量或流入点的流入量，中间点的流入量和流出量是一样的。
概念区分
链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。
前向弧：与链的方向相同的弧称为前向弧。
后向弧：与链的方向相反的弧称为后向弧。
增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：
1.所有前向弧上
$f_{ij}<C_{ij}$

fij​<Cij​
2.所有后向弧上fij>0

Ford-Fulkerson标号算法

• 第一步： 找出第一个可行流，例如所有弧的流量fij =0；

• 第二步：对点进行标号找一条增广链。

  • （1）发点标号（∞）
  • （2）选一个点
    $v_i$

    vi​ 已标号并且另一端未标号的弧沿着某条链向收点检查：

    • A.如果弧的方向向前（前向弧）并且有
      $c_{ij} < f_{ij}$

      cij​<fij​，则vj标号:
      $θ_j＝c_{ij}－f_{ij}（容量-流量）$

      θj​＝cij​－fij​（容量−流量）

    • B.如果弧的方向指向vi（后向弧）并且有
      $f_{ji}$

      fji​>0，则vj标号:
      $θ_j＝f_{ji}$

      θj​＝fji​
      当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。

• 第三步：调整流量

  • （1）求增广链上点vi 的标号的最小值，得到调整量
    $theta=min_j{theta_j}$

    θ=minj​θj​
    

  • （2）调整流量
    
    得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止.

定理1 可行流f是最大流的充分必要条件是不存在发点到收点的增广链 .

例 求图中的发点v1到收点v7的最大流.

先假设已经给定了这个可行流，可以检查一下，发点和接收点的流量是相同的，都是16；每个点的流入量和流出量也是相同的。

然后进行第一轮标号

• 先看｛
  $1→2$

  1→2｝正向弧，8-6=2，圈2上就标号为2；

• ｛
  $2→4$

  2→4｝｛
  $2→6$

  2→6｝都是正向弧，但流量已经到达最大流了，所以不能增加了

• ｛
  $2→5$

  2→5｝反向弧，所以圈3直接标3-0=3

• ｛
  $3→4$

  3→4｝正向弧，圈4标3，当然也可以｛3→6→4｝这样多一条路径但结果一样就不用这个了

• ｛4→7｝正向弧，圈7标号10-3=7

增广链μ＝{(1,2)，(3,2)，(3,4)，(4,7) },μ+={(1,2)，(3,4)，(4,7)},μ－={(3，2)}，调整量为增广链上点标号的最小值 θ＝min{∞，2，3，3，7}＝2，对其进行调整

这里有反向弧，调整后是正向弧+2，反向弧-2

第二轮
与第一轮是一样的，要说的就是｛3→2｝虽然没有到最大容量，但圈2往后不能增加了，所以直接不用看

增广链μ＝μ＋＝{(1,3)，(3,4)，(4,7) }，调整量为 θ＝min{∞，4，1，5}＝1
这里没有反向弧，经过的弧流量都加1

第三轮

增广链μ＝μ＋＝{(1,3)，(3,6)，(6,4)，(4,7) }，调整量为 θ＝min{∞，3，1，2，4}＝1
全是正向弧，都加1

经过排查只有这些增广链了，所以可以下结论了
最大流量
$color{Blue}v＝f12+f13＝8+12=20=color{Red}f67+f47+f57=6+2+7+7$

v＝f12+f13＝8+12=20=f67+f47+f57=6+2+7+7
上面是有向图，无向图就更简单了，直接全是加就完了。

截集-截量法

将图G＝（V，E）的点集分割成两部分
$V_1,overline{V_1}$

V1​,V1​​并且
$v_sin{V_1}$

vs​∈V1​以及
$v_tinoverline{V_1}$

vt​∈V1​​,则箭尾在V_1箭头在
$overline{V_1}$

V1​​ 的弧集
$V_1,overline{V_1}$

V1​,V1​​称为一个截集，截集中所有弧的容量之和称为截集的截量。

下图所示的截集为
$V_1,overline{V_1}$

V1​,V1​​={(1,2),(3,4),(3,5)}，截量C=6+2+2=10;

为什么没有｛2，3｝呢？是因为弧内的① ③ 要指向弧外的 ② ④ ⑤ ⑥ ，｛2，3｝是弧外的指向弧内的了。

又如下图所示的截集为
$V_1,overline{V_1}$

V1​,V1​​= {（2,4),(3,(5,4)(5,0）}
截量
$C(V_1,overline{V_1})$

C(V1​,V1​​)=4+2+6+9=21

下图所示的截集为
$V_1,overline{V_1}$

V1​,V1​​= {(2,4),(2,5),(3,4),(3,5)}
截量C=4+1+2+2=9

所有截量中此截量最小且等于最大流量，此截集称为最小截集。经过计算这个图最小截量就是9，所以最大流量就是9；

$color{Red}定理2 最大流量等于最小截集的截量。$

定理2最大流量等于最小截集的截量。