Analysis of Graph Isomorphism with Examples and Implementation of VF2++ Algorithm

Abstract

Discrete mathematics, with graph theory as a key component, explores relationships among countable, distinct objects. Graphs, comprising vertices and edges, are essential for analyzing connectivity and processing discrete data across various fields like computer science, network theory, transportation, and social sciences. In practical applications such as electrical circuits, organic chemistry, and transportation networks, graph theory facilitates analysis and optimization. For instance, in electrical circuits, nodes and edges represent components and connections, while in organic chemistry, molecules are graphically depicted for structural analysis. Similarly, in transportation networks like airports, graph theory aids in optimizing flight schedules to minimize delays and congestion. In this research, basic terms and the notations are described, and important background observations and the definitions are followed. Detail of the isomorphism and bipartite is covered. Also, computational algorithm of VF2++ is introduced. Finally, the paper concludes with the future research works with MATLAB.