Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 20
- Übungsaufgaben
Es sei ein zusammenhängender bipartiter Graph. Zeige, dass es nur eine (bis auf die Rolle der Teile) bipartite Zerlegung gibt.
Zeige, dass ein Untergraph eines bipartiten Graphen wieder bipartit ist.
Zeige, dass ein Graph genau dann bipartit ist, wenn jede Zusammenhangskomponente davon bipartit ist.
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?
Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem -Brett wie abgebildet.
- Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.
- Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.
Wir betrachten den Spielzuggraphen zum Turm beim Schach auf einen -Brett.
- Zeige, dass dies bei bipartit ist.
- Zeige, dass dies bei nicht bipartit ist.
Es sei ein Graph, der eine disjunkte Vereinigung von Kanten sei. Auf wie viele Arten kann man als bipartiten Graphen auffassen? Wie viele optimale Paarungen gibt es?
Kommentar:
Sei die disjunkte Kanten von . Zu bestimmen ist die Anzahl der bipartiten Zerlegungen
Man beachte, dass bei einer solchen Zerlegung die Reihenfolge von und keine Rolle spielt, d.h. ie Zerlegungen und werden als gleich angesehen.
Um eine Zerlegung zu finden, muss man nur einen Knotenpunkt jeder Kante betrachten: Ist , dann ist und umgekehrt. Also entspricht jede Zerlegung einer Verteilung von auf und . Da jedes entweder in oder sein kann, gibt es insgesamt Verteilungen. Die Anzahl der bipartiten Zerlegungen ist also , da die Reihenfolge von und keine Rolle spielt.
Offensichtlich besitz der Graph nur eine optimale Paarung, die alle Kanten enthält.
Zeige, dass in einem vollständigen Graphen jede maximale Paarung bereits optimal ist.
Kommentar:
In einem vollständigen Graphen sind je zwei Knotenpunkte miteinander durch eine Kante verbunden. Eine Paarung in , die mindestens zwei Knotenpunkte von nicht abdeckt, ist somit nicht maximal, da wieder eine Paarung in ist. Dies bedeutet, dass jede maximale Paarung in mindestens Knotenpunkte abdecken muss (oder genauer: jede maximale Paarung in abdeckt genau Knotenpunkte und enthält genau Kanten). Daher muss jede maximale Paarung optimal sein.
Bei einem Fußballspiel auf dem Bolzplatz hat Mannschaft gegen die Mannschaft 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.
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?
Bei einem Fußballspiel auf dem Bolzplatz hat Mannschaft gegen die Mannschaft 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.
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?
Es sei ein Graph und ein Graphhomomorphismus in einen bipartiten Graphen . Zeige, dass ebenfalls bipartit ist.
- Aufgaben zum Abgeben
Aufgabe (2 Punkte)
Zeige, dass der Spielzuggraph zum Springer beim Schach bipartit ist.
Aufgabe (2 Punkte)
Es sei 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 ein Rundgang mit Knoten.
- Erstelle eine Formel für die Paarungszahl von .
- Erstelle eine Formel für minimale Kantenanzahl in einer maximalen Paarung von .
Aufgabe (4 Punkte)
Aufgabe (2 Punkte)
Prof. Knopfloch, Dr. Eisenbeis und Vorli machen wieder Urlaub. In der Ferienwohnung sind die Töpfe und die Deckel durcheinandergeraten. Eine systematische Durchsicht ergibt, dass zu den Töpfen die folgenden Deckel passen.
Kann man eine Paarung finden, die jeden Topf abdeckt? Falls ja, wie sieht sie aus? Wie sieht es aus, wenn Deckel als Napf für Vorli verwendet wird?
<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> |
---|