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



Übungsaufgaben

Wir betrachten den Spielzuggraphen zum Turm auf einem -Schachbrett.

  1. Bestimme die Anzahl der linearen Spannbäume von .
  2. Bestimme die Anzahl der Spannbäume von .



Wir betrachten den Spielzuggraphen zum Läufer auf einem -Schachbrett.

  1. Bestimme die Anzahl der linearen Spannbäume von .
  2. 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 .



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.

  1. ist ein Baum.
  2. ist ein aufspannender Baum.
  3. ist maximal kreisfrei, d. h. sobald man eine Kante aus zu hinzutut, entsteht ein Kreis.
  4. ist minimal zusammenhängend, d. h. sobald man eine Kante herausnimmt, wird der Graph unzusammenhängend.



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.



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)

Man beschreibe einen Spannbaum für die Mailänder Metro, indem man gewisse Kanten herausnimmt.



Aufgabe (3 Punkte)

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)

Bestimme rekursiv die Anzahl der aufspannenden Bäume des vollständigen Graphen mit Knotenpunkten.



Aufgabe (3 Punkte)

Bestimme rekursiv die Anzahl der aufspannenden Bäume des abgebildeten Graphen.



Aufgabe (5 Punkte)

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.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)