Richtiges Verständnis vom Vertex Cover Problem? |
| 29.12.2010, 19:54 | Majin_Clodan | Auf diesen Beitrag antworten » |
Richtiges Verständnis vom Vertex Cover Problem?
Ich habe eine kleine Frage bzgl. des Vertex Cover Problems: Ich versuche gerade zu verstehen, was es mit dem Problem auf sich hat. Irgendwie verstehe ich nicht zu 100% das Problem. Ich fand zu diesem Problem die folgende Definition: Das Vertex Cover Problem (Knotenüberdeckungsproblem) ist ein Problem der Graphentheorie. Es fragt, ob es zu einem gegebenen einfachen Graphen und einer natürlichen Zahl k eine Knotenüberdeckung der Größe von höchstens k existiert. Das heißt, ob eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, sodass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist. Wenn es hierfür für k keine Einschränkung gibt, dann wäre es doch immer wahr, indem man für k mit der Anzahl aller Knoten gleichsetzt, oder? Oder versucht man die minimale Anzahl von Knoten zu finden, welche alle Kanten überdeckt? Ich verstehe leider nicht genau, was die mit "...eine Knotenüberdeckung der Größe von höchstens k existiert..." meinen, außer das, wenn man weiß, dass es eine Knotenüberdeckung der Größe k gibt, dass man dann vllt. schaut, ob es eine für k-1 gibt. Wäre supi, wenn mir da jemand auf die Sprünge helfen könnte, da ich da gerade auf dem Schlauch stehe.
MFG Majin_Clodan |
||
| 30.12.2010, 21:47 | Abakus | Auf diesen Beitrag antworten » |
| RE: Richtiges Verständnis vom Vertex Cover Problem? Hallo! Ich denke, das k ist vorgegeben und nicht selbst wählbar. Ggf. ist auch das minimale k zu ermitteln. Grüße Abakus
|
||
| 02.01.2011, 18:49 | plizzz | Auf diesen Beitrag antworten » |
Wie schon geschrieben wurde, ist k ein Teil des Inputs. Der Algorithmus bekommt einen Graphen und irgendein k dazu (zB k= n/2) und soll dann entscheiden, ob es eben einen Vertex Cover der Größe k gibt (wenn es einen der Größe <k gibt, dann auch einen der Größe k, aber er darf eben nicht größer als k sein). |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
