Graph/Adjazenzmatrix/Charakteristisches Polynom/Eigenräume/Textabschnitt

Aus Wikiversity


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 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.