Question

数学建模难题求大神帮解答~

《1》某省共有10个大中城市，各城市之间的连接示意图如图1所示（单位：km），求这10个城市的最优连线。

图1：城市之间的连接示意图

《2》张先生家住在D城市，每年的假期都会到Y市度假。由于张先生是一位旅游爱好者，所以他希望每年开车去度假所选择的路线互不相同。经过仔细的查看地图之后，张先生确定了几条从D市到Y市的路线，如图2所示。利用最大流问题的数学模型，为张先生找出：(1)从D市到Y市全部边不同的线路（即任意两条线路不经过相同的边）；(2)从D市到Y市全部点不同的线路（即任意两条线路不经过相同的点）。

图2：D市到Y市的道路网络示意图





Answer 1

其实就是求最小生成树啦

先将所有数字从大到小排序：

443    415    359    345    246    215    213    199    195    180    167    163    122    92    79

再从大到小依次去掉，但不能让图不连通，也不能有回路

去掉：443    415    359    246    215    213     

余下：345       199    195    180    167    163    122    92    79