Insieme indipendente massimale: differenze tra le versioni

Versione delle 21:27, 6 apr 2014

Versione delle 21:28, 6 apr 2014

Riga 18:

Alcuni autori includono la massimalità come parte della definizione di una cricca, e si riferiscono alle cricche massimali semplicemente come cricche.

Il [[Complemento (teoria degli insiemi)|complemento]] di un insieme indipendente massimale, cioè, l'insieme di vertici non appartenenti all'insieme indipendente, forma una '''copertura dei vertici minimale'''. Cioè, il complemento è una [[copertura dei vertici]], un insieme di vertici che include almeno un estremo di ciascuno spigolo, ed è is minimale nel senso che nessuno dei suoi vertici può essere rimosso mentre si preserva la proprietà che è una copertura. Le coperture di vertici minimali sono state studiate in [[meccanica statistica]] in connessione con il modello del [[Sfere rigide|gas di reticolo a sfere rigide]], un'astrazione matematica delle transizioni di stato fluido-solido.<ref>{{cita|Weigt2001||Weigt & Hartmann (2001)|harv=s}}.</ref>

Ogni insieme indipendente massimale è un [[insieme dominante]], un insieme di vertici tale che uogni vertice nel grafo o appartiene all'insieme o è adiacente all'insieme stesso. Un insieme di vertici è un insieme indipendente massimale se e solo se è un insieme dominante indipendente.