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: Install NetworkX library. !pip install networkx Import required libraries. import networkx as ntwkx import matplotlib.pyplot as plt Instantiate Graph instance G1 = ntwkx.Graph() 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)]) 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: 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: 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: 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: 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 sourceGoogle colab notebook for graph operation in PythonNetworkX documentationRelated articles
This article talks about some basic concepts of graph theory and its applications using the Python programming language.
This article explains basic concepts of Graph Theory (to show pairwise relationships among entities) and its applications using Python.
["Python"]
["Go", "TPU", "AWS", "AI", "cloud_platforms:AWS", "Python", "Colab", "programming_languages:Python", "Matplotlib", "R"]
["AI", "Colab", "Matplotlib", "AWS", "TPU", "Python", "R", "Go", "cloud_platforms:AWS", "programming_languages:Python"]
A zealous learner aspiring to advance in the domain of AI/ML. Eager to grasp emerging techniques to get insights from data and hence explore realistic Data Science applications as well.