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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

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 .


Aufgabe

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 .


Aufgabe

Fish graph.svg

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.


Aufgabe

Es sei ein zusammenhängender Graph mit Durchmesser . Zeige, dass es in einen aufspannenden Baum mit Durchmesser gibt.


Aufgabe

Es sei der vollständige Graph mit Knoten. Bestimme die Anzahl der linearen aufspannenden Bäume in .


Aufgabe

Zeige, dass die Potenzmenge zu einer Menge ein Matroid ist.


Aufgabe

Es sei eine Menge und . Es sei die Menge aller Teilmengen von , die höchstens Elemente enthalten. Zeige, dass ein Matroid ist.


Aufgabe

Es sei die Familie der folgenden Vektoren im .

Bestimme das Matroid, das durch die lineare Unabhängigkeit von Teilfamilien gegeben ist.


Aufgabe

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.


Aufgabe

Es sei ein Rundgang mit Knotenpunkten. Bestimme die Anzahl der Spannbäume von mit und ohne Lemma 18.12.


Aufgabe

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.


Aufgabe

Antenna graph.svg

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


Aufgabe

Bestimme die Anzahl der aufspannenden Bäume des dreidimensionalen Würfelgraphen.




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Milano - mappa rete metropolitana (schematica).svg

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)

2-edge connected graph.svg

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)