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.



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



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?



Zeige, dass ein Wald bipartit ist.



Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem -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.



Wir betrachten den Spielzuggraphen zum Turm beim Schach auf einen -Brett.

  1. Zeige, dass dies bei bipartit ist.
  2. Zeige, dass dies bei nicht bipartit ist.



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?



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?



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



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



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.

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



Aufgabe (4 Punkte)

Zeige, dass für einen Graphen folgende Eigenschaften äquivalent sind.

  1. Es gibt unter allen (durch Inklusion geordneten) Paarungen eine größte Paarung.
  2. ist selbst eine Paarung
  3. Alle Wege in haben die Länge oder .
  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 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) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)