Spektrum (Graphentheorie)

Das Spektrum dient in der Graphentheorie zur Untersuchung der Eigenschaften von Graphen. Das entsprechende Gebiet wird als Algebraische Graphentheorie oder Spektrale Graphentheorie bezeichnet. Die Berechnung des Spektrums eines Graphen ermöglicht einen sehr effektiven Algorithmus zum Graphenzeichnen (Hall's Algorithmus.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden.

Definition

Als Spektrum eines Graphen bezeichnet man die (nach Größe geordnete) Folge der Eigenwerte seiner Adjazenzmatrix. Letztere werden auch als Eigenwerte des Graphen bezeichnet.

(Ungerichtete Graphen haben eine symmetrische Adjazenzmatrix und deshalb reelle Eigenwerte.)

Graph Adjazenzmatrix Eigenwerte
6n-graf.svg
{\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}
{\begin{pmatrix}\lambda _{1}=2.53948\ldots \\\lambda _{2}=1.08247\ldots \\\lambda _{3}=0.26114\ldots \\\lambda _{4}=-0.54063\ldots \\\lambda _{5}=-1.20607\ldots \\\lambda _{6}=-2.13639\ldots \\\end{pmatrix}}

Häufig werden auch die Eigenwerte der Laplace-Matrix des Graphen als sein Spektrum bezeichnet.

Beispiele

Die folgenden Beispiele beziehen sich auf das Spektrum der Adjazenzmatrix.

(n-1,-1,-1,\ldots ,-1).
({\sqrt  {mn}},0,\ldots ,0,-{\sqrt  {mn}}).
Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 08.10. 2021