Metraipolis › archive › dc_52dbf2abbe13
Graph canonization — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Graph_canonization
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T16:32:04.001Z
- SHA-256 of the archived text
a062947c1e833476293f9be97aa93ccc9be306a326cad0db6c46317e7d3ceb36- Stable URL of this page
https://metraipolis.com/documento/dc_52dbf2abbe13
How to cite
Graph canonization — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_canonization (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_52dbf2abbe13 (Metraipolis archive dc_52dbf2abbe13, sha256 a062947c1e833476293f9be97aa93ccc9be306a326cad0db6c46317e7d3ceb36)
BibTeX
@misc{dc52dbf2abbe13,
title = {Graph canonization — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Graph_canonization},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_52dbf2abbe13; sha256 a062947c1e833476293f9be97aa93ccc9be306a326cad0db6c46317e7d3ceb36},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_canonization. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical. The canonical form of a graph is an example of a complete graph invariant: every two isomorphic graphs have the same canonical form, and every two non-isomorphic graphs have different canonical forms. Conversely, every complete invariant of graphs may be used to construct a canonical form. The vertex set of an n-vertex graph may be identified with the integers from 1 to n, and using such an identification a canonical form of a graph may also be described as a permutation of its vertices. Canonical forms of a graph are also called canonical labelings, and graph canonization is also sometimes known as graph canonicalization. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»). Fonte: Wikipedia in inglese, voce «Graph canonization» — https://en.wikipedia.org/wiki/Graph_canonization Wikidata Q5597079 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5597079 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_canonization?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1330143987, consultata il 2026-10-06T15:17:42.487Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 296637b984512f114f5995d8c8b21fc770fbd8ce881434cd10ef860a5079789d