Топ-100
Indietro

ⓘ Colorazione golosa. Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa è una colorazione dei vertici d ..




Colorazione golosa
                                     

ⓘ Colorazione golosa

Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa è una colorazione dei vertici di un grafo formata da un algoritmo goloso che considera i vertici del grafo in sequenza e assegna a ciascun vertice il suo primo colore disponibile. Le colorazioni golose in generale non usano il numero minimo di colori possibili; tuttavia, sono state usate in matematica come tecnica per dimostrare altri risultati sulle colorazioni e in informatica come euristica per trovare le colorazioni con pochi colori.

                                     

1. La golosità non è sempre buona

Un grafo a corona un grafo bipartito completo K n, n, con gli spigoli di un accoppiamento perfetto eliminato è un caso particolarmente sbagliato di colorazione golosa: se lordinamento dei vertici pone due vertici consecutivamente ogni volta che appartengono a una delle coppie dellaccoppiamento eliminato, allora una colorazione golosa userà n colori, mentre il numero ottimale di colori per questo grafo è due. Esistono anche i grafi come quello con alta probabilità che un ordinamento dei vertici scelto a caso conduce a un numero di colori molto più grande del minimo Perciò, è di qualche importanza nella colorazione golosa scegliere lordinamento dei vertici con attenzione.

È NP-completo determinare, per un dato grafo G e un dato numero k, se esista un ordinamento dei vertici G che forzi lalgoritmo goloso a usare k o altri colori. In particolare, questo significa che è difficile trovare lordinamento peggiore per G.

                                     

2. Ordinamento ottimale

I vertici di qualsiasi grafo possono essere sempre ordinati in modo tale che lalgoritmo goloso produca una colorazione ottimale. Poiché, data una qualsiasi colorazione ottimale in cui il più piccolo insieme di colori è massimale, il secondo insieme di colori è massimale rispetto al primo insieme di colori, ecc., si possono ordinare i vertici in base ai loro colori. Allora quando si usa un algoritmo goloso con questo ordine, la colorazione risultante è automaticamente ottimale. In modo più forte, i grafi perfettamente ordinabili che includono i grafi cordali, i grafi di comparabilità e i grafi ereditari per le distanze hanno un ordinamento che è ottimale sia per il grafo stesso che per tutti i suoi sottografi indotti. Tuttavia, trovare un ordinamento ottimale per un grafo arbitrario è NP-difficile perché potrebbe essere usato per risolvere il problema NP-completo della colorazione dei grafi, e anche riconoscere i grafi perfettamente ordinabili è NP-completo. Per questa ragione, sono state usate euristiche che tentano di ridurre il numero di colori pur non garantendo un numero ottimale di colori.

                                     

3. Strategie euristiche di ordinamento

Un ordinamento comunemente usato per la colorazione golosa è di scegliere un vertice v di grado minimo, ordinare i vertici rimanenti e poi porre v allultimo posto nellordinamento. Se ogni sottografo di un grafo G contiene un vertice al massimo di grado d, allora la colorazione golosa per questo ordinamento userà al massimo d + 1 colori. Il più piccolo di tali d è noto comunemente come degenerazione del grafo.

Per un grafo di grado massimo Δ, qualsiasi colorazione golosa userà al massimo Δ + 1 colori. Il teorema di Brooks afferma che con due eccezioni cricche e cicli dispari sono richiesti al massimo Δ colori. Una prova del teorema di Brooks implica di trovare un ordinamento dei vertici nel quale i primi due vertici sono adiacenti al vertice finale ma non adiacenti tra loro, e ogni vertice successivo ha almeno un vertice anteriore. Per un ordinamento con questa proprietà, lalgoritmo della colorazione golosa usa al massimo Δ colori.



                                     

4. Schemi alternativi di selezione dei colori

È possibile definire un algoritmo della colorazione golosa nel quale i vertici del grafo dato sono colorati in una data sequenza, ma nel quale il colore scelto per ogni vertice non è necessariamente il primo colore disponibile; le strategie alternative di selezione dei colori sono state studiate allinterno della cornice degli algoritmi in linea "algoritmi online". Nel problema della colorazione dei grafi in linea, i vertici di un grafo sono presentati uno alla volta in un ordine arbitrario a un algoritmo di colorazione; lalgoritmo deve scegliere un colore per ciascun vertice, basato soltanto sui colori dei e sulle adiacenze tra i vertici già processati. In questo contesto, si misura la qualità di una strategia di selezione di colori mediante il suo rapporto competitivo, il rapporto tra il numero di colori che esso usa e il numero ottimale di dolori per il grafo dato.

Se non sono date restrizioni aggiuntive al grafo, il rapporto competitivo ottimale è soltanto lievemente sublineare. Tuttavia, per i grafi dintervallo, è possibile un rapporto competitivo costante, mentre per i grafi bipartiti e per i grafi sparsi si può ottenere un rapporto logaritmico. In realtà, per i grafi sparsi, la strategia normale di colorazione golosa di scegliere il primo colore disponibile ottiene questo rapporto competitivo, ed è possibile dimostrare un limite inferiore corrispondente sul rapporto competitivo di qualsiasi algoritmo di colorazione in linea.

                                     
  • La qualità della colorazione risultante dipende dall ordinamento prescelto. Esiste un ordinamento che conduce a una colorazione golosa in inglese greedy
  • ottima da un punto di vista globale attraverso la scelta della soluzione più golosa aggressiva o avida, a seconda della traduzione preferita del termine greedy
  • grafi che possono essere ordinati in modo tale che un algoritmo di colorazione golosa sia ottimale su ogni sottografo indotto. Questi includono i grafi
  • sono perfettamente ordinabili: una colorazione ottimale può essere ottenuta applicando un algoritmo di colorazione golosa ai vertici nell inverso di un ordinamento
  • Psittaculidi. Uccelletto compatto, con taglia attorno ai 20 cm, si presenta con colorazione base verde nelle parti superiori, rossa in quelle inferiori. Ha un minimo
  • 1842 sottospecie nominale P. r. pallidus van Someren, 1922, con colorazione generale del piumaggio più pallida. Predilige gli ambienti aridi delle
  • leggero e sottile e di colore nerastro. Ha taglia attorno ai 40 cm e la colorazione generale verde chiaro, fronte rossa, penne della corona e del dorso verdi
  • Deroptyus Wagler, 1832. Pappagallo di taglia attorno ai 35 cm, presenta una colorazione base verde, fronte e corona bianche, penne delle guance marroni con il
  • perforando le cellette opercolate con la spirotromba corta e robusta. È talmente golosa di miele che capita che ne ingurgiti in quantità eccessive, tanto da non
  • coperrtura dei vertici β G è uguale al numero di vertici nel grafo. La colorazione dei vertici di un grafo G corrisponde a una partizione dell insieme dei
  • dove è formato da setole rigide e da una corta e crespa lanugine. La colorazione è molto variabile indipendentemente dal sesso e dall età, e va dal cannella
  • rabbia l ittero è sintomo di malattia epatica caratterizzata dalla colorazione giallognola Influenze della teoria umorale e della teoria dei quattro