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.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

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