imported>Cheongnyangni-dong: /* Wichtige Aussagen und Sätze */

2025-09-23T11:17:37Z

Wichtige Aussagen und Sätze

Neue Seite

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 ==
[[Datei:Vertex-cover.svg|300px|mini|Zwei (nichtminimale) Knotenüberdeckungen.]]
[[Datei:Minimum-vertex-cover.svg|300px|mini|Zwei minimale Knotenüberdeckungen.]]

Sei <math>G=(V,E)</math> ein ungerichteter [[Graph (Graphentheorie)|Graph]] mit der [[Knotenmenge]] <math>V</math> und der [[Kantenmenge]] <math>E</math>. Dann ist eine [[Teilmenge]] <math>U \subseteq V</math> eine ''Knotenüberdeckung'' (englisch ''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>.

[[Gerichteter Graph|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 ==
# Die Knotenüberdeckungszahl eines Graphen ist mindestens so groß wie seine [[Matching (Graphentheorie)#Definitionen|Paarungszahl]], da die Knoten der Kanten einer größten Paarung nur zu einer Paarungskante inzident sein können.
# Andererseits kann die Knotenüberdeckungszahl höchstens doppelt so groß sein wie die Paarungszahl, da die Knoten aller Paarungskanten eine gültige Knotenüberdeckung ergeben.
# In [[Bipartiter Graph|bipartiten Graphen]] stimmen Knotenüberdeckungszahl und Paarungszahl überein. ([[Satz von König (Graphentheorie)|Satz von König]])
# Eine Knotenüberdeckung ist genau das Komplement einer [[Stabile Menge|stabilen Menge]]. In diesem Sinne ist das Knotenüberdeckungsproblem dual zum Stabilitätsproblem.

== Probleme und Komplexität ==
Das [[Entscheidbar|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ändigkeit|NP-vollständig]], das zugehörige Optimierungs- und Suchproblem ist [[NP-Äquivalenz|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. Das Knotenüberdeckungsproblem gehört zur Liste der [[Karps 21 NP-vollständige Probleme|21 klassischen NP-vollständigen Probleme]], von denen [[Richard M. Karp|Richard Karp]] [[1972]] die Zugehörigkeit zu dieser Klasse zeigen konnte.

=== In Polynomialzeit lösbare Fälle ===
Der ungarische Mathematiker [[Dénes Kőnig]] konnte schon 1931 zeigen, dass in [[Bipartiter Graph|bipartiten Graphen]] die Knotenüberdeckungszahl der [[Paarungszahl]] entspricht ([[Satz von König (Graphentheorie)|Satz von König]]). Für das Problem, eine [[größte Paarung]] zu finden, gibt es aber einen [[Polynomieller Algorithmus|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 [[Perfekter Graph|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 (Graphentheorie)|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<br />
''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(|E|)</math>.

== Weblinks ==

{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 21|Eine Vorlesung über Knotenüberdeckungen im Rahmen eines Kurses zur diskreten Mathematik}}

== Literatur ==
* {{Literatur
|Autor=[[Reinhard Diestel]]
|Titel=Graphentheorie
|Auflage=4.
|Verlag=Springer
|Ort=Berlin
|Datum=2010
|ISBN=978-3-642-14911-5
|Online=[https://diestel-graph-theory.com/ diestel-graph-theory.com]}}
* {{Literatur
|Autor=[[Bernhard Korte]], [[Jens Vygen]]
|Titel=Kombinatorische Optimierung. Theorie und Algorithmen
|Reihe=Springer Spektrum
|Auflage=2.
|Verlag=Springer
|Ort=Heidelberg
|Datum=2012
|ISBN=978-3-642-25400-0}}

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Grundbegriff (Graphentheorie)]]
[[Kategorie:Komplexitätstheorie]]

Knotenüberdeckung - Versionsgeschichte

imported>Cheongnyangni-dong: /* Wichtige Aussagen und Sätze */