Metraipolis › archive › dc_4cabc340da7c

Insieme indipendente (teoria dei grafi) — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Insieme_indipendente_(teoria_dei_grafi)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T14:29:45.748Z
SHA-256 of the archived text
b167c95676923ecc6f8099d1bbb4924aa784ee92b8c169bed1dc8da9596ae15a
Stable URL of this page
https://metraipolis.com/documento/dc_4cabc340da7c

How to cite

Insieme indipendente (teoria dei grafi) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Insieme_indipendente_(teoria_dei_grafi) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_4cabc340da7c (Metraipolis archive dc_4cabc340da7c, sha256 b167c95676923ecc6f8099d1bbb4924aa784ee92b8c169bed1dc8da9596ae15a)
BibTeX
@misc{dc4cabc340da7c,
  title = {Insieme indipendente (teoria dei grafi) — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Insieme_indipendente_(teoria_dei_grafi)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_4cabc340da7c; sha256 b167c95676923ecc6f8099d1bbb4924aa784ee92b8c169bed1dc8da9596ae15a},
  year = {2026}
}

Archived text

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

Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili. Un insieme indipendente massimale è un insieme indipendente tale che aggiungere un qualsiasi vertice all'insieme costringe l'insieme stesso a contenere uno spigolo. Un insieme indipendente massimo è un insieme indipendente della più grande dimensione possibile per un dato grafo G. Questa dimensione è chiamata numero d'indipendenza di G, e denotata α(G). Il problema di trovare un tale insieme è chiamato problema del massimo insieme indipendente ed è un problema di ottimizzazione NP-difficile. Come tale, è improbabile che esista un algoritmo efficiente per trovare un insieme indipendente massimo di un grafo. Ogni massimo insieme indipendente è anche massimale, ma l'implicazione inversa non è necessariamente valida.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Insieme indipendente (teoria dei grafi)» — https://it.wikipedia.org/wiki/Insieme_indipendente_(teoria_dei_grafi)
Wikidata Q1060343 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1060343
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Insieme_indipendente_(teoria_dei_grafi)?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 148551729, consultata il 2026-10-06T12:47:40.561Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fd92439e5eca7ecbca83f156c9dc17ea2fe98dfd8c4016aad29d3933240ff63e