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

Übungsaufgaben

Aufgabe

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

Aufgabe

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

Kommentar:

Der Satz behauptet, dass es bei einer nicht optimalen Paarung einen alternierenden Weg mit zwischen unabgedeckten verschiedenen Punkten gibt. Der Beweis zeigt, wie man einen solchen alternierenden Weg unter Verwendung einer optimalen Paarung findet und wie man damit die gegebene Paarung zu einer optimalen Paarung abändern kann. Das Beispiel ist besonders einfach, da es nur eine optimale Paarung gibt, nämlich diejenige, die aus den abstehenden Kanten besteht. Nennen wir diese $Q$. Wir bestimmen die symmetrische Differenz von $P$ und $Q$, diese besteht aus den drei Kanten links. Dies ist wie im Beweis des Satzes von Berge vorausgesagt eine alternierender Weg mit einer Kante aus $Q$ (nämlich zwei Stück) mehr als Kanten aus $P$ (nämlich eine). Wir schmeißen aus $P$ die Dreieckseite links heraus und nehmen die zwei abstehenden Kanten hinzu und erhalten eine optimale Paarung (die in diesem Beispiel mit $Q$ übereinstimmt).

 

Aufgabe *

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

Aufgabe *

Es sei  $G=(V,E)$  ein Graph und  $W\subseteq V$  eine Teilmenge der Knotenmenge. Zeige, dass $W$ genau dann eine Knotenüberdeckung von $G$ ist, wenn  $E\cap {𝔓}_2(V\setminus W)=\mathrm{\varnothing }$  gilt.

Aufgabe *

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

Kommentar:

Wir analysieren erst mal den Graphen. Der Graph hat $9$ Knotenpunkte, wie man unmittelbar sieht. Der König kann um ein Feld in jede Richtung ziehen, horizontal, vertikal und diagonal. Die Anzahl der Kanten bestimmen wir entlang dieser Einteilung. Es gibt sechs horizontale, sechs vertikale und vier diagonale Kanten, also insgesamt $16$ Kanten. Eine Knotenüberdeckung muss all diese Kanten abdecken. Die Paarungszahl gibt eine erste Orientierung für die Knotenüberdeckungszahl, suchen wir also nach zueinander disjunkten Kanten. Da gibt es außen im Uhrzeigersinn vier Kanten, beginnend mit rechts oben und oben mittig. Die Paarungszahl ist also genau $4$, da sie ja höchstens so groß wie die Hälfte der Punktanzahl sein kann. Somit ist die Knotenüberdeckungszahl zumindest $4$. Wir behaupten, dass sie $5$ ist. Beispielsweise bildet der zentrale Punkt zusammen mit den $4$ weißen Feldern eine Knotenüberdeckung. Dies kann man sich mit einer Fallunterscheidung überlegen, ob der zentrale Punkt dazu oder nicht dazugehört.

 

Aufgabe *

Bestimme die Knotenüberdeckungszahl des abgebildeten Graphen.

Aufgabe *

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

Aufgabe *

Charakterisiere diejenigen Graphen, deren Knotenüberdeckungszahl gleich $1$ ist.

Aufgabe

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

Aufgabe

Es sei  $G=(V,E)$  ein bipartiter Graph mit einer Zerlegung  $V=A\uplus B$.  Zeige, dass die Knotenüberdeckungszahl von $G$ durch das Minimum der Anzahl von $A$ und der Anzahl von $B$ nach oben beschränkt ist.

Aufgabe

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

Aufgabe *

Wir betrachten Graphen

$G=S(n_1,n_2,\dots ,n_k)$

von der folgenden Bauart: Es gibt ein Zentrum $z$, an das $k$ lineare Graphen (Strahlen) der Länge $n_1,n_2,\dots ,n_k$ anliegen. Ansonsten gibt es keine weiteren Kanten.

1. Skizziere einen solchen Graphen für  $k=5$  und

   $(n_1,n_2,n_3,n_4,n_5)=(2,3,1,3,4).$

2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von $G$.
3. Beschreibe eine minimale Knotenüberdeckung von $G$, die $z$ enthält, und eine minimale Knotenüberdeckung, die $z$ nicht enthält.
4. Bestimme die Knotenüberdeckungszahl von $G$.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Finde im abgebildeten Graphen (mit der abgebildeten nicht optimalen Paarung $P$ und einer optimalen Paarung $Q$) 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 $K_n$.

Aufgabe (2 Punkte)

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