Vertex Cover Problem < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:50 Mi 29.12.2010 | | Autor: | Clodan |
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 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.
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 k existiert" meint. :(
Wäre echt supi, wenn ihr mir da helfen könntet. :)
MFG Clodan
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
uni-protokolle.de
onlinemathe.de
matheboard.de
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:42 Do 30.12.2010 | | Autor: | felixf |
Moin!
> 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 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.
Sei $V$ die Knotenmenge und $E [mm] \subseteq [/mm] V [mm] \times [/mm] V$ die Kantenmenge.
> 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 k existiert"
> meint. :(
Es gibt immer eine Knotenueberdeckung: $V$ selber ist etwa eine. Formal gesagt: eine Teilmenge $U [mm] \subseteq [/mm] V$ ist eine Knotenueberdeckung, wenn $E [mm] \subseteq [/mm] V [mm] \times [/mm] U [mm] \cup [/mm] U [mm] \times [/mm] V$ gilt.
Daraus folgt: ist $U$ eine Knotenueberdeckung und $U' [mm] \supseteq [/mm] U$ irgendeine Obermenge, so ist $U'$ ebenfalls eine Knotenueberdeckung. Und die groesste ist halt $V$ selber.
Die interessante Frage ist nun: wie klein kann so eine Knotenueberdeckungsmenge sein?
Oder anders formuliert: wie gross ist das kleinste $k$, so dass es eine Knotenueberdeckungsmenge $U$ mit $|U| = k$ gibt? Ein "kleineres" Problem ist die Frage: gegeben $k$, gibt es eine Knotenueberdeckungsmenge $U$ mit hoechstens $k$ Elementen? (Falls $k [mm] \le [/mm] |V|$ gilt, so gibt es dann auch eine mit genau $k$ Elementen, da man beliebig viele Elemente zu $U$ hinzunehmen kann.)
Wenn man dieses "kleinere" Problem effizient loesen kann, dann auch das finden eines kleinsten $k$s (einfach eine binaere Suche machen). Deswegen konzentriert man sich auf das "kleinere" Problem mit dem festen $k$, und das ist das Knotenueberdeckungsproblem (VCP).
Ich hoffe das macht's etwas verstaendlicher...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:08 Do 30.12.2010 | | Autor: | Clodan |
Also anders gesagt versucht man herauszufinden, ob man nur mit k Knoten eine Knotenüberdeckung des Graphen V schafft? Also würde ich z.B. bei V kontrollieren, ob ich mit k = 3 eine Knotenüberdeckung schaffe d.h. ich setze selber den Wert k und kontrolliere dann, ob ich mittels diesem Wert eine Knotenüberdeckung schaffe?
Wenn dem so wäre, könnte man doch das Vertex-Cover-Problem wie folgt definieren:
Bei dem Vertex-Cover-Problem versucht man zu einem gegebenen Graphen G = (V,E), einer Teilmenge V' Teilmenge V und einer gegebenen (ist doch gegeben dann, oder?) natürlichen Zahl n eine minimale Knotenüberdeckung der Kardinalität n zu finden. Die entscheidende Frage hierbei ist, ob es eine Knotenüberdeckung der Größe n gibt oder nicht (da ja n gegeben ist).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:41 Do 30.12.2010 | | Autor: | felixf |
Moin!
> Also anders gesagt versucht man herauszufinden, ob man nur
> mit k Knoten eine Knotenüberdeckung des Graphen V schafft?
> Also würde ich z.B. bei V kontrollieren, ob ich mit k = 3
> eine Knotenüberdeckung schaffe d.h. ich setze selber den
> Wert k und kontrolliere dann, ob ich mittels diesem Wert
> eine Knotenüberdeckung schaffe?
Genau.
> Wenn dem so wäre, könnte man doch das
> Vertex-Cover-Problem wie folgt definieren:
>
> Bei dem Vertex-Cover-Problem versucht man zu einem
> gegebenen Graphen G = (V,E), einer Teilmenge V' Teilmenge V
> und einer gegebenen (ist doch gegeben dann, oder?)
> natürlichen Zahl n eine minimale Knotenüberdeckung der
> Kardinalität n zu finden. Die entscheidende Frage hierbei
> ist, ob es eine Knotenüberdeckung der Größe n gibt oder
> nicht (da ja n gegeben ist).
Sie muss nicht minimal sein. Aber sonst ist's ok.
Bei der Frage nach der Existenz spricht man von einem Entscheidungsproblem, bei der Frage nach dem Finden einer konkreten solchen Menge von einem Berechnungsproblem (wobei die Antwort "gibt es nicht" auch eine Ausgabe ist).
Die urspruengliche Formulierung aus deiner ersten Frage ist ein Entscheidungsproblem.
LG Felix
|
|
|
|
