Understanding basics of graph is very essential. Many real world problems are effectively represented and solved using graph. Many graph problems can be solved using greedy approach. In this article, we will discuss basics of graph and various graph terminologies. We will talk about graph problems in upcoming articles.

Basics of Graph

Graph G = (V, E) is defined by a set of vertices (V) and set of edges (E) joining those vertices.

For the graph shown in following figure,

V    =   {A, B, C, D, E}

E    =   {AB, AD, AE, BD, BE, DC}

Basics of Graph
Graph G = <V, E>

Weighted Graph

Graph G = (V, E, W) is called weighted graph if some weight or cost is associated with each of its edges. W represents the set of weight associated with each edge.

A graph representing the distance between cities is a weighted graph, where cost / weight is the distance between two corresponding cities. For the weighted graph is illustrated in following figure,

V    =   {V1, V2, V3, V4}

EV1V2V1V3V1V4V2V3V2V4V3V4
W102012152225
Weighted graph
Weighted Graph

Tree

Tree T = (V’, E’) is a subset of Graph G = (V, E), where V’ is a subset of V and E’ is a subset of E. Tree does not contain a cycle, while Graph or subgraph can have a cycle.

Following figure shows the graph, its tree and subgraph. Multiple trees and subgraphs are possible for given graph

Tree of Graph G

Basics of Graph
Graph G
Tree
Tree
Sub graph
Sub Graph

Spanning Tree

Spanning tree T = (V’, E’) is a tree of connected, undirected, weighted graph G = (V, E, W), which contains all the vertices of G and some or all edges of G. So V’ = V and E’ ⊂ E.

Following illustrates the spanning tree of graph G.

Basics of Graph
Graph G
Spanning tree
Spanning Tree of G

Minimum Spanning Tree

Spanning tree T = (V’, E’) is a tree of connected, undirected, weighted graph G = (V, E, W), which contains all the vertices of G and some or all edges of G. So V’ = V and E’ ⊂ E. Graph G can have many spanning trees with a different cost. Minimum spanning tree is a spanning tree with minimum cost.

Graph and its minimum spanning tree are shown in following figure

Basics of Graph
Graph G
Minimum spanning tree
Minimum Spanning Tree

Applications of MST

  • MST is used in network design
  • It is used to implement efficient routing algorithm.
  • It is used to solve travelling salesman problem.

Additional Reading: Graph Functions – Click to read