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 allclose allScope (8)
Specification (5)
FindGraphIsomorphism works with undirected graphs:
Use rules to specify the graph:
It returns an empty list if no isomorphism can be found:
FindGraphIsomorphism works with large graphs:
Applications (1)
Properties & Relations (3)
Isomorphic graphs have the same number of vertices and edges:
Test whether two graphs are isomorphic using IsomorphicGraphQ:
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