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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Erstelle die Adjazenzmatrix zum Sterngraphen mit Blättern.


Aufgabe

Skizziere den Graphen zur Adjazenzmatrix


Aufgabe

Bestimme die -te Potenz zur Adjazenzmatrix eines vollständigen Graphen mit Knotenpunkten.


Aufgabe *

Bestimme zu jedem Graphen mit drei Knotenpunkten das charakteristische Polynom und die Eigenwerte.


Aufgabe

Bestimme zu einem linearen Graphen das charakteristische Polynom und die Eigenwerte.


Aufgabe

In einem Sterngraphen mit Blättern sei zu Beginn ein Gerücht mit der Stärke im Zentrum platziert. Wie sieht die Gerüchteverteilung nach Weitergabevorgängen aus?


Aufgabe

Berechne in Beispiel 19.14 die Determinante zu allen Streichungsmatrizen der Laplace-Matrix.


Aufgabe

Fish graph.svg

Bestimme die Anzahl der Spannbäume des abgebildeten Graphen mit Hilfe von Satz 19.15.


Aufgabe

Identity graph2.svg

Bestimme die Anzahl der Spannbäume des abgebildeten Graphen mit Hilfe von Satz 19.15.


Aufgabe *

Bestimme die Anzahl der Spannbäume des vollständigen Graphen zu Punkten mit Hilfe des Satzes von Kirchhoff.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ein Graph mit zugehöriger Adjazenzmatrix . Es sei eine Permutation der Knotenmenge in sich mit der zugehörigen Permutationsmatrix . Zeige, dass genau dann ein Automorphismus ist, wenn

gilt.


Aufgabe (3 Punkte)

Es sei ein Graph und die Adjazenzmatrix, die Gradmatrix und die Inzidenzmatrix von . Zeige, dass der Zusammenhang

besteht.


Aufgabe (3 Punkte)

Bestimme zum Sterngraph mit drei Blättern das charakteristische Polynom und die Eigenwerte.


Aufgabe (4 Punkte)

Domino graph.svg

Bestimme die Anzahl der Spannbäume des abgebildeten Graphen mit Hilfe von Satz 19.15.


Aufgabe (5 Punkte)

Beweise Aufgabe 18.18 mit Satz 19.15.



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)