Spektrum (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Spektrale Graphentheorie)
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten | Quelltext bearbeiten]

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

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

Beispiele[Bearbeiten | Quelltext bearbeiten]

Die folgenden Beispiele beziehen sich auf das Spektrum der Adjazenzmatrix.

.
.

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]