Spektrum (Graphentheorie)

Das Spektrum d​ient in d​er Graphentheorie z​ur Untersuchung d​er Eigenschaften v​on Graphen. Das entsprechende Gebiet w​ird als Algebraische Graphentheorie o​der Spektrale Graphentheorie bezeichnet. Die Berechnung d​es Spektrums e​ines Graphen ermöglicht e​inen sehr effektiven Algorithmus z​um Graphenzeichnen (Hall's Algorithmus.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden.

Definition

Als Spektrum e​ines Graphen bezeichnet m​an die (nach Größe geordnete) Folge d​er Eigenwerte seiner Adjazenzmatrix. Letztere werden a​uch als Eigenwerte d​es Graphen bezeichnet.

(Ungerichtete Graphen h​aben eine symmetrische Adjazenzmatrix u​nd deshalb reelle Eigenwerte.)

Graph	Adjazenzmatrix	Eigenwerte
	${\displaystyle {\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}}}$	${\displaystyle {\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 a​uch die Eigenwerte d​er Laplace-Matrix d​es Graphen a​ls sein Spektrum bezeichnet.

Beispiele

Die folgenden Beispiele beziehen s​ich auf d​as Spektrum d​er Adjazenzmatrix.

• Der vollständige Graph auf ${\displaystyle n}$ Knoten hat das Spektrum
  ${\displaystyle (n-1,-1,-1,\ldots ,-1)}$.
• Der vollständig bipartite Graph ${\displaystyle K_{mn}}$ hat das Spektrum
  ${\displaystyle ({\sqrt {mn}},0,\ldots ,0,-{\sqrt {mn}})}$.
• Ein Graph ist genau dann bipartit, wenn sein Spektrum symmetrisch bzgl. ${\displaystyle 0}$ ist.
• Der größte Eigenwert eines ${\displaystyle k}$-regulären Graphen ist ${\displaystyle k}$ (Satz von Frobenius), seine Vielfachheit ist die Anzahl der Zusammenhangskomponenten des Graphen.

Literatur

• Dragoš M. Cvetković, Michael Doob, Horst Sachs: Spectra of graphs. Theory and applications. Third edition. Johann Ambrosius Barth, Heidelberg 1995, ISBN 3-335-00407-8.
• Norman Biggs: Algebraic graph theory. Second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge 1993, ISBN 0-521-45897-8.
• Chris Godsil, Gordon Royle: Algebraic graph theory (Graduate Texts in Mathematics, 207). Springer-Verlag, New York 2001, ISBN 0-387-95241-1; 0-387-95220-9.

Weblinks

• Brouwer-Haemers: Graph Spectrum (PDF)
• Spielman: Spectral Graph Theory (PDF; 476 kB)
• Gerrit Pflüger: Hauptseminar: Spektren von Graphen. 1. Vortrag: Grundlagen der Graphentheorie/Beispiele. Sommersemester 2012. Uni Mainz.
• Chung: Diameters and Eigenvalues (PDF; 472 kB)