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

Übungsaufgaben

Aufgabe

Erstelle die Adjazenzmatrix zum Sterngraphen mit ${}4$ Blättern.

Aufgabe

Skizziere den Graphen zur Adjazenzmatrix

${\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&1\\0&1&1&0\end{pmatrix}}.$

Aufgabe

Bestimme die ${}\ell$-te Potenz zur Adjazenzmatrix eines vollständigen Graphen mit ${}n$ Knotenpunkten.

Kommentar:

Zu bestimmen ist die Matrixpotenz ${}A^{\ell }$, wobei

$A={\begin{pmatrix}0&1&\ldots &1&1\\1&0&1&\ldots &1\\\vdots &\ddots &\ddots &\ddots &\vdots \\1&\ldots &1&0&1\\1&1&\ldots &1&0\end{pmatrix}}$

die Adjazenzmatrix des vollständigen Graphen ${}K_{n}$ 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 ${}A$ schon berechnet. Aus der linearen Algebra weiß man, dass ${}A$ diagonalisierbar ist und es gilt

$B^{-1}AB={\begin{pmatrix}-1&0&\ldots &0&0\\0&-1&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&-1&0\\0&0&\ldots &0&n-1\end{pmatrix}},$

wobei

$B={\begin{pmatrix}1&0&\ldots &0&1\\-1&1&0&\ldots &1\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &-1&1&1\\0&0&\ldots &-1&1\end{pmatrix}}$

die Matrix ist, deren Spalten aus Eigenvektoren von ${}A$ bestehen. Es ist

$B^{-1}A^{\ell }B=(B^{-1}AB)^{\ell }={\begin{pmatrix}(-1)^{\ell }&0&\ldots &0&0\\0&(-1)^{\ell }&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&(-1)^{\ell }&0\\0&0&\ldots &0&(n-1)^{\ell }\end{pmatrix}}.$

Somit gilt

$A^{\ell }=B{\begin{pmatrix}(-1)^{\ell }&0&\ldots &0&0\\0&(-1)^{\ell }&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&(-1)^{\ell }&0\\0&0&\ldots &0&(n-1)^{\ell }\end{pmatrix}}B^{-1}.$

Es bleibt also, die inverse Matrix ${}B^{-1}$ zu bestimmen. Dies kann man beispielsweise mit Verfahren 12.11 (Lineare Algebra (Osnabrück 2017-2018)) durchführen.

 

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.

Kommentar:

Sei ${}P_{n}(x)$ das charakteristische Polynom eines linearen Graphen mit ${}n$ Knotenpunkten. Bei Aufgaben dieses Typs ist es immer hilfreich, ${}P_{n}(x)$ für kleines ${}n$ zu berechnen. Man sieht leicht, dass ${}P_{1}(x)=x$ und ${}P_{2}(x)=x^{2}-1$. Nach Definition ist ${}P_{3}(x)$ die Determinante von

${\begin{pmatrix}x&-1&0\\-1&x&-1\\0&-1&x\end{pmatrix}}.$

Entwicklung nach der ersten Spalte ergibt sich ${}P_{3}(x)=xP_{2}(x)-P_{1}(x)$. Ebenso erhält man die gleiche Formel für ${}n\geq 3$, d.h. ${}P_{n}(x)=xP_{n-1}(x)-P_{n-2}(x)$. Man kann also ${}P_{n}(x)$ rekursiv berechnen. Es ist aber nicht einfach, eine explizite Formel für ${}P_{n}(x)$ abzuleiten oder die Nullstellen von ${}P_{n}(x)$ zu berechnen. Eine Idee dafür ist es, die Tschebyschow-Polynome zweiter Art zu verwenden, die wie folgt definiert sind:

$U_{1}(x)=2x,\quad U_{2}(x)=4x^{2}-1,\quad U_{n}(x)=2xU_{n-1}(x)-U_{n-2}(x),\ n\geq 3.$

Offensichtlich gilt ${}P_{n}(x)=U_{n}(x/2)$ für alle ${}n$. Es ist bekannt, dass

$U_{n}(x)={\frac {(x+{\sqrt {x^{2}-1}})^{n+1}-(x-{\sqrt {x^{2}-1}})^{n+1}}{2{\sqrt {x^{2}-1}}}}$

und die Nullstellen von ${}U_{n}(x)$ sind

$x_{k}=\cos {\Big (}{\frac {k\pi }{n+1}}{\Big )},\ k=1,\dots ,n.$

 

Aufgabe

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

Aufgabe

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

Aufgabe

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

Kommentar:

Die Laplace-Matrix des Graphen ist

$L={\begin{pmatrix}2&0&0&0&0&0\\0&2&0&0&0&0\\0&0&4&0&0&0\\0&0&0&2&0&0\\0&0&0&0&2&0\\0&0&0&0&0&2\end{pmatrix}}-{\begin{pmatrix}0&1&1&0&0&0\\1&0&1&0&0&0\\1&1&0&1&0&1\\0&0&1&0&1&0\\0&0&0&1&0&1\\0&0&1&0&1&0\end{pmatrix}}={\begin{pmatrix}2&-1&1&0&0&0\\-1&2&-1&0&0&0\\-1&-1&4&-1&0&-1\\0&0&-1&2&-1&0\\0&0&0&-1&2&-1\\0&0&-1&0&-1&2\end{pmatrix}}.$

Sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes. Natürlich sollte man hier die dritte Zeile und dritte Spalte streichen. Nach Satz 19.15 ist ${}\det L'=12$ 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 ${}3\cdot 4=12$ Spannbäume.

 

Aufgabe

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 ${}4$ Punkten mit Hilfe des Satzes von Kirchhoff.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}G=(V,E)$ ein Graph mit zugehöriger Adjazenzmatrix ${}A$. Es sei ${}\pi \colon V\rightarrow V$ eine Permutation der Knotenmenge ${}V$ in sich mit der zugehörigen Permutationsmatrix ${}M_{\pi }$. Zeige, dass ${}\pi$ genau dann ein Automorphismus ist, wenn

${}A=M_{\pi }AM_{\pi }^{-1}\,$

gilt.

Aufgabe (3 Punkte)

Es sei ${}G=(V,E)$ ein Graph und ${}A$ die Adjazenzmatrix, ${}D$ die Gradmatrix und ${}I$ die Inzidenzmatrix von ${}G$. Zeige, dass der Zusammenhang

${}I\cdot {I^{\text{tr}}}=A+D\,$

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.