 |
 |
 |
 |
 |
 |
Startseite » Forum » Vertex Cover Problem
Vertex Cover Problem
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hi Leute! :-) Also diesmal bezieht sich meine Frage auf das Vertex-Cover-Problem (Knotenüberdeckungsproblem). Dieses haben wir wie folgt definiert: 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 eine Knotenüberdeckung der Größe von höchstens existiert. Das heißt, ob eine aus maximal Knoten bestehende Teilmenge der Knotenmenge gibt, sodass jede Kante des Graphen mit mindestens einem Knoten aus verbunden ist. Leider verstehe ich nicht genau diese Definition. Ist jetzt das Problem, eine minimale Knotenüberdeckung zu finden oder das es überhaupt eine Knotenüberdeckung gibt? Verstehe leider nicht genau, was man mit "eine Knotenüberdeckung der Größe von höchstens existiert" meint. Wäre echt supi, wenn ihr mir da helfen könntet. :-) MFG Clodan Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg." |
|
 |
|
Es geht nicht darum, eine minimale Überdekcung zu finden (also eine Überdeckung, die die Überdeckungseigenschaft verliert, wenn man einen Knoten wegnimmt) noch eine kleinste Überdekcung (also eine mit dem kleinstmöglichen sonder einfach allgemein zu gegebenem zu entscheiden, ob eine Überdeckung existiert. Das berühmte "Haus vom Nikolaus" hat 6 Knoten und Kanten. Gibt es für ein Vertex Cover? Das kann man aus dem Stegreif beantworten mit JA, denn wenn man alle bis auf enien Knoten verwenden darf, hat man von jeder Kante mindestens einen ihrer Endpunkte gewählt. Gibt es ein Cover für ? Gewiss nicht, denn das hieße ja, dass alle Kanten an dem einen das Cover bildenden Knoten enden müssten; das ist bei diesem Grafen nicht der Fall. Gibt es für ein Vertex Cover? Ja. Zum Beispiel den Kreuzpunkt in der Mitte sowie den Dachfirst. Oder auch: Zwei gegenüber liegende Ecken des "Mauer"-Vierecks. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
836537
836421