NP-Vollständig ( 3-Färbbarkeitsproblem)

Re(8): NP-Vollständig ( 3-Färbbarkeitsproblem)

Valen314 — Tue, 24 Jan 2006 19:15:07 GMT

oder kurz gesagt: wenn du keinen schimmer von komplexitätstheorie hast, ists nix für dich

Re(7): NP-Vollständig ( 3-Färbbarkeitsproblem)

TBone — Tue, 24 Jan 2006 18:02:14 GMT

Ahja ...

Re(6): NP-Vollständig ( 3-Färbbarkeitsproblem)

Valen314 — Tue, 24 Jan 2006 18:00:41 GMT

er soll Zeigen, daß das Problem "Färbe einen Graphen mit 3 Farben, sodaß 2 Knoten die mit einer kante verbunden sind nicht die selbe Farbe haben" in der Komplexitätsklasse NP ist (NP=schon ziemlich schwer laienhaft ausgedrückt)

Re: NP-Vollständig ( 3-Färbbarkeitsproblem)

Valen314 — Tue, 24 Jan 2006 17:58:52 GMT

Reduziers auf SAT (oder ein anderes NP vollständiges)

und dann noch den umgekehrten weg (SAT -> 3färbbarkeit reduzieren).

sollt sich eigentlich genügend sachen dazu in der Literatur finden lassen

Re: NP-Vollständig ( 3-Färbbarkeitsproblem)

komplexler — Tue, 24 Jan 2006 17:29:58 GMT

Wie soll man das denn machen? Mit polynomieller Reduktion, d.h. kann man andere NP-vollständige Probleme verwenden?

Re(6): NP-Vollständig ( 3-Färbbarkeitsproblem)

Qbus — Tue, 24 Jan 2006 16:07:35 GMT

Ja, präzise is schön und gut, aber für einen Laien unverständlich ...

das stimmt...

aber wer keine ahnung von der materie hat kann ihm eh nicht helfen - und wer ihm helfen kann, für den ist es auch nicht unverständlich

Re(5): NP-Vollständig ( 3-Färbbarkeitsproblem)

TBone — Tue, 24 Jan 2006 16:05:17 GMT

Ja, präzise is schön und gut, aber für einen Laien unverständlich ...

Re(4): NP-Vollständig ( 3-Färbbarkeitsproblem)

Qbus — Tue, 24 Jan 2006 16:03:25 GMT

naja, eigentlich hat er es so präzise wie möglich formuliert. ok, ich kenn das farbenproblem jetzt nicht, aber sonst...

Re(3): NP-Vollständig ( 3-Färbbarkeitsproblem)

TBone — Tue, 24 Jan 2006 10:15:14 GMT

Tjo ... ich aber auch nicht ... kannst das mal ausdeutschen?

Re: NP-Vollständig ( 3-Färbbarkeitsproblem)

Mike_72 — Tue, 24 Jan 2006 09:56:35 GMT

Also viel kann ich dir dazu auch nicht sagen, außer vielleicht folgenden Link:
http://de.wikipedia.org/wiki/F%C3%A4rbung_von_Graphen

Viel Glück!

Re(2): NP-Vollständig ( 3-Färbbarkeitsproblem)

kelpheus — Tue, 24 Jan 2006 09:52:04 GMT

nicht gerade die antwort die ich erwartet habe

Re: NP-Vollständig ( 3-Färbbarkeitsproblem)

TBone — Tue, 24 Jan 2006 09:51:22 GMT

NP-Vollständig ( 3-Färbbarkeitsproblem)

kelpheus — Tue, 24 Jan 2006 09:41:10 GMT

hallo, habe fogendes Problem. Soll die NP-Vollständigkeit vom 3-Färbbarkeitsproblme beweisen, aber habe keinen Ansatz . Kann mir irgendjemand helfen. Danke im voraus.

kelpheus