Metraipolis › archive › dc_f8dafa877df6

Graph isomorphism — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Graph_isomorphism
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T16:31:58.566Z
SHA-256 of the archived text
c26b41b08f4d092bb9e9066b5898c1f788be4704bc033ddce04ff1e1d8252070
Stable URL of this page
https://metraipolis.com/documento/dc_f8dafa877df6

How to cite

Graph isomorphism — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_isomorphism (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f8dafa877df6 (Metraipolis archive dc_f8dafa877df6, sha256 c26b41b08f4d092bb9e9066b5898c1f788be4704bc033ddce04ff1e1d8252070)
BibTeX
@misc{dcf8dafa877df6,
  title = {Graph isomorphism — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Graph_isomorphism},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f8dafa877df6; sha256 c26b41b08f4d092bb9e9066b5898c1f788be4704bc033ddce04ff1e1d8252070},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_isomorphism. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f : V ( G ) → V ( H ) {\displaystyle f\colon V(G)\to V(H)} such that any two vertices u and v of G are adjacent in G if and only if f ( u ) {\displaystyle f(u)} and f ( v ) {\displaystyle f(v)} are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic, often denoted by G ≃ H {\displaystyle G\simeq H} . In the case when the isomorphism is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the isomorphism is called an automorphism of G. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The question of whether graph isomorphism can be determined in polynomial time is a major unsolved problem in computer science, known as the graph isomorphism problem. The two graphs shown below are isomorphic, despite their different looking drawings.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»).
Fonte: Wikipedia in inglese, voce «Graph isomorphism» — https://en.wikipedia.org/wiki/Graph_isomorphism
Wikidata Q303100 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q303100
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_isomorphism?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 1374954227, consultata il 2026-10-06T15:17:42.479Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0f1aca2330d8e63b6c728ba7c097d344d8aa6fb70f62330e7f2effb1f2e38d9e