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:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)