Metraipolis › archive › dc_dd25d0cbe90f
Grafo perfetto — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Grafo_perfetto
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T14:48:39.020Z
- SHA-256 of the archived text
02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6- Stable URL of this page
https://metraipolis.com/documento/dc_dd25d0cbe90f
How to cite
Grafo perfetto — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_perfetto (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_dd25d0cbe90f (Metraipolis archive dc_dd25d0cbe90f, sha256 02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6)
BibTeX
@misc{dcdd25d0cbe90f,
title = {Grafo perfetto — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Grafo_perfetto},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_dd25d0cbe90f; sha256 02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_perfetto. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al teorema del grafo perfetto forte, sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un ciclo indotto di lunghezza dispari uguale a 5 o superiore. I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il teorema di Dilworth, possono essere espressi in termini della perfezione di certi grafi associati. La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del teorema di König, un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di Claude Berge, dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il teorema del grafo perfetto forte. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»). Fonte: Wikipedia in italiano, voce «Grafo perfetto» — https://it.wikipedia.org/wiki/Grafo_perfetto Wikidata Q1187620 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1187620 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Grafo_perfetto?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 152602126, consultata il 2026-10-07T14:21:41.010Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 55db6bc8b701a4ee1f63bfe1616fee835eb0bd01ba89a76bfff8bab9f446bdd8