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

《最小树最短路与最大流问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、见表4-6。点击Result→GraphicSolution，显示各点的流量图4-5。表4-6图4-5