++ 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 Knotenüberdeckung Formel Hilfe Hausaufgabeb
Knotenüberdeckung

Eine Knotenüberdeckung ist in der Graphentheorie eine Teilmenge der Knoten eines Graphen, die insgesamt mit allen Kanten inzident sind.

Das Komplement einer kleinsten Knotenüberdeckung ist in jedem Graph eine größte stabilen Menge. Die Bestimmung beider Größen ist im allgemeinen NP-schwer. In bipartiten Graphen können sie über die Paarungszahl in polynomieller Zeit bestimmt werden.

siehe auch: Cliquen und stabile Mengen
Dieser Artikel ( Knotenüberdeckung ) 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 +++