FindGraphIsomorphism
FindGraphIsomorphism[g1,g2]
finds an isomorphism that maps the graph g1 to g2 by renaming vertices.
FindGraphIsomorphism[g1,g2,n]
finds at most n isomorphisms.
FindGraphIsomorphism[{vw,…},…]
uses rules vw to specify the graph g.
Details and Options
- FindGraphIsomorphism is also known as edge-preserving bijection.
- FindGraphIsomorphism is typically used for identification of equivalent structures and verification of equivalence of various representations.
- FindGraphIsomorphism gives a list of associations Association[v1->w1,v2->w2,…] such that vi and vj are adjacent vertices in g1 if wi and wj are adjacent vertices in g2, and vice versa.
- FindGraphIsomorphism gives an empty list if no isomorphism can be found.
- FindGraphIsomorphism[g1,g2,All] gives all the isomorphisms.
Examples
open all close allBasic Examples (2)
Scope (8)
Specification (5)
FindGraphIsomorphism works with undirected graphs:
FindGraphIsomorphism[[image], [image]]FindGraphIsomorphism[[image], [image]]Use rules to specify the graph:
FindGraphIsomorphism[{1 -> 2, 1 -> 3, 1 -> 4}, {"a" -> "b", "a" -> "c", "a" -> "d"}]It returns an empty list if no isomorphism can be found:
FindGraphIsomorphism[CycleGraph[3], CycleGraph[4]]FindGraphIsomorphism works with large graphs:
g = GridGraph[{10, 10, 10}];h = VertexReplace[g, Thread[VertexList[g] -> RandomSample[VertexList[g], VertexCount[g]]]];FindGraphIsomorphism[g, h]//Short//TimingEnumeration (3)
Applications (1)
Find an isomorphism that maps two graphs:
g = PetersenGraph[4, 1, VertexLabels -> "Name", ImagePadding -> 10, VertexSize -> Large];v1 = {"a", "b", "c", "d"};v2 = {"e", "f", "g", "h"};edge = Table[(v1[[i]]#)& /@ Delete[v2, 5 - i], {i, 4}]//Flatten;h = Graph[Join[v1, v2], edge, VertexLabels -> "Name", ImagePadding -> 10, VertexSize -> Large, AbsoluteOptions[CompleteGraph[{4, 4}], VertexCoordinates]];map = (Normal /@ FindGraphIsomorphism[g, h])[[1]]Highlight and label two graphs according to the mapping:
a = First /@ map;b = Last /@ map;highlightGraph[g_, v_] := HighlightGraph[g, Table[Style[Labeled[v[[i]], v[[i]]], ColorData["TemperatureMap"][i / VertexCount[g]]], {i, VertexCount[g]}]];{highlightGraph[g, a], highlightGraph[h, b]}Properties & Relations (3)
Isomorphic graphs have the same number of vertices and edges:
{g, h} = {PetersenGraph[4, 1], HypercubeGraph[3]}FindGraphIsomorphism[g, h]VertexCount[g] == VertexCount[h]EdgeCount[g] == EdgeCount[h]Test whether two graphs are isomorphic using IsomorphicGraphQ:
{g, h} = {CycleGraph[4], Graph[{23, 34, 41, 12}]}FindGraphIsomorphism[g, h]IsomorphicGraphQ[g, h]Isomorphic graphs have the same canonical graph:
g = [image];h = [image];FindGraphIsomorphism[g, h]CanonicalGraph[h] == CanonicalGraph[g]Text
Wolfram Research (2010), FindGraphIsomorphism, Wolfram Language function, https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html (updated 2015).
CMS
Wolfram Language. 2010. "FindGraphIsomorphism." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html.
APA
Wolfram Language. (2010). FindGraphIsomorphism. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html