In graph theory, a branch of mathematics, graph canonization is finding a canonical form of a graph G, which is a graph Canon(G) isomorphic to G such that Canon(H) = Canon(G) if and only if H is isomorphic to G. The canonical form of a graph is an example of a complete graph invariant. Since the vertex sets of (finite) graphs are commonly identified with the intervals of integers 1,..., n, where n is the number of the vertices of a graph, a canonical form of a graph is commonly called canonical labeling of a graph. Graph canonization is also sometimes known as graph canonicalization.
A commonly known canonical form is the lexicographically smallest graph within the isomorphism class, which is the graph of the class with lexicographically smallest adjacency matrix considered as a linear string.
Read more about Graph Canonization: Computational Complexity, Applications
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)