Топ-100
Indietro

ⓘ Insieme indipendente massimale. Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sot ..




Insieme indipendente massimale
                                     

ⓘ Insieme indipendente massimale

Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un insieme dominante nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipendenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamente variabili; un insieme indipendente massimale più grande è chiamato insieme indipendente massimo.

Per esempio, nel grafo P 3, un cammino con tre vertici a, b e c e due spigoli ab e bc, gli insiemi { b } e { a, c } sono entrambi massimamente indipendenti. Linsieme { a } è indipendente, ma non è massimamente indipendente, perché è un sottoinsieme dellinsieme indipendente più grande { a, c }. In questo stesso grafo, le cricche massimali sono gli insiemi { a, b } e { b, c }.

La locuzione "insieme indipendente massimale" si usa anche per descrivere sottoinsiemi massimali di elementi indipendenti in strutture matematiche diverse dai grafi, e in particolare negli spazi vettoriali e nei matroidi.

                                     

1. Insiemi di vertici correlati

Se S è un insieme indipendente massimale in qualche grafo, è una cricca massimale o un sottografo completo massimale nel grafo complementare. Una cricca massimale è un insieme di vertici che induce un sottografo completo, e che non è un sottoinsieme dei vertici di nessun sottografo completo più grande. Cioè, è un insieme S tale che ogni coppia di vertici in S è connessa da uno spigolo e ad ogni vertice non in S manca uno spigolo per almeno un vertice in S. Un grafo può avere molte cricche massimali, di dimensioni variabili; trovare la più grande di queste è il problema della cricca massima.

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

Il complemento di un insieme indipendente massimale, cioè, linsieme di vertici non appartenenti allinsieme 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 è 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 gas di reticolo a sfere rigide, unastrazione matematica delle transizioni di stato fluido-solido.

Ogni insieme indipendente massimale è un insieme dominante, un insieme di vertici tale che ogni vertice nel grafo o appartiene allinsieme o è adiacente allinsieme stesso. Un insieme di vertici è un insieme indipendente massimale se e solo se è un insieme dominante indipendente.

                                     

2. Caratterizzazioni delle famiglie di grafi

Certe famiglie di grafi sono state caratterizzate anche in termini delle loro cricche massimali e dei loro insiemi indipendenti massimali. Gli esempi includono i grafi irriducibili alle cricche massimali e i grafi ereditari irriducibili alle cricche massimali. Si dice che un grafo è irriducibile alle cricche massimali se ogni cricca massimale ha uno spigolo che non appartiene a nessunaltra cricca massimale, ed ereditario irriducibile alle cricche massimali se la stessa proprietà è vera per ogni sottografo indotto. I grafi ereditari irriducibili alle cricche massimali includono i grafi senza triangoli, i grafi bipartiti e i grafi dintervallo.

I cografi possono essere caratterizzati come grafi nei quali ogni cricca massimale interseca ogni insieme indipendente massimale, e nei quali la stessa proprietà è vera in tutti i sottografi indotti.

                                     

3. Limitare i numeri degli insiemi

Moon & Moser 1965 mostrarono che qualsiasi grafo con n vertici ha al più 3 n /3 crocche massimali. Complementarmente, anche qualsiasi grafo con n vertici ha al più 3 n /3 insiemi indipendenti massimali. Un grafo con esattamente 3 n /3 insiemi indipendenti massimali è facile da costruire: si prende semplicemente lunione disgiunta di n /3 grafi con triangoli. Qualsiasi insieme indipendente massimale in questo grafo è formato scegliendo un vertice da ciascun grafo. Il grafo complementare, con esattamente 3 n /3 cricche massimali, è un tipo speciale di grafo di Turán; a causa della loro connessione con il limite di Moon e Moser, questi grafi talvolta sono chiamati anche grafi di Moon-Moser. Limiti più rigidi sono possibili se si limita la dimensione degli insiemi indipendenti massimali: il numero di insiemi indipendenti massimali di dimensione k in qualsiasi grafo con n vertici è al più

⌊ n / k ⌋ k − n mod k ⌊ n / k + 1 ⌋ n mod k. {\displaystyle \lfloor n/k\rfloor ^{k-n{\bmod {k}}}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}

I grafi che raggiungono questo limite sono ancora grafi di Turán.

Certe famiglie di grafi possono, tuttavia, avere limiti molto più restrittivi sui numeri degli insiemi massimali indipendenti e delle cricche massimali. Se tutti i grafi con n vertici in una famiglia di grafi hanno On spigoli, se ogni sottografo di un grafo della famiglia appartiene anchesso alla famiglia, allora ciascun grafo nella famiglia può avere al più On cricche massimali, le quali hanno tutte dimensione O1. Ad esempio, queste condizioni sono vere per i grafi planari: ogni grafo planare con n vertici ha al più 3 n − 6 spigoli, e il sottografo di un grafo planare è sempre planare, dal cui segue che ciascun grafo planare ha On cricche massimale al massimo quattro. Anche i grafi dintervallo e i grafi cordali hanno al massimo n cricche massimali, anche se non sempre sono grafi sparsi.

Il numero di insiemi indipendenti massimali nei grafi ciclo con n vertici è dato da numeri di Perrin, e il numero di insiemi indipendenti massimali nei grafi cammino è dato dalla successione di Padovan. Perciò, entrambi i numeri sono proporzionali alle potenze di 1.324718, il numero plastico.



                                     

4. Algoritmi per lelencazione di insiemi

Un algoritmo per elencare tutti gli insiemi indipendenti massimali o tutte le cricche massimali in un grafo può essere usato come subroutine per risolvere molti problemi di grafi NP-completi. È assai ovvio che le soluzioni per il problema del massimo insieme indipendente, il problema della cricca massima e il problema del minimo dominante indipendente devono essere tutte insiemi indipendenti massimali o cricche massimali, e possono essere trovate da un algoritmo che elenca tutti gli insiemi indipendenti massimali o le cricche massimali e conserva quelli con la dimensione più grande o più piccola. Similmente, la copertura minima dei vertici può essere trovata come il complemento di uno degli insiemi indipendenti massimali. Lawler 1976 osservò che elencare gli insiemi indipendenti massimali può essere usato anche per trovare le 3-colorazioni dei grafi: un grafo può essere 3-colorato se e solo se il complemento di uno dei suoi insiemi indipendenti massimali è bipartito. Usò questo approccio non solo per la 3-colorazione ma come parte di un più generale algoritmo di colorazione dei grafi, e da allora approcci simili alla colorazione dei grafi sono stati perfezionati da altri autori. Anche altri problemi più complessi possono essere modellati per trovare una cricca o un insieme indipendente di tipo specifico. Questo giustifica il problema algoritmico di elencare tutti gli insiemi indipendenti massimali o equivalentemente, tutte le cricche massimali in modo efficiente.

È immediato trasformare una dimostrazione del limite 3 n /3 di Moon e Moser sul limite di insiemi indipendenti massimali in un algoritmo che elenca tutti gli insiemi di questo tipo nel tempo O3 n /3. Per i grafi che hanno il massimo numero possibile di insiemi indipendenti massimali, questo algoritmo impiega un tempo costante per ogni insieme delle uscite. Tuttavia, un algoritmo con questo limite temporale può essere altamente inefficiente per i grafi con numeri più limitati di insiemi indipendenti. Per questa ragione, molti ricercatori hanno studiato algoritmi che elencano tutti gli insiemi indipendenti massimali in tempo polinomiale per ogni insieme delle uscite. Il tempo per ogni insieme indipendente massimale è proporzionale a quello per la moltiplicazione di matrici nei grafi densi, o più veloce in varie classi di grafi sparsi.

                                     
  • stabili. Un insieme indipendente massimale è un insieme indipendente tale che aggiungere un qualsiasi vertice all insieme costringe l insieme stesso a contenere
  • cricca massimale interseca qualsiasi insieme indipendente massimale in un unico vertice. Un grafo d intervallo è un grafo le cui cricche massimali possono
  • accoppiamento massimo. Si noti che ogni accoppiamento massimo è massimale ma non ogni accoppiamento massimale è un accoppiamento massimo. La figura seguente mostra
  • mentre il problema dell insieme indipendente rimane NP - difficile sui grafi planari. Una cricca massimale talvolta chiamata massimale con inclusione, è
  • 5, 5, 7, 10, 12, 17, 22, 29, 39 . Il numero dei diversi insiemi indipendenti massimali in un grafo ciclo con n vertici è conteggiato dal numero Perrin
  • insieme indipendente di cardinalità massima, i due problemi non sono equivalenti in quanto ad approssimabilità. Il problema dell insieme indipendente
  • chiamato un insieme possibile. Quando prendiamo in analisi un matroide, un insieme possibile è anche noto come insieme indipendente Un sistema insieme accessibile
  • sono molto limitate nel muscolo in maniera tale da sostenere lo sforzo massimale per soli 6 secondi circa. Esistono quattro differenti sistemi energetici
  • detto P - primario. Tra gli ideali primari vi sono le potenze degli ideali massimali tuttavia non è detto né che tutte le potenze di ideali primi siano primarie
  • finiti sono perfetti. Campo algebricamente chiuso Estensione algebrica massimale di un campo F è la sua chiusura algebrica. Un campo è algebricamente chiuso
  • degli insiemi di Zermelo - Fraenkel, che è quella comunemente usata, questa ipotesi non può essere né dimostrata né confutata, cioè è indipendente dai suoi