Explain briefly. i) Minimum Spanning Tree ii) Applications of Graph

i) Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. In other words, MST is a tree whose sum of edge weights is as small as possible.

Steps to find the Minimum Spanning Tree:

1. Sort all the edges in non-decreasing order of their weight.
2. Start adding edges to the MST from the smallest edge.
3. If adding the edge created a cycle, discard it.
4. Repeat steps 2 and 3 until there are (V-1) edges in the spanning tree where V is the number of vertices.

Two popular algorithms to find the MST are Kruskal’s Minimum Spanning Tree Algorithm and Prim’s Minimum Spanning Tree Algorithm.

Example:

Consider the following graph:

   2
A-----B
| \   |
4|  \1| 3
|   \ |
C-----D
   5

The MST of the above graph would be:

   2
A-----B
  \   
   \1 
    \
C-----D
   5

ii) Applications of Graph

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc.

Here are a few more examples of how graphs are used:

1. Google Maps: Graphs are used to represent places and the path (distance) between them.
2. Social Network: Each user is a vertex and when they become friends, an edge is drawn between them.
3. Web Pages: Each web page is a vertex. When one page links to another, there's an edge between them.
4. In Biology, to find the presence of a path in the sequence of genes.
5. In Computer Science, to represent networks of communication, data organization, computational devices, the flow of computation, etc.

Applications	Description
Google Maps	Graphs are used to represent places and the path (distance) between them.
Social Network	Each user is a vertex and when they become friends, an edge is drawn between them.
Web Pages	Each web page is a vertex. When one page links to another, there's an edge between them.
Biology	To find the presence of a path in the sequence of genes.
Computer Science	To represent networks of communication, data organization, computational devices, the flow of computation, etc.