< Sterngraph < Knotenüberdeckungszahl
Bei einem Sterngraphen (sagen wir mit zumindest drei Knotenpunkten) ist die Knotenüberdeckungszahl gleich , man kann ja das Zentrum als einelementige Knotenüberdeckungsmenge nehmen. Dies ist die einzige optimale Knotenüberdeckung. Die Menge aller Blätter ist eine minimale Knotenüberdeckung, aber keine optimale Knotenüberdeckung.
This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.