Problem 107
Minimal network
The following undirected network consists of seven vertices and twelve edges with a total weight of 243.
The same network can be represented by the matrix below.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 16 | 12 | 21 | - | - | - |
| B | 16 | - | - | 17 | 20 | - | - |
| C | 12 | - | - | 28 | - | 31 | - |
| D | 21 | 17 | 28 | - | 18 | 19 | 23 |
| E | - | 20 | - | 18 | - | - | 11 |
| F | - | - | 31 | 19 | - | - | 27 |
| G | - | - | - | 23 | 11 | 27 | - |
However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 ? 93 = 150 from the original network.
Using network.txt (right click and ‘Save Link/Target As…’), a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.
最小网络
下面这个无向网络包含有7个顶点和12条边，其总重量为243。
这个网络也可以用矩阵的形式表示如下。
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 16 | 12 | 21 | - | - | - |
| B | 16 | - | - | 17 | 20 | - | - |
| C | 12 | - | - | 28 | - | 31 | - |
| D | 21 | 17 | 28 | - | 18 | 19 | 23 |
| E | - | 20 | - | 18 | - | - | 11 |
| F | - | - | 31 | 19 | - | - | 27 |
| G | - | - | - | 23 | 11 | 27 | - |
然而，我们其实可以优化这个网络，移除其中的一些边，同时仍然保证每个顶点之间都是连通的。节省重量最多的网络如下图所示，其总重量为93，相比原来的网络节省了243 ? 93 = 150。
在文本文件network.txt中存放了一个包含有40个顶点的网络的连通矩阵。移除其中冗余的边，同时仍然保证每个顶点之间都是连通的，求最多能节省的重量。