最小树最短路与最大流问题

《最小树最短路与最大流问题》由会员分享，可在线阅读，更多相关《最小树最短路与最大流问题（4页珍藏版）》请在金锄头文库上搜索。

1、最小树、最短路与最大流问题最小树与最短路问题的运算程序是 Network Modeling（网络模型） ，最小部分树选择Minimal Spanning Tree ，最短路选择 Shortest Path Problem，最大流问题选择 Maximal Flow Problem。1、 如图 4-1 所示， （1）求解最小部分树问题， （2）分别求 v1 到 v7 和 v2 到 v6 的最短路及最短路长。（1）进入图 4-2 所示界面，选择 Minimal Spanning Tree， ，输入节点数 7。对照图 4-1 输入表 4-1 所示的数据。两点间的权数只输入一次（上三角） 。图 4-1

2、图 4-2表 4-1点击菜单栏 Solve and Analyze，输出表 4-2 最小树结果，最小树长为 15。点击菜单栏Results Graphic Solution,，显示最小部分树形，见图 4-3。表 4-2图 4-3（2）进入图 4-2 所示界面，选择 Shortest Path Problem，如果是有向图就按弧的方向输数据，本例是无向图，每一条边必须输入两次，无向边变为两条方向相反的弧，见表 4-3。点击Solve and Analyze 后系统提示用户选择图的起点和终点，系统默认从第一个点到最后一个点，用户选择后系统不仅输出 v1 到 v7 路径和路长，还显示了 v1 到各点

3、的最短路长 12，见表 4-4。点击 ResultGraphic Solution，显示 v1 到各点的最短路线图 4-4。同理，选择 v2到 v6 得到最短路长为 6，路径为 v2 v 3v 6。表 4-3表 4-4图 4-42、 用 WinQSB 软件求解例 7.15。进入图 4-2 所示界面，选择 Maximal Flow Problem。输入节点数 6，输入表 4-5 所示的数据，输入弧容量即可。表 4-5点击 Solve and Analyze 后系统提示用户选择图的起点和终点，系统默认从第一个点到最后一个点，用户选择后系统不仅输出 v0 到 v5 路径和流量，还显示了最大流量 18，见表 4-6。点击 ResultGraphic Solution，显示各点的流量图 4-5。表 4-6图 4-5