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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Zuerst war sie kurz etwas beleidigt über ihre unvorteilhaften Startbedingungen.




Graphen und Matrizen
G1kevohuong.png

Definition  

Zu einem Graphen versteht man unter der Adjazenzmatrix diejenige -Matrix, deren Einträge durch

gegeben sind.

Die Adjazenzmatrix ist eine quadratische Matrix, und zwar eine -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 in diesem Fall die Knotenmenge mit bis durchnummerieren und erhält dann eine -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 ist die Adjazenzmatrix gleich



Beispiel  

Zu einem kantenfreien Graphen ist die Adjazenzmatrix die Nullmatrix.



Beispiel  

Zum vollständigen bipartiten Graphen ist die Adjazenzmatrix eine Blockmatrix der Form

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




Lemma  

Die Adjazenzmatrix eines Graphen besitzt die folgenden Eigenschaften.

  1. Für Knotenpunkte ist
  2. ist symmetrisch.
  3. Die Diagonaleinträge von sind .
  4. Der Knotengrad zum Punkt ist die Summe der Einträge der -ten Zeile (oder Spalte) von .

Beweis  

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

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



Lemma  

Es sei ein Graph mit zugehöriger Adjazenzmatrix .

Dann ist die Anzahl der Wege von nach der Länge gleich dem Eintrag an der Stelle zur Matrixpotenz .

Beweis  

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


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 in dieser Reihenfolge. Die Adjazenzmatrix ist

Die Wege der Länge 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 , zum übernächsten Punkt gibt es jeweils einen Weg der Länge . Entsprechend ist

Ab der Länge 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




Das charakteristische Polynom zu einem Graphen

Definition  

Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von .

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 ist nach Definition die Determinante von

In diesem Fall ist es einfacher, direkt die Eigenräume zu berechnen. Für steht hier überall und der Kern besitzt die Basis

Somit ist ein Eigenwert mit geometrischer Vielfachheit . Für ergibt sich die Matrix

und der Kern davon ist

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


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 und besteht, so bedeutet dies, dass in einem bestimmten Zeitabschnitt das Gerücht von nach hinüber- oder zurückwechselt. Die Gesamtverteilung des Gerüchtes ist ein Spaltenvektor

der für jeden Punkt angibt, wie stark im Ort das Gerücht verbreitet ist. Der Gesamtübergang in dem erwähnten Zeitintervall wird dann durch Multiplikation der Adjazenzmatrix mit der Gesamtverteilung beschrieben. Wenn beispielsweise zu Beginn das Gerücht nur in einem Knotenpunkt mit der Stärke präsent ist, so ist es nach dem Zeitintervall in den zu benachbarten Knoten jeweils mit der Stärke präsent, und dies ist gerade der -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 Durchläufen zur Anfangsgerüchtverteilung wird dann durch 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 und . Die Gerüchtverteilung (an jeder Stelle wird mit der gleichen Intensität das Gerücht geglaubt) wird durch einen Weitergabevorgang in die Gerüchtverteilung überführt, jeder hört das Gerücht mal. Die Gerüchtverteilung , wobei 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 ü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 ein Graph. Unter der Inzidenzmatrix zu verstehen wir die -Matrix, deren Einträge durch

gegeben sind.


Definition  

Es sei ein Graph. Unter der Gradmatrix zu verstehen wir die -Diagonalmatrix, deren Diagonaleintrag an der Stelle durch den Grad im Knotenpunkt 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 versteht man unter der Laplace-Matrix die Differenz

aus Gradmatrix und Adjazenzmatrix .

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


Beispiel  

Graph with all its spanning trees.svg

Wir betrachten den Diamantgraphen mit den Knoten , bei dem die einzige Nichtkante ist. Die Adjazenzmatrix ist , die Gradmatrix ist und die Laplace-Matrix ist

Die Determinante der Streichungsmatrix zur ersten Zeile und ersten Spalte ist

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 ein Multigraph und sei die Laplace-Matrix zu . Es sei die Streichungsmatrix von bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von gleich der Determinante von .

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 . Bei zwei Knoten und verbindenden Kanten gibt es Spannbäume. Die Adjazenzmatrix ist und die Gradmatrix ist . Daher ist die Laplace-Matrix gleich . Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante . Sei nun die Aussage für alle Multigraphen mit höchstens Knoten bewiesen, und sei eine Multigraph mit Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl 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 . Sei also die Aussage auch für alle Graphen mit Knoten und mit weniger als Kanten bewiesen, und habe Knoten und Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen und kontrahiert, wovon es gibt. Die Laplace-Matrix von sei

Die Laplace-Matrix von ist

und die Laplace-Matrix zur Kontraktion ist die -Matrix

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

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.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)