# Graph Theory

A graph is simply a finite set of points(also called nodes or vertices) along with a set of pairs of points that are present in the given finite set. These pairs of points represent edges or connections between the points. The edges can possess attributes such as color, weight or distance depending on the problem.

**TERMINOLOGY**

**Degree of a vertex V**

The number of edges connected to the vertex V is called the degree of V.

**Parallel Edges **

The number of edges connected to the vertex V is called the degree of V.

**Self-Loop **

An edge starting and ending at the same vertex is called Self-Loop.

**Simple Graph**

A graph that has no parallel edges of self-loops is called a simple graph.

**Path**

A sequence of vertices such that each successive vertex is connected to the preceding vertex is called a path.

**Cycle**

A path that starts and ends at the same vertex.

**Connected Graph**

A graph that has all pairs of vertices connected by at least 1 path. In other words, for any pair of vertices (A, B), a path exists that connected A and B.

If there exists a set of vertices that are not connected to the other vertices, then this set is called a component of the graph. For example, in the image given below, each of the sub-graphs formed by nodes {2,4,5,6} and {1,3,7} are called components.

**Forest**

A graph without cycles is called a forest.

**Tree**

A connected forest is called a Tree.

**Spanning Sub-Graph**

A graph that contains all the vertices of the graph.

**Spanning Tree**

A spanning subgraph that is a tree.sub-graph that is a tree.

**Directed Graphs or di-graph**

When all the edges are directed, it is called a

**Undirected Graph**

Intuitive as it is, if traveling from node A to node B which means the same thing as traveling from node B to node A, it is an undirected graph.

**Mixed Graph**

If a graph contains both directed and undirected edges, it is called a Mixed Graph.

**REPRESENTATION**

Consider the image below:

We will discuss two ways to represent a graph in programming.

**Adjacency List**

In Adjacency List representation of a graph, we create an array of lists. The size of the array is the number of nodes in the graph and each list contains the nodes connected to the node it represents.

This can be represented as:

Node –> Connected Nodes

—————————————–

1 –> 3, 7

2 –> 4, 5, 6

3 –> 1

4 –> 2, 5

5 –> 2, 4

6 –> 2

7 –> 1

How do we implement in programming? Resizeable data types, like ArrayLists and Maps in Java, since we do not know the number of nodes each node is attached to, beforehand. Here is a Java implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | import java.util.*; class AdjacencyList { static LinkedList<Integer> adjList[]; static int N; public static void main(String args[]) { N = 7; adjList = new LinkedList[N+1]; for(int i=1;i<=N;i++) adjList[i] = new LinkedList<>(); addEdge(1, 3); addEdge(7, 1); addEdge(2, 6); addEdge(2, 5); addEdge(2, 4); addEdge(4, 5); /* Nodes --> Connected Nodes ------------------------- 1 --> 7 3 2 --> 4 5 6 3 --> 1 4 --> 5 2 5 --> 4 2 6 --> 2 7 --> 1 */ for(int i=1;i<=N;i++) { Iterator<Integer> it=adjList[i].listIterator(); System.out.print(i+" --> "); while(it.hasNext()) System.out.print((int)it.next()+" "); System.out.println(); } } static void addEdge(int i, int j) { //In case of undirected graph, //i-->j and j-->i, both are possible //Hence, both the nodes are updated adjList[i].addFirst(j); adjList[j].addFirst(i); } } |

**Adjacency Matrix**

Adjacency Matrix is NxN matrix where N is the number of Nodes in the graph. Here,

A[i][j] = 1; if there is an edge between nodes i and j,

A[i][j] = 0, if there is no edge between nodes i and j.

Such a matrix is used only when the number of vertices is small. The graph given above can be represented as:

1 0 0 1 0 0 0 1

2 0 0 0 1 1 1 0

3 1 0 0 0 0 0 0

4 0 1 0 0 0 0 0

5 0 1 0 0 0 0 0

6 0 1 0 0 0 0 0

7 1 0 0 0 0 0 0

Note: In case of undirected graphs, A[i][j] = A[j][i], always.

# More from this Category

## Getting Started with Software Development

Insight on building a software.

## Codechef: KMXOR Solution

Codechef May Cook-off 2018: KMXOR editorial with Java implementation.

## Algorithm: Binary Search

Variations of the conventional binary search algorithm are discussed.

## Graph Traversal

This article explains breadth first traversal and depth first traversal in graph theory.

## Primality Sieves

Segmented Sieve, Sieve of Sundaram, Sieve of Atkin are discussed here.

## Recursion: Optimization

A more optimized approach to the use of recursion