++ Mathe Formeln ++ Mathematik Lexikon ++ Lösungen ++ Hausaufgaben ++ Algebra ++ Lernen ++ Übungen ++ Schule ++ Geometrie ++

Navigation

Mathematik Begriffe
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 123      
Goldkurs

Mathematik Begriff Erklärung Vertex Cover Formel Hilfe Hausaufgabeb
Vertex Cover

Vertex Cover (kurz VC) ist ein Graphproblem, bei dem es darum geht, mit Knoten Kanten abzudecken.

Für einen Graphen G = (V,E) ist eine Menge V' \subseteq V gesucht, für die gilt:

\forall (a,b)\in E : a \in V' \or b \in V'

In seiner Entscheidungsvariante übergibt man außer den Graphen noch einen Parameter k und es ist zu entscheiden, ob es ein Vertex Cover dieser Kardinalität gibt. Die Lösung ist nicht unbedingt eindeutig.

In der Optimierungsvariante ist ein VC mit minimaler Kardinalität gesucht.

Das Problem ist NP-vollständig.

Beispiel
vergrößern
Beispiel

 

Beispiel

Der erste Graph ist der Ursprungsgraph. Die anderen sind jeweils ein Vertex Cover, wobei die eingekreisten Knoten die Knoten aus V' (aus dem Vertex Cover) sind. Das erste Vertex Cover (also der zweite Graph) ist hierbei ein minimales Vertex Cover.
Dieser Artikel ( Vertex Cover ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence. 
+++ Mathe Formeln ++ Mathematik Lexikon ++ Lösungen ++ IMPRESSUM ++ Algebra ++ Lernen ++ Übungen ++ Schule ++ Geometrie +++