Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

22 giugno 2010

Esercizio (8 punti)

Il file graph.pl descrive un grafo non diretto; esso contiene dei fatti node(A). che rappresentano i nodi del grafo e dei fatti edge(A,B). che rappresentano gli archi.

Si desidera rimuovere dei nodi e partizionare i rimanenti nodi in modo tale che

• le due partizioni contengano approssimativamente lo stesso numero di nodi. Più precisamente, la differenza nel numero di nodi fra le partizioni non deve superare le 2 unità (cioè la partizione più grande non può avere più di 2 nodi in più rispetto alla più piccola).
• non ci siano archi che congiungono un nodo di una partizione con un nodo dell'altra.

Si scriva un programma CLP che trova il numero minimo di nodi da togliere per soddisfare i requisiti espressi sopra.