Basics of Graph – Terminologies You Must Know

by codecrucks · Published 27/10/2021 · Updated 08/06/2022

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}

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}

E	V₁V₂	V₁V₃	V₁V₄	V₂V₃	V₂V₄	V₃V₄
W	10	20	12	15	22	25

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

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.

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

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