Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 21



Übungsaufgaben

Zeige, dass ein Graph, bei dem der Minimalgrad und der Maximalgrad gleich ist, ein Rundgang sein muss.



Finde im abgebildeten Graphen (mit der abgebildeten nicht optimalen Paarung und einer optimalen Paarung ) den im Satz von Berge postulierten alternierenden Weg und die dazugehörige optimale Paarung.



Zeige, dass man im Satz von Berge nicht darauf verzichten kann, dass die Endpunkte der alternierenden Wege verschieden sind.



Es sei ein Graph und eine Teilmenge der Knotenmenge. Zeige, dass genau dann eine Knotenüberdeckung von ist, wenn gilt.



Bestimme die Knotenüberdeckungszahl zum Spielzuggraphen des Königs auf einem -Schachbrett.



Bestimme die Knotenüberdeckungszahl des abgebildeten Graphen.



Bestimme zu einem linearen Graphen der Länge die maximale Anzahl an Knoten in einer minimalen Knotenüberdeckung.



Charakterisiere diejenigen Graphen, deren Knotenüberdeckungszahl gleich ist.



Zeige, dass im abgebildeten Graphen jede minimale Knotenüberdeckung optimal ist.



Es sei ein bipartiter Graph mit einer Zerlegung . Zeige, dass die Knotenüberdeckungszahl von durch das Minimum der Anzahl von und der Anzahl von beschränkt ist.



Bestimme die Knotenüberdeckungszahl des Potenzmengengraphen zu einer dreielementigen Menge.



Wir betrachten Graphen

von der folgenden Bauart: Es gibt ein Zentrum , an das lineare Graphen (Strahlen) der Länge anliegen. Ansonsten gibt es keine weiteren Kanten.

  1. Skizziere einen solchen Graphen für und
  2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von .
  3. Beschreibe eine minimale Knotenüberdeckung von , die enthält, und eine minimale Knotenüberdeckung, die nicht enthält.
  4. Bestimme die Knotenüberdeckungszahl von .




Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Finde im abgebildeten Graphen (mit der abgebildeten nicht optimalen Paarung und einer optimalen Paarung ) den im Satz von Berge postulierten alternierenden Weg und die dazugehörige optimale Paarung.



Aufgabe (3 Punkte)

Bestimme die Knotenüberdeckungszahl des abgebildeten Graphen.



Aufgabe (2 Punkte)

Bestimme die Knotenüberdeckungszahl des vollständigen Graphen .



Aufgabe (2 Punkte)

Bestimme die Knotenüberdeckungszahl des Potenzmengengraphen zu einer vierelementigen Menge.




<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)