Graph Theory

Basic Terminologies Of Graphs

BASIC TERMINOLOGIES

Loop : An edge of a graph that joins a node to itself is called loop or self loop. i.e., a loop is an edge (vi, vj) where vi = vf.

Multigraph: In a multigraph no loops are allowed but more than one edge can join two vertices, these edges are called multiple edges or parallel edges and a graph is called multigraph.

Two edges (vi, vj) and (vf , vr) are parallel edges if vi = vr and vj, vf.

Pseudo graph: A graph in which loops and multiple edges are allowed, is called a pseudo graph.

Simple graph: A graph which has neither loops nor multiple edges. i.e., where each edge connects two distinct vertices and no two edges connect the same pair of vertices is called a simple graph.

Figure 1.1(a) and (b) represents simple undirected and directed graph because the graphs do not contain loops and the edges are all distinct.

Finite and Infinite graphs: A graph with finite number of vertices as well as a finite number of edges is called a finite graph. Otherwise, it is an infinite graph.