MINIMUM SPANNING TREE:

A largest spanning tree (MST) is the maximum spanning tree (MST). all of the edges of a linked, edge-weighted undirected graph of the vertices with the smallest average edge weight available without any kind of cycles It’s a spanning tree with the absolute minimum sum of edge weights, in other words. In any edge-weighted undirected graph, a shortest path forest is the fusion of the minimum spanning trees for its connected sequence (not necessarily linked).

Each spanning tree has n 1 edges if there are n vertices in the graph. There may be numerous minimum spanning trees of the same weight; for example, if all of a graph’s edge weights are the same, then every spanning tree of that graph is minimum.

UNIQUENESS OF MINIMUM SPANNING TREE:

There will be only one minimal spanning tree, and it will be distinctive. if each edge has a different weight.

Proof:

1. Assume, on the other hand, that MSTs A and B are distinct.

2. Due to the fact that A and B differ while having the same nodes, at least one edge belongs to one but not the other. Let e1 be the edge with the least weight among these; this decision is unique because the edge weights are all different. Assume e1 is in A without losing generality.

3. Because B is an MST, cycle C with e1 must be present in e1

4. Because A does not have any cycles as a tree, C must have an edge e2 that is not present in A.

5. Because e1 was picked as the lowest-weight edge among those belonging to exactly one of A or B, e2’s weight must be bigger than e1's.

6. Because e1 and e2 are both part of cycle C, substituting e2 with e1 in B results in a lighter spanning tree.

7. This is completely contrary to the notion that B is an MST.

If the edge weights are not all unique, only the (multi-)set of weights in minimal spanning trees is guaranteed to be unique; this is true for all minimum spanning trees.

PROPERTIES OF SPANNING TREE:

1. When any edge in the spanning tree is removed, it becomes disconnected. As a result, no edges can be removed from the spanning tree.

2. A loop is created when an edge is added to the spanning tree. As a result, we are unable to add any new edges to the spanning tree.

3. If each edge in a graph has a different weight, then there can only be one minimum spanning tree. This contradicts the statement “There can be more than one minimum spanning tree.” if the edge weight is not distinct.

4. There can be a n^n-2 number of spanning trees in a complete undirected graph.

5. At least one spanning tree exists in every linked and undirected graph.

6. There is no spanning tree in the unconnected graph.

7. To create a spanning tree, we can eliminate the maximum (e-n+1) edges from a complete graph.

REAL LIFE APPLICATIONS:

For network designs, minimum spanning trees are used (i.e., telephone or cable networks). They’re also utilised to come up with approximate solutions to difficult mathematical issues like the Traveling Salesman Problem. Among the many more applications are:

1. Cluster Analysis is a technique for analyzing groups of people.

2. Face recognition and verification in real time (i.e., locating human faces in a video stream).

3. In computer science, protocols are used to avoid network cycles.

4. Image registration based on entropy.

5. Paths with the most bottlenecks

6. Idleness (adding white noise to a digital recording in order to reduce distortion).

KRUSKAL’S ALGORITHM:

Kruskal’s approach finds the undirected edge-weighted graph’s least spanning forest. It finds a minimum spanning tree if the graph is linked. In a connected graph, a minimal spanning tree is a subset of the edges that forms a tree that includes every vertex and minimizes the sum of the weights of all the edges in the tree. A minimal spanning forest for a disconnected graph is made up of a minimum spanning tree for each connected component. In graph theory, it is a greedy method since it adds the next lowestweight to the boundary that doesn’t form a cycle minimal spanning forest at each step.

PSEUDOCODE:

TIME COMPLEXITY:

Kruskal’s approach can be proven to execute in O (E log V) time, or equivalently, O (E log V) time, for a graph with E edges and V vertices, all with basic data structures. Because of the following, these running timings are equivalent:

1. E is at most V² and log V² = 2 log V belongs to O (log V)

2. Each isolated vertex is a separate component of the minimum spanning forest. If we ignore isolated vertices, we obtain V <=2E, so log V is O (log E)