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



Übungsaufgaben

Erstelle die Adjazenzmatrix zum Sterngraphen mit Blättern.



Skizziere den Graphen zur Adjazenzmatrix



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



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





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?



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



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



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



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)

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)