Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 25. Juni 2019 

Knotenüberdeckungszahl


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Als Knotenüberdeckungszahl eines Graphen bezeichnet man in der Graphentheorie die Anzahl Knoten seiner kleinstmöglichen Knotenüberdeckung .

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

siehe auch: Cliquen und stabile Mengen



Bücher zum Thema Knotenüberdeckungszahl

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Knoten%FCberdeckungszahl.html">Knotenüberdeckungszahl </a>