Chapter: Isomorphism (Graphs)

The isomorphism of graphs is a very important concept for trying to solve graph-theoretical problems by means of a computer, because any graph or digraph can be represented in a way, which can be handled with a computer.

Graph isomorphism ensures that two graphs, e.g. having different diagrams or labeling of vertices and edges can be, in a sense, regarded as the same, because they convey the same information. Consider an office resource graph with three persons: Alice Norisson \(A,N\) , Christine Smith \(C,S\) and Bob Parker \(B,P\) , connected to three resources in their office network - a printer \(p\) or \(r_1\), an internet hot spot \(h\) or \(r_2\), and a database \(d\) or \(r_3\). Due to some network problems, Bob Parker lost his connection to the hot spot.

All of the below diagrams convey the same information about the network connection in the office, although they are quite different and have different labellings (e.g. using the first or last names of each person, varying of the diagram pictograms, or moving them around, without changing the connections in-between):

graphs10

  1. Definition: Isomorphic Undirected Graphs
  2. Definition: Isomorphic Digraphs

Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs