Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 18/kontrolle
- Übungsaufgaben
Wir betrachten den Spielzuggraphen zum Turm auf einem -Schachbrett.
- Bestimme die Anzahl der linearen Spannbäume von .
- Bestimme die Anzahl der Spannbäume von .
Wir betrachten den Spielzuggraphen zum Läufer auf einem -Schachbrett.
- Bestimme die Anzahl der linearen Spannbäume von .
- Bestimme die Anzahl der Spannbäume von .
Es sei ein Rundgang mit Knoten und ein Rundgang mit Knoten, . Es sei die Vereinigung der beiden Graphen an einem einzigen Punkt. Zeige, dass die Anzahl der aufspannenden Bäume von gleich ist.
Es sei ein zusammenhängender Graph mit Durchmesser . Zeige, dass es in einen aufspannenden Baum mit Durchmesser gibt.
Es sei der vollständige Graph mit Knoten. Bestimme die Anzahl der linearen aufspannenden Bäume in .
Kommentar:
Ein linearer aufspannender Baum ist einfach ein Untergraph von , der ein Pfad ist. Er muss alle Punkte genau einmal enthalten, es handelt sich also um ein vollständiges und eindeutiges Durchlaufen des Graphen. Da es keine Wiederholungen der Knoten geben darf, gibt es erst recht keine Wiederholungen von Kanten (es gibt auch das Konzept Eulerzug, das wir später behandeln werden).
Bei einen vollständigen Graphen kann man an einem beliebigen Punkt anfangen, und dann zu einem beliebigen Punkt mittels der Kante laufen, dann ...
Zeige, dass die Potenzmenge zu einer Menge ein Matroid ist.
Es sei eine Menge und . Es sei die Menge aller Teilmengen von , die höchstens Elemente enthalten. Zeige, dass ein Matroid ist.
Es sei die Familie der folgenden Vektoren im .
Bestimme das Matroid, das durch die lineare Unabhängigkeit von Teilfamilien gegeben ist.
Es sei ein zusammenhängender Graph. Zeige, dass für einen Untergraphen (also mit voller Vertexmenge) die folgenden Aussagen äquivalent sind.
- ist ein Baum.
- ist ein aufspannender Baum.
- ist maximal kreisfrei, d. h. sobald man eine Kante aus zu hinzutut, entsteht ein Kreis.
- ist minimal zusammenhängend, d. h. sobald man eine Kante herausnimmt, wird der Graph unzusammenhängend.
Kommentar:
Die Aussage sollte strukturell an die Aussage der linearen Algebra errinnern: Eine Familie von Vektoren ist genau dann eine Basis, wenn sie eine maximal linear unabhängig ist genau dann, wenn sie ein minimales Erzeugendensystem ist, siehe Satz 7.11 (Lineare Algebra (Osnabrück 2024-2025)). Die Analogie zwischen (aufspannenden) Bäumen bzw. Wälder zu (maximal) linear unabhängigen Vektorfamilien wird ja bereits durch den Matroidbegriff präzise gemacht. (1) und (2) sind trivialerweise äquivalent, da ja ein aufspannender Baum einfach ein Baum mit der vollen Knotenmenge ist, was vorausgesetzt wird. Von (2) nach (3). Es werde die Kante hinzugenommen. Es gibt aber bereits in einen verbindenden Weg von nach und durch die Hinzunahme entsteht ein mehrfacher Weg und ein Kreis. Dieses Argument wurde schon im Beweis zu Satz 17.22 verwendet.
Von (3) nach (1). Es ist zu zeigen, dass unter der angegebenen Bedingung zusammenhängend ist. Wenn nicht zusammenhängend ist, so gebe es keinen Weg in von nach . Es gibt in nach der Obervoraussetzung einen Weg von nach . Zumindest eine Kante davon gehört nicht zu , nach Umbenennung sei das die Kante . Wenn man aber diese Kante zu hinzunimmt, entsteht ein größerer kreisfreier Untergraph.
Von (1) nach (4) folgt aus Satz 17.22, wenn man die Kante herausnimmt, so zerstört man den eindeutigen wiederholungsfreien Verbindungsweg von nach .
Von (4) nach (1) folgt ebenfalls aus Satz 17.22.
Es sei ein Rundgang mit Knotenpunkten. Bestimme die Anzahl der Spannbäume von mit und ohne Lemma 18.12.
Es sei ein Graph. Zeige mit und ohne Lemma 18.12, dass die Anzahl der Spannbäume von mit der Anzahl der Spannbäume des Graphen übereinstimmt, der aus entsteht, indem man alle Blätter zusammen mit den zugehörigen Kanten entfernt.
Kommentar:
Da man die Blätter sukzessive entfernen kann, muss man lediglich zeigen, dass die Anzahl der aufspannenden Bäume gleich bliebt, wenn man ein Blatt zusammen mit der anliegenden Kanten entfernt. Sei also ein Blatt mit zugehöriger Kante .
Jeder aufspannende Baum muss das Blatt enthalten, und die einzige Möglichkeit ist über die einzige Kante . Wenn man das Blatt und diese Kante entfernt, so erhält man nach Lemma 17.21 wieder einen (Spann)-Baum. Wenn umgekehrt ein aufspannender Baum von des reduzierten Graphen vorliegt, so wird dieser durch Hinzunahme des Blattes und der Kante zu einem Spannbaum des Ausgangsgraphen. Es gibt also eine natürliche Bijektion zwischen den aufspannenden Bäumen des Graphen mit oder ohne dem Blatt.
Mit Lemma 18.12 geht das Argument so: Der Graph (also mit dem Knoten , aber ohne die verbindende Kante) ist nicht zusammenhängend und hat daher keinen Spannbaum. Damit stimmt die Anzahl der Spannbäume von mit der Anzahl der Spannbäume von überein. Das Argument von oben ist aber andererseits auch der wesentliche Punkt im Beweis des Lemmas.
Bestimme rekursiv die Anzahl der aufspannenden Bäume des abgebildeten Graphen.
Bestimme die Anzahl der aufspannenden Bäume des dreidimensionalen Würfelgraphen.
- Aufgaben zum Abgeben
Aufgabe (2 Punkte)Referenznummer erstellen
.svg)
Man beschreibe einen Spannbaum für die Mailänder Metro, indem man gewisse Kanten herausnimmt.
Aufgabe (3 Punkte)Referenznummer erstellen
Auf der Knotenmenge sei ein linearer Multigraph gegeben, wobei , , die Anzahl der Kanten zwischen und sei (und sonst gebe es keine Kanten). Zeige, dass die Anzahl der aufspannenden Bäume von gleich ist.
Aufgabe (5 Punkte)Referenznummer erstellen
Bestimme rekursiv die Anzahl der aufspannenden Bäume des vollständigen Graphen mit Knotenpunkten.
Aufgabe (3 Punkte)Referenznummer erstellen
Bestimme rekursiv die Anzahl der aufspannenden Bäume des abgebildeten Graphen.
Es sei ein Graph zusammen mit zwei vollen Untergraphen mit (auf der Vertexmenge)
und derart, dass alle Kanten von entweder zu oder zu gehören. Zeige, dass die Anzahl der aufspannenden Bäume von gleich dem Produkt der Anzahl der aufspannenden Bäume von und der Anzahl der aufspannenden Bäume von ist.