高速公路的区段通行能力分析。高速公路的S点到T点之间的网络结构如图5- 38所示。车流从S点分流后在T点汇流。分流后的车辆可以由As到A2或者As到A之间的单向立交匝道变更主干道。各个路段的最大通行能力分别标在了图上。现在请求出高速公路S到T之间的最大通行能力。公路运能饱和时，各路段状态如何(流量是多少，是有剩余、完全空闲，还是饱和)?由S到A1为15，S到A2为5，A1到A3为13，A3到A2为6，A2到A4为12，A4到A1为4，A3到T为7，A4到T为10.

根据网络结构，可以使用最小割算法来求解高速公路S到T之间的最大通行能力。具体步骤如下：

1. 构建图的邻接矩阵。根据给定的路段通行能力，可以得到以下邻接矩阵：

   S  A1  A2  A3  A4  T
S  0  15  5   0   0   0
A1 15  0   0  13   4   0
A2 5   0   0   6  12   0
A3 0  13   6   0   0   7
A4 0   4  12   0   0  10
T  0   0   0   7  10   0

2. 使用Ford-Fulkerson算法求解最小割。从源点S开始，可以找到一条增广路径S-A1-A3-T，其容量为min(15, 13, 7) = 7。将这个容量加入到最小割中，同时将这个容量从对应的边上减去。得到更新后的邻接矩阵：

   S  A1  A2  A3  A4  T
S  0   8  5   0   0   0
A1 8   0   0   6   4   0
A2 5   0   0   6   7   0
A3 0   6   6   0   0   1
A4 0   4   7   0   0  10
T  0   0   0   1  10   0

继续找到增广路径S-A2-A4-T，其容量为min(5, 7, 10) = 5。将这个容量加入到最小割中，同时将这个容量从对应的边上减去。得到更新后的邻接矩阵：

   S  A1  A2  A3  A4  T
S  0   3  0   0   2   0
A1 3   0   0   3   1   0
A2 0   0   0   6   2   0
A3 0   3   3   0   0   1
A4 2   1   2   0   0   7
T  0   0   0   1   7   0

继续找到增广路径S-A1-A4-T，其容量为min(3, 1, 7) = 1。将这个容量加入到最小割中，同时将这个容量从对应的边上减去。得到更新后的邻接矩阵：

   S  A1  A2  A3  A4  T
S  0   2  0   0   1   0
A1 2   0   0   2   0   0
A2 0   0   0   6   1   0
A3 0   2   2   0   0   0
A4 1   0   1   0   0   6
T  0   0   0   0   6   0

此时无法找到增广路径了，停止算法。最小割的容量为6，即高速公路S到T之间的最大通行能力为6。

3. 分析各路段状态。根据最小割的定义，将图中的节点分成两个集合S和T，使得S到T的最小割的容量最大。在本题中，最小割的容量为6，将图中节点分成两个集合后，从S集合到T集合的边的通行能力之和为6。因此，S到A1、A1到A3、A3到T、A4到T这四条边将达到饱和状态，其它边将有剩余空间。具体来说，S到A1、A1到A3、A3到T、A4到T这四条边的流量都为其容量，分别为15、13、7、6；其它边的流量都为其容量减去对应边上的割值，分别为2、6、0、1、4、5。