Graph isomorphism problem PDF

Running head: GRAPH ISOMORPHISM PROBLEM
GRAPH ISOMORPHISM PROBLEM
Name of the Student
Name of the University
Course Code

GRAPH ISOMORPHISM PROBLEM1
Abstract:
The problem of graph isomorphism is simpler for defining and for understanding.
Many easily describable algorithms are there for solving these types of problems, however,
the time complexity associated with this type of problems is massively large. Hence,
minimizing the time complexity or increasing the efficiency of graph isomorphism problems
such that it can be practically implemented within a finite frame of time. Generally, these
problems do not solvable in polynomial time or falls in the category of NP complete and
hence often they are categorized in the type class NP-intermediate. The graph isomorphism
problem does not become NP complete until the hierarchy of polynomial time do not goes to
second level. This is one of the special case of subgraph-isomorphism which is about finding
whether a graph A which has a subgraph, is isomorphic to another graph B when it is known
that graph B is NP-complete. Different types of isomorphism problems are described in this
report and its different solution methods are described below.

GRAPH ISOMORPHISM PROBLEM2
Table of Contents
Introduction:.............................................................................................................................3
The graph Isomorphism problem:.........................................................................................3
Definition of graph:..............................................................................................................3
Defining graph isomorphism:..............................................................................................3
Relation between automorphism and isomorphism:.........................................................3
Algorithm overview for trivial graph isomorphism:............................................................3
Application by the graph vertices’ degrees:..........................................................................4
Application through canonical form of graphs:....................................................................4
Canonical form and its computation method:...................................................................4
Conclusion:...............................................................................................................................5
References:................................................................................................................................6

GRAPH ISOMORPHISM PROBLEM3
Introduction:
The problem of graph isomorphism can be seen in many applications like transport
planning, mathematics, computer science, engineering and many numerical fields. Many
structures or circuits can be represented by graphs and most of the time the requirement is to
know whether two or more structures gives the same representation from certain points of
views. Hence, two or more graphs are said to be isomorphic if the same number of vertices
are connected by same number of edges (Awang et al.). In other words two graphs are
isomorphic iff the other graph is a permutation of vertices and edges such that same number
of edges are present between two vertices.
As the isomorphism of graph arises in many situations, hence many methods to solve such
problems have been discussed. However, for the limitation of paper length a few methods are
discussed. For the practical implementation of comparatively huge sized graphs, usually the
canonical forms of graphs are used with appropriate algorithms. This bigger sized graphs
arises in particularly in the field of OOPNs (Object-oriented Petri nets). Towards the end of
this paper the isomorphism problem is described with the OOPNs.
The graph Isomorphism problem:
Definition of graph:
The concept of graph can be defined as a tuple G = (V, E), where V = set of all
vertices and E = set of all edges and E is a subset or equal set of (V2) ∪ (VC2) ∪ V.
Here, V^2 = V X V = {(u , v) | u ∈ V, v ∈ V} is the all possible permutations of oriented
edges for all the set of vertices V. The given set of (VC2) = {{u , v}|u ≠ v, u ∈ V, v ∈ V} is