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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

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


Aufgabe

Blossom Counter.svg

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 *

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


Aufgabe

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


Aufgabe *

Clubagroup official insignia.jpg

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


Aufgabe *

Cograph g5.png

Bestimme die Knotenüberdeckungszahl des abgebildeten Graphen.


Aufgabe *

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


Aufgabe *

Charakterisiere diejenigen Graphen, deren Knotenüberdeckungszahl gleich ist.


Aufgabe

2-cube.svg

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


Aufgabe

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.


Aufgabe

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


Aufgabe *

BaummitArmen1.png

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)

Blossoms can't be ignored.svg

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)

Icosahedron graph.svg

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)