Spektrale GraphentheorieSommersemester 2018
|
 |
Kurzbeschreibung
| Inhalt: | Einem Graphen lassen sich zahlreiche Matrizen zuordnen wie z.B. die Adjazenzmatrix. Isomorphe Graphen haben ähnliche Matrizen, daher ist das charakteristische Polynom bzw. Spektrum (Eigenwerte mit Vielfachheiten) eine Isomorphieinvariante des Graphen. Umgekehrt gibt es aber nicht-isomorphe Graphen mit demselben Spektrum. Welche weiteren (spektralen) Informationen helfen diese Graphen zu unterscheiden? Welche strukturellen Informationen lassen sich aus dem Spektrum ablesen? Zum Beispiel lässt sich der Durchmesser eines Graphen durch die Anzahl der verschiedenen Eigenwerte der Adjazenzmatrix und die chromatische Zahl durch ihren maximalen Eigenwert abschätzen. Aus der Laplace-Matrix erhält man die Anzahl der Spannbäume (Matrix-Baum-Satz) und Zusammenhangsinformationen. |
|
Zielgruppe: Vorwissen: |
Mathematiker (wob: M_Ma*), Informatiker Lineare Algebra, besonders wichtig: Determinanten, charakteristisches und Minimalpolynom, Spektralsatz Grundbegriffe der Graphentheorie (Knoten, Kanten, Adjazenzmatrix, Baum, bipartit, Weg, Kreis, Isomorphie...) wie etwa in der Vorlesung "Einführung in die Diskrete Mathematik" oder jedem Buch über Graphentheorie (s.u.) angegeben |
Literatur
Die Vorlesung orientiert sich vorwiegend an folgenden Büchern.
-
D. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, 3. Auflage, Johann Ambrosius Barth, 1995
-
D. Cvetkovic, P. Rowlinson, S. Simic, Eigenspaces of Graphs, Cambridge University Press, 1997
-
D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2010
Graphentheoretische Grundbegriffe kann man auf den ersten Seiten fast jeden Buches zum Thema finden, etwa (Google mich!)
- R. Diestel, Graphentheorie, Springer, 1996
