matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieVertex Cover Problem
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Vertex Cover Problem
Vertex Cover Problem < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Vertex Cover Problem: Verständnisfrage
Status: (Frage) beantwortet Status 
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

        
Bezug
Vertex Cover Problem: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Vertex Cover Problem: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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).

Bezug
                        
Bezug
Vertex Cover Problem: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]