Brute-force code for Isomorphisms
The purpose of this article is to use python code to explain concepts about isomorphism between graphs and related ideas such as automorphisms, cycle notation, vertex-transitive, and edge-transitive graphs.
It’s important to mention that the presented algorithms are highly inefficient, this is related to the graph isomorphism problem, not yet solved so far. Despite the inefficiency (n!), code can be used by the reader to experiment with graphs with n <= 8 vertices. At least for me, when I code something, then I understand it, hope it’s useful for someone who is new to these topics.
Graph Isomorphism
Two graphs are isomorphic if they are structurally equivalent, that is, whether they have the same pattern of connections. Designing an efficient algorithm to test this is a famous unsolved problem, as mentioned above.
Formally, two graphs G and H are isomorphic if there is a bijection from the vertex set of G to the vertex set of H such that adjacency and non-adjacency are preserved. The following pictures show examples of isomorphic graphs:
The following python code has the function “brute_force_test_graph_isomorphism”, which accepts as an arguments 2 adjacency matrix and returns True or False whether graphs are isomorphic or not. The detail of the code is explained below.
Let’s use the following example to go through the code above. We’ll check if the 2 following graphs are isomorphic.
With the following adjacency matrix:
The code checks first if the graph order of both graphs is equal (using get_graph_order function), if that’s not the case, graphs are not isomorphic. In the example, G1 and G2 have vertex order 5.
The next step is check the degree sequence is also equal (the degree-sequence of a graph is the sequence formed by arranging the vertex in non-incresasing order).
degree_sequence_G1 = degree_sequence_G2 = (2, 2, 2, 2, 2)
Finally, if these two checks are passed, then comes the hardest part. The code will use the function get_all_vertex_permutations to generate all the possible vertex permutations for the AG2 and compare if there is one of them that is equal to AG1. In our example, since there are 5 vertex, there are 5! (120) possible permutations to check. For the example, G1 and G2 are isomorphic, so brute_force_test_graph_isomporphism will return True.
The permutation of AG2 that transforms it to AG1 is the following:
It means that if we relabel in G2 vertex 1 as 1, 2 as 3, 3 as 3, 4 as 2, 5 as 4, we end up as the same G1 graph.
Cyclic notation for permutations
If σ is the set of permutations of {1, 2, … n}, can be represented as the following matrix:
Using cycle notation, the elements in each cycle are put inside parentheses, ordered so that σ(j) immediately follows j or, if j is the last element of the cycle, then σ(j) is the first element of the cycle. Usually numbers of each cycle are written in order. Let’s use an examples:
The following python code has the function cycle_notation, that transforms a permutation into cycle notation format:
Automorphisms
An automorphism from a graph G is an isomorphism to itself. Formally, an automorphism of G is a permutation such that the pair of vertices (u, v) form an edge if an only the pair (σ(u), σ(v)) also form an edge. The number of possible automorphisms of a graph is a way to measure its symmetry.
The following example, graph K₁₃ has 6 automorphims which are illustrated below.
The next code has the function “generate_automorphisms”, which receives an adjacency matrix and returns an array of the possible automorphisms for that graph. The explanation of the code is below.
An example of usage with the K₁₃ graph seen above could be the following:
Code has updated the function “get_all_vertex_permutations”, seen in the first part of the article, adding the corresponding edge permutation. In order to do that uses the functions edge_set and edge_permutation functions.
An automorphism of a graph is a permutation of the vertex labels so that the set of edges remains the same. Then, the code checks for all the possible vertex permutations, which of them has the same edge set as the original adjacency matrix.
Vertex and Edge-transitive graphs
A graph is vertex-transitive if for every vertex pair u, v, there is an automorphisms that maps u to v.
Similarly, a graph G is edge-transitive if for every edge pair d, e, there is an automorphism that maps d to e.
This code receives an adjacency matrix and returns true or false whether graph is vertex and/or edge transitive. For graphs with graph-order ≥ 7 program will need some time to return the result. Here I show some examples of graphs.
Hope this article was useful to understand these graph theory concepts and experiment with the code.
[1]: Gross, J., Yellen, J., Anderson, M. (2018). Graph Theory and Its Applications. CRC Press.
