Direkt zum Inhalt

Lexikon der Mathematik: Eigenwert-eines-Graphen

Bezeichnung für einen Eigenwert der Adjazenzmatrix eines Graphen (Eigenwert).

Es sei G ein Graph und AG = ((aij)) seine Adjazenzmatrix. Ist der Graph G von der Ordnung n, so ist AG = ((aij)) eine symmetrische (n × n)-Matrix, deren Hauptdiagonalenelemente aii sämtlich Null sind. Das charakteristische Polynom PG(x) = det(AGxI) der Matrix AG, wobei I die (n × n)-Einheitsmatrix bedeutet, wird auch charakteristisches Polynom von G genannt, und seine Nullstellen heißen Eigenwerte von G.

Als reelle symmetrische Matrix besitzt AG nur reelle Eigenwerte, die in der Form \begin{eqnarray}{\lambda }_{1}\ge {\lambda }_{2}\ge \cdots \ge {\lambda }_{n}\end{eqnarray} angeordnet seien. Diese Folge der Eigenwerte wird auch das Spektrum von G genannt.

Natürlich ist das Spektrum eines Graphen unabhängig von der Numerierung seiner Ecken, und isomorphe Graphen haben die gleichen Eigenwerte. Beispielsweise besitzt der vollständige Graph Kn das Spektrum λ1 = n − 1 und λ2 = λ3 = … = λn = −1, und der vollständige bipartite Graph Kr,s das Spektrum \({\lambda }_{1}=\sqrt{rs}\), λ2 = λ3 = … = λr+s−1 = 0 und \({\lambda }_{r+s}=-\sqrt{rs}\).

Wäre die Struktur eines Graphen eindeutig durch sein Spektrum bestimmt, so könnte man das bekannte Graphenisomorphieproblem dadurch lösen, daß man die Eigenwerte der entsprechenden Graphen berechnet. Daß diese Methode im allgemeinen jedoch nicht zum Ziel führt, zeigen schon die nicht isomorphen Graphen K1,4 und K1C4, die beide das Spektrum 2, 0, 0, 0, −2 besitzen, wobei C4 der Kreis der Länge 4 ist.

Darüberhinaus gibt es auch nicht isomorphe zusammenhängende Graphen mit gleichem Spektrum, und mit Hilfe einer Konstruktion von A.J. Hoffman (1972) erhält man sogar das folgende Ergebnis.

Zu jeder natürlichen Zahl m existiert eine Zahl N, so daß für alle ganzen Zahlen n ≥ N mindestens m nicht isomorphe reguläre und zusammenhängende Graphen der Ordnung n mit dem gleichen Spektrum existieren.

Sind G1, G2, …, Gη die Zusammenhangskomponenten eines Graphen G, so liefert der Determinantenmultiplikationsatz die Identität \begin{eqnarray}{P}_{G}(x)={P}_{{G}_{1}}(x){P}_{{G}_{2}}(x)\ldots {P}_{{G}_{\eta }}(x).\end{eqnarray}

Folglich erhält man das Spektrum eines Graphen aus den Spektren seiner Zusammenhangskomponenten. Aus der Tatsache, daß die Summe der Eigenwerte (mit Vielfachheit) einer (n × n)-Matrix ((aij)) mit deren Spur, also mit a11 + a22 + … + ann, übereinstimmt, ergibt sich für das Spektrum von G unmittelbar die Aussage \begin{eqnarray}{\lambda }_{1}+{\lambda }_{2}+\cdots +{\lambda }_{n}=0.\end{eqnarray}

Ist G ein zusammenhängender Graph der Ordnung n vom Maximalgrad Δ(G), so beweist man die meisten der folgenden Eigenschaften mit Hilfe von klassischen Resultaten, die O. Perron 1907 und G. Frobenius 1912 zur allgemeinen Matrizentheorie entwickelt haben.

  • Für jeden Eigenwert λ von G gilt |λ| ≤ Δ(G).
  • Der Graph G besitzt genau dann den Eigenwert Δ(G), wenn G regulär ist.
  • Ist −Δ(G) ein Eigenwert von G, so ist G ein regulärer und bipartiter Graph.
  • Ist G bipartit mit dem Eigenwert λ, so ist auch −λ ein Eigenwert von G.
  • Im Jahre 1967 hat H.S. Wilf einen interessanten Zusammenhang zwischen den Eigenwerten eines Graphen G und seiner chromatischen Zahl χ(G) herausgefunden.

    Es sei G ein zusammenhängender Graph und λ1sein größter Eigenwert. Dann gilt \begin{eqnarray}\chi (G)\le 1+{\lambda }_{1},\end{eqnarray}und die obere Schranke wird in dieser Abschätzung genau dann erreicht, wenn G der vollständige Graph oder ein Kreis ungerader Länge ist.

    Wegen (i) verallgemeinert dieser Satz von Wilf den bekannten Satz von Brooks χ(G) ≤ 1 + Δ(G), wobei genau dann die Gleichheit gilt, wenn G der vollständige Graph oder ein Kreis ungerader Länge ist.

    Vertiefte Informationen zur Theorie der Eigenwerte von Graphen findet man beispielweise in der Monographie [1].

    [1] Cvetkovic, D.M.; Doob, M.; Sachs, H.: Spectra of Graphs. Johann Ambrosius Barth, Heidelberg Leipzig, 3rd edition, 1995.

    Lesermeinung

    Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

    • Die Autoren
    - Prof. Dr. Guido Walz

    Partnervideos