====
Abbiamo un grafo completo di ordine N (cioè un poligono di N lati con
tutte le possibili diagonali). Vogliamo colorarle con tre colori in
modo tale che non vi siano triangoli coi lati tutti dello stesso
colore. Questo si chiama problema di Ramsey multicolore
http://en.wikipedia.org/wiki/Ramsey%27s_theorem
(il problema originale, o più famoso, era bicolore, noto anche come il
problema delle strette di mano).
Ho scritto un programma che sfrutta il backtracking per trovare una
soluzione a questo problema, per N via via crescente - il programma è
scritto in python (lo so, non brilla per velocità) e lo allego qua
sotto.
Si dimostra "facilmente" (il punto è proprio qui) che si riesce a
colorare al massimo un grafo di ordine 16. Ora, dimostrare che un
grafo di ordine 17 è impossibile da colorare è semplice, vedi la
pagina di wikipedia. Dimostrare invece che un grafo di ordine 16 è
colorabile è difficile (cioè, nella pagina di wikipedia ci sono due
disegnini: sono due modi per farlo, e pare che siano unici, e quindi
la dimostrazione è già lì, ma io vorrei ripercorrere la strada;
insomma, faccio finta che quei due grafici non esistano e voglio
trovarli).
Domanda: come faccio a trovarli? Il programma ha questi tempi di esecuzione:
N=7: 0m0.116s
N=8: 0m3.082s
N=9: 3m35.373s
L'esplosione combinatoria è evidente: io dovrei arrivare a N=16. Il
fatto è che in giro si trovano valori anche per problemi molto più
difficili di questo, quindi in un qualche modo ci si deve riuscire.
Certamente non si può esplorare l'intero spazio delle configurazioni
(3^120 possibilità, a meno di simmetrie non calcolate), e il problema
è NP, quindi non ci sono trucchetti.
Immagino che, scrivendo il programma in C, potrei fare qualche passo
avanti, ma dubito di arrivare fino a N=16.
Stavo pensando di domandare alla mailing list dei Rudi Mathematici: da
un po' langue e magari questo problema potrebbe interessare. Ho letto
che in giro si parla anche di algoritmi genetici, ma non capisco bene
cosa posso fare evolvere qua. In che modo posso assegnare un peso a
configurazioni parziali "buone"?
Vabbè, questa non è una soluzione ma sono domande. Comunque sia,
questo è il programma:
N = 9
grafo=[[a,b] for a in xrange(N) for b in xrange(a+1,N)]
print grafo
lunghezza=len(grafo)
print "Numero archi: ",lunghezza
def formatriangolo(arco,colore):
papabili=[a for a in archi[colore] if len(set(a) & set(arco))!=0]
lun=len(papabili)
for i in xrange(lun):
for j in xrange(i+1,lun):
for k in xrange(j+1,lun):
if len(set(papabili[i])|set(papabili[j])|set(papabili[k]))==3:
return True
return False
archi=[[],[],[],[]]
def colora(n,colore):
if n>=lunghezza:
return True
arco=grafo[n]
archi[colore]+=[arco]
if not formatriangolo(arco,colore):
#bene, possiamo andare avanti
if colora(n+1,1):
return True
elif colora(n+1,2):
return True
elif colora(n+1,3):
return True
else:
#le ho provate tutte, i colori non vanno bene, torno indietro
archi[colore].remove(arco)
return False
else:
#la scelta del colore non va bene
archi[colore].remove(arco)
return False
return True
colora(0,1)
print archi[1]
print archi[2]
print archi[3]
Ciao
====
Ecco qua, dato che il numero di ottobre non è ancora uscito, non so se
qualcuno ha risolto il problema nel modo in cui vorrei farlo io. Se
qualcuno ha voglia di pensarci...
Ciao