Graph isomorphism

A bijection between the vertex sets of two graphs that preserves adjacency. Isomorphic graphs have the same structure, even when their vertices are named differently.

Graph theory: The mathematical study of graphs, structures made of vertices and edges. Graph isomorphism is a central notion for comparing structures studied in graph theory.
Subgraph isomorphism: The problem of determining whether one graph occurs as a subgraph of another. Unlike graph isomorphism, it matches a graph to only part of another graph.
Graph automorphism problem: The decision problem of determining whether a graph has a nonidentity automorphism. Its symmetry-detection task is closely connected to finding graph isomorphisms.
Chemical graph: A graph representing a molecule with atoms as vertices and bonds as edges. Molecular identity questions can become graph comparisons when atom and bond types are encoded.
Graph: A structure consisting of vertices and edges connecting pairs of vertices. An isomorphism compares two graphs by matching their vertices and edges.
Color refinement: An iterative procedure that partitions graph vertices by their neighborhoods' current classes. It quickly rejects many nonisomorphic pairs, but cannot distinguish every such pair.
Babai's graph isomorphism algorithm: László Babai's quasipolynomial-time algorithm for graph isomorphism, published in 2016. It established a major complexity bound for the graph-isomorphism problem.
Molecular isomorphism: Structural equivalence between molecular graphs under a vertex correspondence preserving atom and bond labels. It applies graph isomorphism to determine whether molecular representations encode the same structure.
Adjacency matrix: A matrix whose entries record whether pairs of graph vertices are adjacent. A vertex bijection preserves adjacency precisely when it reorders one graph's matrix into the other's.
Individualization-refinement: A graph-isomorphism search strategy that combines vertex refinement with branching choices. It narrows candidate vertex correspondences before exploring remaining possibilities.

Linked from 15 pages