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

Übungsaufgaben

Aufgabe

Es sei ${}G=(V,E)$ ein zusammenhängender bipartiter Graph. Zeige, dass es nur eine (bis auf die Rolle der Teile) bipartite Zerlegung ${}V=A\uplus B$ gibt.

Aufgabe

Zeige, dass ein Untergraph eines bipartiten Graphen wieder bipartit ist.

Aufgabe

Zeige, dass ein Graph genau dann bipartit ist, wenn jede Zusammenhangskomponente davon bipartit ist.

Aufgabe *

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge ${}3$ gibt.

Aufgabe

Auf dem Bolzplatz hat die Algebra gegen die Topologie gespielt. Nach dem Spiel beim Grillen sprechen sie über ihre besten Zweikämpfe. Heinz, ein Algebraiker sagt, „ich hatte einen verdammt harten Zweikampf mit August“. August sagt: „meine Zweikämpfe mit Petra waren auch nicht ohne“. Petra sagt: „die Beate hab ich schön alt aussehen lassen“, was Beate kontert, indem sie sagt, dass sie dafür den Bernd umgenietet hat. Bernd wiederum sagt, dass seine Blutgrätsche gegen Alex bestimmt weh getan hat. Ist Alex ein Algebraiker oder ein Topologe?

Aufgabe

Zeige, dass ein Wald bipartit ist.

Aufgabe *

Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem ${}3\times 3$-Brett wie abgebildet.

1. Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.
2. Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

Aufgabe

Wir betrachten den Spielzuggraphen zum Turm beim Schach auf einen ${}n\times n$-Brett.

1. Zeige, dass dies bei ${}n\leq 2$ bipartit ist.
2. Zeige, dass dies bei ${}n\geq 3$ nicht bipartit ist.

Aufgabe

Wir betrachten in einem Kreuzworträtsel die Wörter als Knotenpunkte eines Graphen und verbinden zwei verschiedene Wörter durch eine Kante, falls sie sich in einem Kästchen treffen. Ist ein solcher Graph bipartit?

Aufgabe

Es sei ${}G$ ein Graph, der eine disjunkte Vereinigung von ${}m$ Kanten sei. Auf wie viele Arten kann man ${}G$ als bipartiten Graphen auffassen? Wie viele optimale Paarungen gibt es?

Kommentar:

Sei ${}\{u_{1},v_{1}\},\dots ,\{u_{m},v_{m}\}$ die ${}m$ disjunkte Kanten von ${}G$. Zu bestimmen ist die Anzahl der bipartiten Zerlegungen

$\{u_{1},v_{1},\dots ,u_{m},v_{m}\}=A\uplus B.$

Man beachte, dass bei einer solchen Zerlegung die Reihenfolge von ${}A$ und ${}B$ keine Rolle spielt, d.h. ie Zerlegungen ${}A\uplus B$ und ${}B\uplus A$ werden als gleich angesehen.

Um eine Zerlegung zu finden, muss man nur einen Knotenpunkt jeder Kante betrachten: Ist ${}u_{i}\in A$, dann ist ${}v_{i}\in B$ und umgekehrt. Also entspricht jede Zerlegung einer Verteilung von ${}\{u_{1},\dots ,u_{m}\}$ auf ${}A$ und ${}B$. Da jedes ${}u_{i}$ entweder in ${}A$ oder ${}B$ sein kann, gibt es insgesamt ${}2^{m}$ Verteilungen. Die Anzahl der bipartiten Zerlegungen ist also ${}2^{m}/2=2^{m-1}$, da die Reihenfolge von ${}A$ und ${}B$ keine Rolle spielt.

Offensichtlich besitz der Graph nur eine optimale Paarung, die alle ${}m$ Kanten enthält.

 

Aufgabe

Es sei ${}P$ eine Paarung in einem Graphen ${}G$. Zeige, dass ${}P$ genau dann perfekt (maximal, optimal) ist, wenn dies für die Einschränkungen von ${}P$ auf jede Zusammenhangskomponente von ${}G$ gilt.

Aufgabe

Zeige, dass in einem vollständigen Graphen jede maximale Paarung bereits optimal ist.

Kommentar:

In einem vollständigen Graphen ${}K_{n}$ sind je zwei Knotenpunkte miteinander durch eine Kante verbunden. Eine Paarung ${}P$ in ${}K_{n}$, die mindestens zwei Knotenpunkte ${}u,v$ von ${}K_{n}$ nicht abdeckt, ist somit nicht maximal, da ${}P\cup \{u,v\}$ wieder eine Paarung in ${}K_{n}$ ist. Dies bedeutet, dass jede maximale Paarung in ${}K_{n}$ mindestens ${}n-1$ Knotenpunkte abdecken muss (oder genauer: jede maximale Paarung in ${}K_{n}$ abdeckt genau ${}2\lfloor n/2\rfloor$ Knotenpunkte und enthält genau ${}\lfloor n/2\rfloor$ Kanten). Daher muss jede maximale Paarung optimal sein.

 

Aufgabe

Bei einem Fußballspiel auf dem Bolzplatz hat Mannschaft ${}\{A,B,C,D,E\}$ gegen die Mannschaft ${}\{R,S,T,U,V\}$ gespielt. Beim anschließenden Grillen überlegen sich die Spieler der ersten Mannschaft, mit welchen Spielern sie während des Spiels aneinander geraten sind, und kommen zu folgendem Ergebnis.

	${}A$	${}B$	${}C$	${}D$	${}E$
	${}R,T$	${}S,U$	${}V$	${}V,S$	${}U,T$

Kann es sein, dass es im Spiel eine Situation gab, in der gleichzeitig jeder Spieler mit einem gegnerischen Spieler aneinander geriet? Falls ja, wer geriet mit wem aneinander?

Aufgabe

Bei einem Fußballspiel auf dem Bolzplatz hat Mannschaft ${}\{A,B,C,D,E\}$ gegen die Mannschaft ${}\{R,S,T,U,V\}$ gespielt. Beim anschließenden Grillen überlegen sich die Spieler der ersten Mannschaft, mit welchen Spielern sie während des Spiels aneinander geraten sind, und kommen zu folgendem Ergebnis.

	${}A$	${}B$	${}C$	${}D$	${}E$
	${}R,S,T,U,V$	${}S,U$	${}S,V$	${}S,V$	${}S,V,U$

Kann es sein, dass es im Spiel eine Situation gab, in der gleichzeitig jeder Spieler mit einem gegnerischen Spieler aneinander geriet? Falls ja, wer geriet mit wem aneinander?

Aufgabe *

Es sei ${}G$ ein Graph und ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus in einen bipartiten Graphen ${}H$. Zeige, dass ${}G$ ebenfalls bipartit ist.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Zeige, dass der Spielzuggraph zum Springer beim Schach bipartit ist.

Aufgabe (2 Punkte)

Es sei ${}K_{r,s}$ der vollständige bipartite Graph. Wie viele optimale Paarungen gibt es in ihm?

Aufgabe (3 Punkte)

Bestimme die Anzahl der perfekten Paarungen im dreidimensionalen Würfelgraphen.

Aufgabe (4 (2+2) Punkte)

Es sei ${}G$ ein Rundgang mit ${}n$ Knoten.

1. Erstelle eine Formel für die Paarungszahl von ${}G$.
2. Erstelle eine Formel für minimale Kantenanzahl in einer maximalen Paarung von ${}G$.

Aufgabe (4 Punkte)

Zeige, dass für einen Graphen ${}G=(V,E)$ folgende Eigenschaften äquivalent sind.

1. Es gibt unter allen (durch Inklusion geordneten) Paarungen eine größte Paarung.
2. ${}G$ ist selbst eine Paarung
3. Alle Wege in ${}G$ haben die Länge ${}0$ oder ${}1$.
4. Die Zusammenhangskomponenten sind (leer oder) ein- oder zweielementig.

Aufgabe (2 Punkte)

Prof. Knopfloch, Dr. Eisenbeis und Vorli machen wieder Urlaub. In der Ferienwohnung sind die Töpfe ${}\{a,b,c,d,e\}$ und die Deckel ${}\{1,2,3,4,5,6\}$ durcheinandergeraten. Eine systematische Durchsicht ergibt, dass zu den Töpfen die folgenden Deckel passen.

	${}a$	${}b$	${}c$	${}d$	${}e$
	${}3,4$	${}5$	${}1,2,3$	${}4,6$	${}1,3,6$

Kann man eine Paarung finden, die jeden Topf abdeckt? Falls ja, wie sieht sie aus? Wie sieht es aus, wenn Deckel ${}2$ als Napf für Vorli verwendet wird?