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.
Kommentar:
Zu bestimmen ist die Matrixpotenz , wobei
die Adjazenzmatrix des vollständigen Graphen ist. Um eine (große) Potenz einer Matrix zu berechnen, besteht die erste Idee darin, die Matrix in eine Diagonalmatrix umzuwandeln. In Beispiel 19.9 wurden die Eigenwerte und Eigenvektoren von schon berechnet. Aus der linearen Algebra weiß man, dass diagonalisierbar ist und es gilt
wobei
die Matrix ist, deren Spalten aus Eigenvektoren von bestehen. Es ist
Somit gilt
Es bleibt also, die inverse Matrix zu bestimmen. Dies kann man beispielsweise mit Verfahren 12.11 (Lineare Algebra (Osnabrück 2017-2018)) durchführen.
Bestimme zu jedem Graphen mit drei Knotenpunkten das charakteristische Polynom und die Eigenwerte.
Bestimme zu einem linearen Graphen das charakteristische Polynom und die Eigenwerte.
Kommentar:
Sei das charakteristische Polynom eines linearen Graphen mit Knotenpunkten. Bei Aufgaben dieses Typs ist es immer hilfreich, für kleines zu berechnen. Man sieht leicht, dass und . Nach Definition ist die Determinante von
Entwicklung nach der ersten Spalte ergibt sich . Ebenso erhält man die gleiche Formel für , d.h. . Man kann also rekursiv berechnen. Es ist aber nicht einfach, eine explizite Formel für abzuleiten oder die Nullstellen von zu berechnen. Eine Idee dafür ist es, die Tschebyschow-Polynome zweiter Art zu verwenden, die wie folgt definiert sind:
Offensichtlich gilt für alle . Es ist bekannt, dass
und die Nullstellen von sind
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.
Kommentar:
Die Laplace-Matrix des Graphen ist
Sei die Streichungsmatrix von bezüglich eines Knotenpunktes. Natürlich sollte man hier die dritte Zeile und dritte Spalte streichen. Nach Satz 19.15 ist die Anzahl der Spannbäume des Graphen.
In dieser Aufgabe kann man auch die Anzahl der Spannbäume direkt bestimmen: Jeder Spannbaum wird aus dem Graphen erhalten, indem eine Kante des Dreiecks und eine Kante des Vierecks gelöscht werden. Es gibt also insgesamt Spannbäume.
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) | >> |
---|