# Kleines Graphenspiel



## Apo (9. Okt 2006)

Hi,

ich wollte eigentlich nur ein Petrinetz mit Java simulieren, um Deadlocks und Traps besser zu veranschaulichen. Doch es wurde ein kleines Denkspiel 

Ziel des Spiel ist es, alle Knoten einfarbig zu bekommen.
Wenn man auf einen Knoten klickt, wechselt dieser und seine Nachbarknoten die Farben nach einer bestimmten Reihenfolge.
Klingt recht einfach ... ist es aber meistens nicht  vor allem wenn man mehr als 2 Farben hat.

Es ist noch im Betastadium, deshalb würde ich mich über einige Tester sehr freuen. 

Der Sourcecode ist natürlich mit dabei. 

Screenshot: Schau mich an

Download: Download mich


----------



## B. Sc. Inf. (29. Okt 2006)

Das ist auch nicht einfach. Das Faerbbarkeitsproblem ist NP-Hart.


----------



## Leroy42 (30. Okt 2006)

Ich bin jetzt schon ein paar Mal über den Begriff *NP-hart* gestolpert.  :shock: 

Ist das eigentlich dasselbe wie _NP-vollständig_?


----------



## SlaterB (30. Okt 2006)

wozu gibts denn google und Wikipedia? 

ich glaube man kann es so ausdrücken:
NP-vollständig = in NP und löst alle (anderen) NP-Probleme in NP-Zeit

NP-hart = löst alle (anderen) NP-Probleme in NP-Zeit falls selber in NP

http://de.wikipedia.org/wiki/NP-Vollständigkeit


----------

