Kleines Graphenspiel

[Apo]

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.]

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

 

[Leroy42]

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

Ist das eigentlich dasselbe wie NP-vollständig?

 

[SlaterB]

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