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.
    ABCDEFG
A-161221—
B16–1720–
C12–28-31-
D211728-181923
E-20-18–11
F–3119–27
G—231127-
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.

To solve this problem, we can use a famous algorithm in graph theory called the Minimum Spanning Tree (MST) algorithm. This algorithm is used to find the subset of edges in a connected, edge-weighted (un)directed graph- which connects all the vertices together- without any cycles and with the minimum possible total edge weight.

Here’s the step-by-step process to solve the problem:

Step 1: Convert the Matrix to a Graph

The text file provided contains the weights of the edges between the vertices in matrix form. The first step is to convert this matrix into a weighted, undirected graph.

Each entry in the matrix represents the weight of the edge between the corresponding vertices. For example, if we have a vertex ‘i’ and a vertex ‘j’, the entry in the i-th row and j-th column of the matrix gives the weight of the edge between ‘i’ and ‘j’.

After converting the matrix into an undirected graph, you will have a graph with vertices representing the 40 vertices in the matrix, and the edges between the vertices representing the connections as provided in the matrix.

Step 2: Applying Minimum Spanning Tree Algorithm

With the graph in place, the next step is to find the minimum spanning tree of the graph.

Kruskal’s algorithm or Prim’s algorithm is suitable for this. Both these algorithms are greedy algorithms for finding MST.

Prim’s algorithm begins by selecting an arbitrary vertex and adding the least expensive edge from this vertex to the spanning tree. From then on, a vertex is added to the spanning tree each step by choosing the vertex connected by the least expensive edge.

Kruskal’s algorithm involves sorting all the edges from the lowest cost to the highest. Then, it chooses the smallest edge that does not form a cycle with the already included edges in the MST, ensuring that the number of edges is one less than the number of vertices.

Step 3: Calculate the total weight of the edges in the Minimum Spanning Tree

After getting the minimum spanning tree, find the sum of the weights of all the edges in the MST.

Step 4: Subtract the total weight of the edges in the MST from the total weight of all the edges in the original graph

This will provide the maximum saving which can be achieved by removing redundant edges while ensuring that the network remains connected.

Have in mind that it is not feasible to solve these steps by humans and it requires computer programming AND mathematical understanding.

Bear in mind that handling a complex problem like this manually is not practical and it would be best handled by a computer program or software capable of performing graph theory algorithms.

More Answers: