    
maria
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 23. April, 2002 - 16:36: | 
|
Das sind meine Probleme...
Beim Problem CLIQUE geht es um die Cliquenzahl w(G) eines Graphen.
Formulieren sie die Entscheidungs-, die OPtimierungs - und die Suchversion von Clique.
Angenommen eine dieser Versionen ist in POlynominalzeit lösbar, zeigen sie das es die anderen beiden auch sind.
HAMILTONIAN ist das Problem zu entscheiden ob ein Graph einen Hamiltonkreis enthält. k-COL ist das Problem, zu entscheiden ob ein Graph mit k Farben gefärbt werden kann. k-Clique ist das Problem zu entscheiden ob ein GRaph eine Clique der Größe k enthält.
Zeigen sie das HAMILTONIAN, 3-COL und die Entscheidungsversion von CLIQUE in NP liegen.
Zeigen sie das 17-CLIQUE und 2-COL in P liegen.
Viele Dank für HInweise etc. Maria
|
