Understand Basic Concepts of Graph Theory With Python Implementation

Graph, in simple terms, is a mathematical structure that depicts pairwise relationships among various entities. In computer science, graphs are non-linear data structures. This article talks about some basic concepts of graph theory and its applications using the Python programming language.

Graph Theory - An Overview

The graph is a way of diagrammatically representing a collection of interconnected nodes - each of which stands for an entity. A graph G is mathematically represented as an ordered pair (V, E), where V is the set of vertices and E is the set of edges. A network formed by vertices (or nodes) and the edges joining related vertices forms a graph. In practical applications, a graph can represent several complicated networks, such as a  

Image source

• A simple graph is one having no two edges connecting a common pair of vertices.
• A multigraph can have multiple edges connecting a given pair of vertices. If there are say ‘n’ edges connecting a pair of vertices x and y, then {x,y} is an edge with a multiplicity of ‘n’.
• An edge connecting a vertex to itself is said to form a loop.
• A pseudograph is a multigraph having loops as well. 

Play with graphs!

This section describes some basic operations that we can perform on graphs and change their structures.

Subgraph

A subgraph of a graph (V, E) is a graph (X, Y) such that X is a subset of V and Y is a subset of E. A subgraph S of a graph G is said to be a ‘proper subgraph’ of G if S is not equal to G. 

Image source

Union of graphs

Union of graphs G1=(V1, E1) and G2=(V2, E2) results in a single graph with vertex set V=V1 U V2 and edge set E = e1 U E2. Here union operation ‘U’ plays the same role as that in set operations, i.e. it combines unique elements (vertices/edges) from each of the graphs.

Image source

Complement of a graph

Consider two graphs G1 = (V1,E1) and G2 = (V2,E2). If the edge(s) present in one of them is/are not present in the other and G1 and G2, when combined, form a complete graph, then G1 and G2 are said to be the complement of each other.

Note: A complete graph G(n) is a graph with ‘n’ vertices such that there exists exactly one edge joining each pair of the vertices.

Image source

Graphs I and II in the above figure are complement of each other.

Practical implemention

Here’s a demonstration of performing the above-explained basic graph theory operations using Python. We have used NetworkX library, which has been developed for easy creation, manipulation and analysis of complex networks and graph structures. The code below has been implemented using Python 3.7.10 and networkx 2.5.1 versions. Step-wise implementation of the code is as follows:

1. Install NetworkX library.

!pip install networkx

2. Import required libraries.

 import networkx as ntwkx
 import matplotlib.pyplot as plt 

3. Instantiate Graph instance

G1 = ntwkx.Graph()

4. Add edges to the graph using add_edges_from() method. The edges are specified as 2-tuple (x,y), which means an edge is to be drawn joining vertices x and while or a 3-tuple (x,y,d) where d is a dictionary containing the edge’s data.

G1.add_edges_from([(1, 3), (2, 3), (3, 4), (1, 5), (2, 4), (4, 5), (5, 6), (6, 7), (5, 8),(7, 8)])

5. Plot the created graph.

 #Title of the plot
 plt.suptitle("Original graph")
 #draw_networkx() method draws the graph G1 using matplotlib 
 ntwkx.draw_networkx(G1) 

Output:

6. Create a subgraph from the above graph G1.

SG1 = G1.subgraph([1, 3, 4, 5])

Plot the subgraph

 #Title of the plot
 plt.suptitle("Subgraph of G1")
 #Draw the subgraph using matplotlib
 ntwkx.draw_networkx(SG1) 

Output:

7. Union of two graphs

Create 1st graph named G2

 #Instantite a Graph object
 G2 = ntwkx.Graph()
 #Add edges to the grap
 G2.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 4), 
                          (4, 5), (4, 6), (5, 7), (5, 8), (7, 8)])
 # Draw graph G2 using matplotlib
 ntwkx.draw_networkx(G2) 

Output:

Create 2nd graph named G3

 G3 = ntwkx.Graph()
 G3.add_edges_from([(13, 14), (13, 15), (13, 9),
                   (14, 15), (15, 10), (9, 10)])
 # Second Graph created
 plt.suptitle("Graph G3")
 ntwkx.draw_networkx(G3) 

Output:

Create union of G2 and G3

 #G2 and G3 must be disjoint graphs else union() method raises error
 U = ntwkx.union(G2, G3)
 #Title of the plot
 plt.suptitle("Union of G2 and G3")
 #Draw the union graph using matplotlib
 ntwkx.draw_networkx(U) 

Output:

8. Composition of graphs

compose() method simply performs the same task as union() if the graphs have no node in common. If the graphs have common nodes, they create a connected graph withboth the constituent graphs as subgraphs.

For graphs having no common node:

 C1 = ntwkx.compose(G2,G3)
 #Title of the plot
 plt.suptitle("Composition of disjoint graphs")
#Draw the composed graph
 ntwkx.draw_networkx(C1) 

Output:

For graphs having common nodes:

 #Create 1st graph
 G4 = ntwkx.Graph()
 G4.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4)])
 plt.suptitle("Graph G4")
 ntwkx.draw_networkx(G4) 

Output:

 #Create 2nd graph
 G5 = ntwkx.Graph()
 G5.add_edges_from([(3, 7), (7, 4), (3, 4)])
 # Second Graph created
 plt.suptitle("Graph G5")
 ntwkx.draw_networkx(G5) 

Output:

Composition of graphs G4 and G5:

 C2 = ntwkx.compose(G4, G5)
 plt.suptitle("Composition with common node")
 ntwkx.draw_networkx(C2) 

Output:

9. Complement of a graph

 #Display graph G4
 plt.suptitle(“Graph G4”)
 ntwkx.draw_netwrkx(G4) 

Output:

#Complement of graph G4

 comp = ntwkx.complement(G4)
 plt.suptitle("Complement of graph G4")
 ntwkx.draw_networkx(comp) 

Output:

• Code source
• Google colab notebook for graph operation in Python
• NetworkX documentation
• Related articles