七.网络模型

1. 最小(支撑)树问题

最小部分树求解：

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

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

1. 最短路问题

求最短路有两种算法：

求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法

求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法

1. 最短路问题的数学模型
2. 最大流问题：最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。