Prof. Dr. R. Laue                                                                                                                                  WS0405
                                Künstliche Intelligenz
                                Übungsblatt 5
                                Abgabe: 24.11.04  nach der Vorlesung

URL:         /axel/ai_ws0405_blatt5.html

Aufgabe 5 (9 Punkte)

Lösen Sie das Graphenfärbungs Problem mittels Prolog Programm.
Zum Start wird folgender Programmausschnitt zur Verfügung gestellt:

farbe(rot).
farbe(blau).
farbe(gelb).
graph(
ecken([1,2,3,4,5]),
/* liste = [..,..,,..,] der ecken */
kanten( [ kante(1,2), kante(1,3), kante(2,3), kante(3,4), kante(1,5)] )
/* liste der kanten */
).

/* eine faerbung hat das format = liste der form
   [farb(1,rot),farb(2,gelb), .... ]
*/

/* so wurde der graph angegeben */

/* idee ist jetzt eine faerbung des graphen zu finden
   indem man alle moeglichen generiert und dann
   testet ob ok */

/* alle moeglichen */
allefarben([],[]). /* ohne knoten = ohne farben */
allefarben([Kopf|Schwanz1],[farb(Kopf,Farb)|Schwanz2]) :-
              farbe(Farb), allefarben(Schwanz1,Schwanz2).

/* dieser | operator trennt fuer eine rekursive definition den
   kopf vom rest einer liste */

/* nun kann man z.b. mit allefarben([1,2,3],X)
   sich alle moeglichen faerbungen von 3 knoten mit
   den drei farben anzeigen lassen */

/* die faerbungs routine soll wie folgt
   funktionieren */
faerbung(graph(ecken(V),kanten(E),Col):-
        allefarben(V,Col),
        gutefarbe(E,Col).

/* was fehlt ist das praedikat gutefarbe */


Abzugeben ist ein fertiges Prolog Programm was mittels des Prädikas faerbung erlaubt alle  Faerbungen eines Graphen auszugeben.
Testen Sie ob man bei einem vollständigen Graphen mit 4 Punkten mit  weniger als 4 Farben auskommt, und wieviel Färbungen es gibt.