Knotenüberdeckung - LinkFang.de





Knotenüberdeckung


Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig.

Definitionen

Sei [math]G=(V,E)[/math] ein ungerichteter Graph und [math]U[/math] eine Teilmenge von [math]V[/math], wobei [math]V[/math] die Menge der Knoten und [math]E[/math] die Menge der Kanten ist. Dann ist [math]U[/math] eine Knotenüberdeckung (Vertex Cover) von [math]G[/math], wenn jede Kante von [math]G[/math] wenigstens einen Knoten aus [math]U[/math] enthält. Entsprechend dazu ist eine Kantenüberdeckung des Graphen eine Teilmenge [math]M[/math] seiner Kantenmenge, so dass jeder Knoten in mindestens einer Kante aus [math]M[/math] enthalten ist.

Eine Knotenüberdeckung [math]U[/math] von [math]G[/math] nennt man minimal, wenn es keinen Knoten [math]v\in U[/math] gibt, so dass [math]U[/math] ohne [math]v[/math] immer noch eine Knotenüberdeckung ist. Gibt es in [math]G[/math] keine Knotenüberdeckung, die weniger Elemente als [math]U[/math] enthält, so nennt man [math]U[/math] eine kleinste Knotenüberdeckung. Die Anzahl der Knoten einer kleinsten Knotenüberdeckung von [math]G[/math] nennt man Knotenüberdeckungszahl von [math]G[/math].

Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen, da es nicht auf die Richtung oder Vielfachheit der Kanten ankommt.

Wichtige Aussagen und Sätze

  1. Die Knotenüberdeckungszahl eines Graphen ist mindestens so groß wie seine Paarungszahl, da die Knoten der Kanten einer größten Paarung nur zu einer Paarungskante inzident sein können.
  2. Andererseits kann die Knotenüberdeckungszahl höchstens so groß sein, wie das 2-fache der Paarungszahl, da die Knoten aller Paarungskanten eine gültige Knotenüberdeckung ergeben.
  3. In bipartiten Graphen stimmen Knotenüberdeckungszahl und Paarungszahl überein.

Probleme und Komplexität

Das Entscheidungsproblem zu einem Graphen [math]G[/math] und einer natürlichen Zahl [math]k[/math] zu entscheiden, ob [math]G[/math] eine Knotenüberdeckung der Größe höchstens [math]k[/math] enthält, wird Knotenüberdeckungsproblem genannt. Das zugehörige Optimierungsproblem fragt nach der Knotenüberdeckungszahl eines Graphen. Das zugehörige Suchproblem fragt nach einer kleinsten Knotenüberdeckung.

Nachweis der NP-Schwere

Das Knotenüberdeckungsproblem ist NP-vollständig, das zugehörige Optimierungs- und Suchproblem ist NP-äquivalent. Die NP-Schwere des Knotenüberdeckungsproblems folgt aus dem Satz, dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht, denn das Komplement einer kleinsten Knotenüberdeckung ist immer eine größte stabile Menge und umgekehrt.

In Polynomialzeit lösbare Fälle

König konnte jedoch schon 1931 zeigen, dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht (Satz von König). Für das Problem, eine größte Paarung zu finden, gibt es aber einen polynomiellen Algorithmus. In bipartiten Graphen lässt sich daher auch eine kleinste Knotenüberdeckung und eine größte stabile Menge in polynomieller Zeit berechnen. Tatsächlich gilt sogar etwas stärker, dass die Knotenüberdeckungszahl in perfekten Graphen in polynomieller Zeit berechnet werden kann.

Approximation einer Knotenüberdeckung

Es existiert ein Approximationsalgorithmus, der eine Knotenüberdeckung mit relativer Güte 2 berechnet. Es ist kein besserer Algorithmus mit fester Güte bekannt.

Der Algorithmus berechnet eine nicht-erweiterbare Paarung [math]M[/math] in [math]G[/math]. Da eine derartige Paarung immer eine Knotenüberdeckung darstellt und höchstens doppelt so groß ist wie eine minimale Knotenüberdeckung, berechnet der Algorithmus eine Knotenüberdeckung mit relativer Güte 2.

[math]G = (V, E)[/math]: Graph
approx_vertex_cover([math]G[/math])
1   [math]K \leftarrow\varnothing[/math]
2  solange  [math]E\neq\varnothing[/math]:
3      wähle eine beliebige Kante [math]e = {u,v} \in E[/math]
4      [math]K\leftarrow K \cup\left\{u,v\right\}[/math]
5      entferne alle Kanten aus [math]E[/math], die inzident zu [math]u[/math] oder [math]v[/math] sind
6  return [math]K[/math]

Der Algorithmus hat bei einer geeigneten Datenstruktur eine Laufzeit von [math]O(\mid E\mid)[/math].

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Knotenüberdeckung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.