Network Algorithms: Least Weight Set of Arcs Connecting All Vertices

Introduction

In discrete mathematics, network algorithms are powerful tools applied to solve problems involving networks or graphs.
A network or a graph is a structure that represents objects and the relations between them.
The least weight set of arcs connecting all vertices is a common problem in network algorithms, often dealt with through methods like Kruskal’s and Prim’s algorithms.

Kruskal’s Algorithm is a greedy approach used to determine the minimum spanning tree for a connected and undirected graph.
This network algorithm treats every vertex as an independent tree and connects one vertex at a time, over the least expensive edge.
It keeps adding the lowest weight edge which doesn’t form a cycle in the resulting graph.
The edges are sorted in ascending order based on their weights, and only those edges are chosen which connect two distinct trees in the graph’s forest.

Prim’s Algorithm is another method to find the minimum spanning tree of a graph.
It starts from an arbitrary node and grows the minimum spanning tree one edge at a time.
It always joins the nearest vertex to the current tree in the graph.
The algorithm keeps track of the vertices included in the minimum spanning tree and choose the minimum weight edge among the edges that connect the vertices of the tree to the vertices not yet included.

Network algorithms are extensively used in fields like computer science, transportation, telecommunications and logistics.
Among these, the problem of least weight set of arcs connecting all vertices is central to tasks like network design, circuit design, transportation planning and the like.

Let’s say you want to find the most efficient way to connect all houses in a neighbourhood to a network of water pipelines with the least total length (weight) of pipes. Draw a network where vertices represent houses and weights on the arcs represent the length of pipe needed to connect two houses. Using either Kruskal’s or Prim’s algorithm, we can obtain the minimum spanning tree i.e., the least weight set of arcs connecting all vertices.
In another scenario, say you are planning a road network that connects all cities in a country with the least amount of road length. You could represent this problem as a graph where vertices represent cities and arc weights represent the distance between cities. Apply either Kruskal’s or Prim’s algorithm to obtain the plan with the least total road length.