Definition (Graph):
Sei V eine Menge (Vertizes) und K
(Kanten) eine Menge von Paaren von Elementen aus V.
Dann heißt G=(V,K) ein Graph.
Geometrisch werden
die Vertizes eines Graphen oft als Punkte und die Kanten als
deren Verbindungsstrecken gedeutet.
Sei G ein Graph der Ordnung n mit
numerierten Vertizes 
, wobei 
.
Die Inzidenzmatrix 
von G ist definiert durch:
Der Vektorraum von G ist die Menge aller Abbildungen
. Er wird aufgespannt durch die Basisvektoren
Die Inzidenzmatrix A(G) operiert auf Vektorraum von G. Gesucht
ist nun das Spektrum von G, also die Eigenwerte 
von A(G) und ihre
Multiplizitäten 
.
Eine gute Einführung in die Graphentheorie und einige nützliche
Theoreme hierzu finden sich in [Boll], insbesondere zur
Verwendung kollabierter Inzidenzmatrizen: weist ein Graph bestimmte
Symmetrien auf, so läßt sich eine Matrix kleinerer Dimension finden,
die die gleichen Eigenwerte wie die Inzidenzmatrix besitzt.