最小树形图问题

一个网络图可以有多个生成树．记N的所有生成树的集合为：

设

则称 T * 为网络N的一棵最小树树形图，简称最小树。

求最小树的两种方法，是避圈法与破圈法 。

最小树形图问题避圈法

从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。

最小树形图问题破圈法

① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；

② 去掉该圈中权数最大的边；

反复重复 ① ② 两步，直到最小树。

最小树形图问题Kruskal 算法

将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n-1 条边，则 T 是最小生成树。

树形图的概念

无圈且连通的无向图称为树。树一般记为T。作为树定义还可以有以下几种表述：

(1) T 连通且无圈或回路；

(2) T 无圈且有n－1条边（如果有n个结点）；

(3) T 连通有n－1条边；

(4) T 无回路，但不相邻的两个结点之间联以一边，恰得一个圈；

(5) T 连通，但去掉T 的任意一条边，T 就不连通了；（亦即在点集合相同的图中，树是含边数最少的

连通图。）

(6) T 的任意两个结点之间恰有一条初等链。

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。

在实际中：n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

由割集的定义不难看出，无论拿掉那个割集，发点v_s到收点v_t便不再相通，所以任何一个可行流都会经过割集，且不会超过任一割集的容量。最小割如同瓶颈一般，即使是最大流也无法超过最小割，网络的最大流与最小割容量满足下面的定理（证明略）。

最大流问题定理一

设f为网络G=(V,E,C)的任一可行流，流量为v(f)，

最大流问题定理二

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不带任一割集的容量，因此割集一定是最小的割集。

任一网络G中，从v_s到v_t的最大流的流量等于分离v_s、v_t的最小割的容量（最小的割集的容量）。

最大流问题前后向弧

一条从起点v_s到终点vt的链μ，规定从v_s到v_t的方向为链μ的方向，链上与μ方向一致的边叫前向弧（边），记作μ^-；与μ方向相反的边称为后向弧（边），记作μ 。

最大流问题可增广链

f是一个可行流，f_ij表示由i点指向j点的流量，如果满足前向弧的流量非负且小于容量，或后向弧的流量大于0且不超过容量：

则称μ为从v_s到v_t的关于f的可增广链。

可增广链的实际意义是：沿着这条从v_s到v_t输送的流，仍有潜力可挖，只要前向弧的流量增加或后向弧的流量减少，就可以将截集的流量提高。调整后的流，在各点仍满足平衡条件及容量限制条件，仍为可行流。

从另一个角度来说，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要条件是不存在从v_s到v_t的可增广链。

在一个网络

当它大于0时，表示该点可供给一定量的货物；

当它小于0时，表示该点需求一定量的货物；

当它为0时，表示该点既不需要也不能提供货物，这样的点可以作为货物的中转点。

另外，假设网络中供需是平衡的。

网络

最小费用流问题是求一个可行流

该问题存在多项式时间算法。