Grafo n colorabile
In un esercizio mi viene chiesto di trovare un algoritmo che determini il minimo numero di colori richiesti per colorare i nodi adiacenti di un grafo non orientato con colori distinti .Inoltre devo studiare la complessità dell'algoritmo e dire per quale dimensione dei dati ha senso utilizzarlo.
Non sò bene da dove iniziare a risolverlo,sopratutto non sò come determinare la complessità.
Per l'algoritmo ho provato a basarmi sul fatto che "Se G è un grafo il cui grado massimo di un nodo è d, allora G è (d+1)-colorabile",ma non sò se è giusta come base iniziale per svilupparlo
Non sò bene da dove iniziare a risolverlo,sopratutto non sò come determinare la complessità.
Per l'algoritmo ho provato a basarmi sul fatto che "Se G è un grafo il cui grado massimo di un nodo è d, allora G è (d+1)-colorabile",ma non sò se è giusta come base iniziale per svilupparlo
Risposte
Ciao,
a parte che questo starebbe meglio nella sezione Infomatica...
questo è il problema della k-colorazione di grafi versione ottimizzazione, come è ben noto non si trovano soluzioni ottime con algoritmi in tempo polinomiale ed il problema appartiene alla classe NP (o ad un suo pari insieme, non lo ricordo). vedi http://en.wikipedia.org/wiki/Graph_coloring
Ci sono varie tecniche che approssimano una soluzione, dalla ricerca locale ad algoritmi p-approssimati (anche se questi ultimi sono parecchio complicati).
Devi vedere quale è lo scopo di scrivere un algoritmo di risoluzione, se è solo uno pseudo-codice anche superesponenziale esaustivo o limitare con tecniche specifiche il tempo operazionale.
a parte che questo starebbe meglio nella sezione Infomatica...
questo è il problema della k-colorazione di grafi versione ottimizzazione, come è ben noto non si trovano soluzioni ottime con algoritmi in tempo polinomiale ed il problema appartiene alla classe NP (o ad un suo pari insieme, non lo ricordo). vedi http://en.wikipedia.org/wiki/Graph_coloring
Ci sono varie tecniche che approssimano una soluzione, dalla ricerca locale ad algoritmi p-approssimati (anche se questi ultimi sono parecchio complicati).
Devi vedere quale è lo scopo di scrivere un algoritmo di risoluzione, se è solo uno pseudo-codice anche superesponenziale esaustivo o limitare con tecniche specifiche il tempo operazionale.
Ecco,anche ame pareva fosse un problema $NP$,mi pareva strano solo che fosse nel testo di un esercizio....
"One":
Ecco,anche ame pareva fosse un problema $NP$,mi pareva strano solo che fosse nel testo di un esercizio....
ok
ora che sai questo, cosa vuoi fare?
Ho letto più volte il testo della pagina di Wikipedia postata prima e mi pare che,se non ho capito male,non c'è un modo relativamente semplice di risolvere questo problema.Tralasciando l'algoritmo e la parte di programmazione,stò cercando di capire per quale dimensione dei dati ha senso utilizzarlo;anche in questo caso non sò cosa rispondere di preciso...
L'esercizio probabilmente ti chiede un algoritmo per risolvere il problema. Nessuno si aspetta che questo algoritmo sia efficiente. Prova a buttar giù un semplice algoritmo e studiane la complessità (che sarà molto probabilmente esponenziale). Dopodiché puoi ragionare su che dimensione dell'input il tuo algoritmo può risolvere il problema in tempi "umani".
NOTA: dire che un problema è in NP non vuol dire che questo problema è difficile o non è risolvibile in tempo polinomiale*. La somma tra due numeri è un problema in NP eppure è un problema risolvibile efficientemente. È l'essere NP-hard che rende un problema intrattabile.
*(un problema di decisione è in NP, informalmente, se data una possibile soluzione è possibile verificare se tale soluzione è accettabile o meno efficientemente; il problema è che non è detto che trovare una soluzione accettabile sia possibile efficientemente; es.: data una 3-colorazione possiamo facilmente stabilire se sia colorabile o meno, dato un grafo trovare una 3-colorazione accettabile, o affermare che non esiste, è invece intrattabile).
NOTA: dire che un problema è in NP non vuol dire che questo problema è difficile o non è risolvibile in tempo polinomiale*. La somma tra due numeri è un problema in NP eppure è un problema risolvibile efficientemente. È l'essere NP-hard che rende un problema intrattabile.
*(un problema di decisione è in NP, informalmente, se data una possibile soluzione è possibile verificare se tale soluzione è accettabile o meno efficientemente; il problema è che non è detto che trovare una soluzione accettabile sia possibile efficientemente; es.: data una 3-colorazione possiamo facilmente stabilire se sia colorabile o meno, dato un grafo trovare una 3-colorazione accettabile, o affermare che non esiste, è invece intrattabile).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo