Grafi

Da Zar un problemino carino sulla copertura dei grafi. Tanto per perdere un po' di tempo, mi sono divertito a scrivere uno stupido programmino c++ per disegnare il grafo di un problema sulla scacchiera generica di ordine n.

Il programma genera un file in formato dot, che può essere poi trasformato in un grafico con graphviz.

Ecco il grafo per una scacchiera 4x4:


Come potete notare, il grafo è bi-partito, quindi il problema non ha soluzione. Va meglio con schacchiere 5x5:


Non so se il problema ha soluzione in questo caso, magari faccio la prova a mano e vi faccio sapere!

E infine il grafo 8x8:


Un po' complicato, no?

(E' banale cambiare il programma per generare il grafo del problema "giro del cavallo", provare per credere).