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

Zuerst war sie kurz etwas beleidigt über ihre unvorteilhaften Startbedingungen.

Graphen und Matrizen

Definition

Zu einem Graphen ${}G=(V,E)$ versteht man unter der Adjazenzmatrix diejenige ${}V\times V$- Matrix, deren Einträge durch

${}a_{u,v}={\begin{cases}1,\,{\text{falls }}\{u,v\}\in E,\\0\,{\text{ sonst}},\end{cases}}\,$

gegeben sind.

Die Adjazenzmatrix ist eine quadratische Matrix, und zwar eine ${}V\times V$-Matrix. Es ist sinnvoll, hier Matrizen zu beliebigen endlichen Indexmengen zuzulassen. Wenn man allerdings die Matrix tabellarisch aufschreiben möchte, so muss man die Indexmenge (also die Knotenmenge) mit ${}1$ bis ${}n$ durchnummerieren und erhält dann eine ${}n\times n$-Matrix. Wie bei jeder quadratischen Matrix kann man von der Adjazenzmatrix ihre Determinante, ihr charakteristisches Polynom, ihre Eigenwerte bestimmen, man kann ihre Potenzen ausrechnen, u.s.w., und sich überlegen, was diese Strukturen der linearen Algebra für den Ausgangsgraphen bedeuten.

Beispiel

Zum vollständigen Graphen ${}K_{n}$ ist die Adjazenzmatrix gleich

${\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}}.$

Beispiel

Zu einem kantenfreien Graphen ist die Adjazenzmatrix die Nullmatrix.

Beispiel

Zum vollständigen bipartiten Graphen ${}K_{r,s}$ ist die Adjazenzmatrix eine Blockmatrix der Form

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

wobei die Blöcke aber nicht quadratisch sein müssen.

Lemma

Die Adjazenzmatrix ${}A$ eines Graphen ${}G=(V,E)$ besitzt die folgenden Eigenschaften.

1. Für Knotenpunkte ${}u,v\in V$ ist

   ${}{e_{u}^{\text{tr}}}Ae_{v}={\begin{cases}1,{\text{wenn }}\{u,v\}\in E\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

2. ${}A$ ist symmetrisch.
3. Die Diagonaleinträge von ${}A$ sind ${}0$.
4. Der Knotengrad zum Punkt ${}v\in V$ ist die Summe der Einträge der ${}v$-ten Zeile (oder Spalte) von ${}A$.

Beweis

Diese Aussagen folgen alle unmittelbar aus der Definition der Adjazenzmatrix und dem Matrizenkalkül.

$\Box$

In einem Graphen gibt es zwischen zwei Knotenpunkten ${}u$ und ${}v$ im Allgemeinen mehrere Wege einer vorgegebenen Länge ${}\ell$. Deren Anzahl kann man mit Hilfe der Potenzen der Adjazenzmatrix berechnen.

Lemma

Es sei ${}G=(V,E)$ ein Graph mit zugehöriger Adjazenzmatrix ${}A$.

Dann ist die Anzahl der Wege von ${}u$ nach ${}v$ der Länge ${}\ell$ gleich dem Eintrag an der Stelle ${}(u,v)$ zur Matrixpotenz ${}A^{\ell }$.

Beweis

Wir beweisen die Aussage durch Induktion über ${}\ell$, wobei der Induktionsanfang für ${}\ell =1$ unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge ${}1$ sind (bei ${}\ell =0$ stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge ${}0$ gibt und die ${}0$-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge ${}\ell +1$ von ${}u$ nach ${}v$ startet mit einer Kante ${}\{u,w\}$ gefolgt von einem Weg von ${}w$ nach ${}v$ der Länge ${}\ell$. Es gilt also unter Verwendung der Induktionsvoraussetzung

${}{\begin{aligned}{\#\left({\text{ Weg von }}u{\text{ nach }}v{\text{ der Länge }}\ell +1\}\right)}&=\sum _{\{u,w\}\in E}{\#\left({\text{ Weg von }}w{\text{ nach }}v{\text{ der Länge }}\ell \}\right)}\\&=\sum _{\{u,w\}\in E}{\left(A^{\ell }\right)}_{(w,v)}\\&=\sum _{w\in V}A_{(u,w)}{\left(A^{\ell }\right)}_{(w,v)}\\&={\left(A\cdot A^{\ell }\right)}_{(u,v)}\\&={\left(A^{\ell +1}\right)}_{(u,v)}\end{aligned}}$

$\Box$

Es gibt auch naheliegende Varianten für Adjazenzmatrizen einschließlich der vorstehenden Aussage für gerichtete Graphen und für Multigraphen.

Beispiel

Wir betrachten den Rundgang zur Vertexmenge ${}a,b,c,d,e$ in dieser Reihenfolge. Die Adjazenzmatrix ist

${}A={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}\,.$

Die Wege der Länge ${}2$ kann man direkt so bestimmen: Es gibt zwei Wege von jedem Punkt zu sich selbst, nämlich zu den beiden Nachbarn und dann zurück. Zum Nachbarn gibt es keinen Weg der Länge ${}2$, zum übernächsten Punkt gibt es jeweils einen Weg der Länge ${}2$. Entsprechend ist

${}{\begin{aligned}A^{2}&={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}{\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}\\&={\begin{pmatrix}2&0&1&1&0\\0&2&0&1&1\\1&0&2&0&1\\1&1&0&2&0\\0&1&1&0&2\end{pmatrix}}.\end{aligned}}$

Ab der Länge ${}3$ muss man bei der kombinatorischen Abzählung berücksichtigen, dass Wege mit unterschiedlichem Umlaufsinn sich überlagern und das gleiche Ergebnis haben können. Mit der Matrixregel aus Lemma 19.6 muss man einfach nur multiplizieren, es ist

${}{\begin{aligned}A^{3}&={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}{\begin{pmatrix}2&0&1&1&0\\0&2&0&1&1\\1&0&2&0&1\\1&1&0&2&0\\0&1&1&0&2\end{pmatrix}}\\&={\begin{pmatrix}0&3&1&1&3\\3&0&3&1&1\\1&3&0&3&1\\1&1&3&0&3\\3&1&1&3&0\end{pmatrix}}.\end{aligned}}$

Das charakteristische Polynom zu einem Graphen

Definition

Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von ${}G$.

Entsprechende nennt man die Eigenwerte (Eigenvektoren, Eigenräume u.s.w.) der Adjazenzmatrix auch die Eigenwerte des Graphen.

Beispiel

Das charakteristische Polynom zur Adjazenzmatrix des vollständigen Graphen ${}K_{n}$ ist nach Definition die Determinante von

${\begin{pmatrix}x&-1&\ldots &-1&-1\\-1&x&-1&\ldots &-1\\\vdots &\ddots &\ddots &\ddots &\vdots \\-1&\ldots &-1&x&-1\\-1&-1&\ldots &-1&x\end{pmatrix}}.$

In diesem Fall ist es einfacher, direkt die Eigenräume zu berechnen. Für ${}x=-1$ steht hier überall ${}-1$ und der Kern besitzt die Basis

${\begin{pmatrix}1\\-1\\0\\\vdots \\0\\0\end{pmatrix}},\,{\begin{pmatrix}0\\1\\-1\\\vdots \\0\\0\end{pmatrix}},\ldots ,{\begin{pmatrix}0\\0\\0\\\vdots \\1\\-1\end{pmatrix}}.$

Somit ist ${}-1$ ein Eigenwert mit geometrischer Vielfachheit ${}n-1$. Für ${}x=n-1$ ergibt sich die Matrix

${\begin{pmatrix}n-1&-1&\ldots &-1&-1\\-1&n-1&-1&\ldots &-1\\\vdots &\ddots &\ddots &\ddots &\vdots \\-1&\ldots &-1&n-1&-1\\-1&-1&\ldots &-1&n-1\end{pmatrix}}$

und der Kern davon ist

$\mathbb {R} {\begin{pmatrix}1\\1\\\vdots \\1\\1\end{pmatrix}}.$

Somit ist ${}n-1$ ein Eigenwert mit geometrischer Vielfachheit ${}1$. Da die Summe der geometrischen Vielfachheiten bereits die Dimension ${}n$ ist, handelt es sich jeweils auch um die algebraischen Vielfachheiten und das charakteristische Polynom ist

$(x+1)^{n-1}(x-n+1).$

Bemerkung  

Für einen Graphen liegt folgende Interpretation nahe: Ein Knotenpunkt ist der mögliche Aufenthaltsort eines Gerüchtes, einer Information, eines Virus. Wenn eine Kante zwischen zwei Punkten ${}u$ und ${}v$ besteht, so bedeutet dies, dass in einem bestimmten Zeitabschnitt das Gerücht von ${}u$ nach ${}v$ hinüber- oder zurückwechselt. Die Gesamtverteilung des Gerüchtes ist ein Spaltenvektor

${\left(c_{v}\right)}_{v\in V}$

der für jeden Punkt angibt, wie stark im Ort ${}v$ das Gerücht verbreitet ist. Der Gesamtübergang in dem erwähnten Zeitintervall wird dann durch Multiplikation der Adjazenzmatrix ${}A$ mit der Gesamtverteilung beschrieben. Wenn beispielsweise zu Beginn das Gerücht nur in einem Knotenpunkt ${}u$ mit der Stärke ${}1$ präsent ist, so ist es nach dem Zeitintervall in den zu ${}u$ benachbarten Knoten jeweils mit der Stärke ${}1$ präsent, und dies ist gerade der ${}u$-te Spaltenvektor der Adjazenzmatrix (da wir ohne Schleifen arbeiten, vergisst man in diesem Modell das Gerücht, indem man es weitererzählt, es liegt eine gedächtnislose Weitergabe vor; man kann die Weitergabe auch abschwächen, wenn man die Adjazenzmatrix mit einem Faktor skaliert). Die Gerüchtverteilung nach ${}\ell$ Durchläufen zur Anfangsgerüchtverteilung wird dann durch ${}A^{\ell }(c_{v})$ beschrieben. Eine Eigenverteilung, also ein Eigenvektor der Adjazenzmatrix, ist durch die Eigenschaft gekennzeichnet, dass sich bei einem Durchlauf ein bestimmtes Vielfaches dieser Verteilung selbst ergibt. Der gemeinsame Faktor, der an jeder Stelle den Übergang beschreibt, ist der Eigenwert.

Im vollständigen Graphen gibt es nach Beispiel 19.9 die beiden Eigenwerte ${}n-1$ und ${}-1$. Die Gerüchtverteilung ${}{\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}$ (an jeder Stelle wird mit der gleichen Intensität ${}1$ das Gerücht geglaubt) wird durch einen Weitergabevorgang in die Gerüchtverteilung ${}{\begin{pmatrix}n-1\\n-1\\\vdots \\n-1\end{pmatrix}}$ überführt, jeder hört das Gerücht ${}n-1$ mal. Die Gerüchtverteilung ${}{\begin{pmatrix}1\\-1\\0\\\vdots \\0\end{pmatrix}}$, wobei ${}-1$ so zu verstehen ist, dass das Gerücht an dieser Stelle mit der gleichen Intensität nicht geglaubt wird, wird durch den Vorgang in die Verteilung ${}{\begin{pmatrix}-1\\1\\0\\\vdots \\0\end{pmatrix}}$ überführt. Die beiden nichtneutralen Personen übernehmen wechselseitig ihre Einstellung zum Gerücht und alle anderen Personen hören es einmal in positiver und einmal in negativer Weise, was sich aufhebt.

Definition

Es sei ${}G=(V,E)$ ein Graph. Unter der Inzidenzmatrix zu ${}G$ verstehen wir die ${}V\times E$- Matrix, deren Einträge durch

${}b_{v,e}:={\begin{cases}1,\,{\text{falls }}v\in e,\\0{\text{ sonst}}\,,\end{cases}}\,$

gegeben sind.

Definition

Es sei ${}G=(V,E)$ ein Graph. Unter der Gradmatrix zu ${}G$ verstehen wir die ${}V\times V$- Diagonalmatrix, deren Diagonaleintrag an der Stelle ${}(v,v)$ durch den Grad im Knotenpunkt ${}v$ gegeben ist.

Laplace-Matrix und Spannbäume

Für einen Multigraphen definieren wir die Adjazenzmatrix und die Gradmatrix entsprechend wie im einfachen Fall.

Definition

Zu einem Multigraphen ${}G$ versteht man unter der Laplace-Matrix ${}L$ die Differenz

${}L=D-A\,$

aus Gradmatrix ${}D$ und Adjazenzmatrix ${}A$.

Mit Hilfe der Laplace-Matrix kann man die Anzahl von Spannbäumen berechnen, wozu wir zuerst ein Beispiel geben.

Beispiel

Wir betrachten den Diamantgraphen mit den Knoten ${}a,b,c,d$, bei dem ${}\{1,4\}$ die einzige Nichtkante ist. Die Adjazenzmatrix ist ${}A={\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{pmatrix}}$, die Gradmatrix ist ${}D={\begin{pmatrix}2&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&2\end{pmatrix}}$ und die Laplace-Matrix ist

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

Die Determinante der Streichungsmatrix zur ersten Zeile und ersten Spalte ist

${}\det {\begin{pmatrix}3&-1&-1\\-1&3&-1\\-1&-1&2\end{pmatrix}}=8\,.$

Diese Zahl stimmt mit der Anzahl der Spannbäume des Diamantgraphen, die in Beispiel 18.13 berechnet wurde, überein.

Der folgende Satz heißt Satz von Kirchhoff und formuliert einen direkten Zusammenhang zwischen der Anzahl der Spannbäume und der Determinante von Streichungsmatrizen der Laplace-Matrix.

Satz

Es sei ${}G$ ein Multigraph und sei ${}L$ die Laplace-Matrix zu ${}G$. Es sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von ${}G$ gleich der Determinante von ${}L'$.

Beweis

Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist ${}1$. Bei zwei Knoten und ${}m$ verbindenden Kanten gibt es ${}m$ Spannbäume. Die Adjazenzmatrix ist ${}{\begin{pmatrix}0&m\\m&0\end{pmatrix}}$ und die Gradmatrix ist ${}{\begin{pmatrix}m&0\\0&m\end{pmatrix}}$. Daher ist die Laplace-Matrix gleich ${}{\begin{pmatrix}m&-m\\-m&m\end{pmatrix}}$. Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante ${}m$. Es sei nun die Aussage für alle Multigraphen mit höchstens ${}n-1$ Knoten bewiesen, und sei eine Multigraph ${}G$ mit ${}n$ Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl ${}m$ der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon ist die Nullmatrix mit Determinante ${}0$. Es sei also die Aussage auch für alle Graphen mit ${}n$ Knoten und mit weniger als ${}m$ Kanten bewiesen, und ${}G$ habe ${}n$ Knoten und ${}m$ Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen ${}1$ und ${}2$ kontrahiert, wovon es ${}a_{12}\geq 1$ gibt. Die Laplace-Matrix von ${}G$ sei

${\begin{pmatrix}d_{1}&-a_{12}&-a_{13}&\ldots &-a_{1n}\\-a_{12}&d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Laplace-Matrix von ${}G\setminus \{e\}$ ist

${\begin{pmatrix}d_{1}-1&-a_{12}+1&-a_{13}&\ldots &-a_{1n}\\-a_{12}+1&d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

und die Laplace-Matrix zur Kontraktion ${}G/e$ ist die ${}(n-1)\times (n-1)$-Matrix

${\begin{pmatrix}d_{1}+d_{2}-2a_{12}&-a_{13}-a_{23}&\ldots &-a_{1n}-a_{2n}\\-a_{13}-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{1n}-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach

${\begin{pmatrix}d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}},$

${\begin{pmatrix}d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

${\begin{pmatrix}d_{3}&\ldots &-a_{3n}\\\vdots &\ddots &\vdots \\-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Entwicklung nach der ersten Spalte (für die beiden ersten Matrizen) zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit Lemma 18.12 aus den beiden Induktionsvoraussetzungen.

$\Box$

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)