//start adsense code //end adsense code

Graph Theory

by | Sep 14, 2017

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 di-graph. In other words, if each pair in the given set of pairs ( edges ) is an ordered pair, the graph will be a directed graph.

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:Graph

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 2 3 4 5 6 7
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