Hilfe beim Nachvollziehen der Musterlösung

Question

Hallo,

ich habe gerade Schwierigkeiten, die Musterlösung zu der Aufgabe b nachzuvollziehen. Aber zuerst noch eine kleine Frage zu der Definition von VC in der Aufgabestellung: Kann es sein, dass das letzte ^ eigentlich ein v sein müsste? Weil jede Kante des Graphen muss mit min. einem Knoten aus C verbunden sein, also genügt es doch wenn z.B. nur v1 in C liegt?

Zur b): Ich verstehe hier die Idee hinter der Vorgehensweise nicht ganz, deswegen kann ich die einzelnen Schritte auch nicht wirklich nachvollziehen...(Aber sehe ich das richtig, dass Gc zunächst ein "Graph" mit unverbundenen Knoten ist und ich dann abh. von G die Kanten selbst bilden muss?)

Zuerst stellt man fest, dass in Gc keine Kanten zwischen den Knoten, die in G eine Clique bilden, sein können (warum muss das so sein? In der Graphik "minimales C" ist mein VC doch teil der 3er-Clique, mit denselben Kanten und so?).

Dann heißt es, dass in Gc jede Kante an einen Knoten aus V\S stößt. Aber mit welchen Knoten aus S werden die Knoten aus V\S verbunden? Wo kommt das "wo in G eine Kante ist, ist in Gc keine" aus der Behauptung mit rein? Weil lt. Beweis darf ich die Kanten beliebig bilden solange ich nichts innerhalb der Clique verbinde. Gibt es dabei mehrere Möglichkeiten, meine Kanten zu konstruieren?

 

Wäre sehr dankbar, wenn mir jemand weiterhelfen könnte!

 

Answer 1

Hallo,

ich habe gerade Schwierigkeiten, die Musterlösung zu der Aufgabe b nachzuvollziehen. Aber zuerst noch eine kleine Frage zu der Definition von VC in der Aufgabestellung: Kann es sein, dass das letzte ^ eigentlich ein v sein müsste? Weil jede Kante des Graphen muss mit min. einem Knoten aus C verbunden sein, also genügt es doch wenn z.B. nur v1 in C liegt?

>Die Aufgabenstellung ist korrekt so. Bei einem Vertex-Cover müssen für jede Kante des Vertex-Covers beide anliegenden Knoten wieder selbst zum Vertex-Cover gehören. Und wenn k = 2 bedeutet das eben, dass 3 Knoten zum Vertex-Cover gehören, da der Teilgraph selbst auch zusammenhängen muss.

 

Zur b): Ich verstehe hier die Idee hinter der Vorgehensweise nicht ganz, deswegen kann ich die einzelnen Schritte auch nicht wirklich nachvollziehen...(Aber sehe ich das richtig, dass Gc zunächst ein "Graph" mit unverbundenen Knoten ist und ich dann abh. von G die Kanten selbst bilden muss?)

> G^c ist das Komplement (daher hoch c) des Graphen G. Wenn also für einen Graphen G zwei Knoten verbunden sind, dann sind genau diese beiden im Komplement nicht verbunden und umgekehrt.

 

Zuerst stellt man fest, dass in Gc keine Kanten zwischen den Knoten, die in G eine Clique bilden, sein können (warum muss das so sein? In der Graphik "minimales C" ist mein VC doch teil der 3er-Clique, mit denselben Kanten und so?).

Dann heißt es, dass in Gc jede Kante an einen Knoten aus V\S stößt. Aber mit welchen Knoten aus S werden die Knoten aus V\S verbunden? Wo kommt das "wo in G eine Kante ist, ist in Gc keine" aus der Behauptung mit rein? Weil lt. Beweis darf ich die Kanten beliebig bilden solange ich nichts innerhalb der Clique verbinde. Gibt es dabei mehrere Möglichkeiten, meine Kanten zu konstruieren?

> Ich hoffe, dass dir zum Verständnis diesen Teils die oberen Anmerkungen helfen. Allerdings darf man die Kanten nicht beliebig "verschieben". Aber da die Aufgabe allgemein gestellt ist, kann man sich selbst einen Graphen überlegen und dessen Knoten und Kanten definieren. Diesen kann man dann auf ein Vertex-Cover untersuchen.

 

Wäre sehr dankbar, wenn mir jemand weiterhelfen könnte!

> Ich hoffe ich konnte dir weiterhelfen.

> Viele Grüße, Daniel (Tutor)