Adjazenzmatrix

Eine Adjazenzmatrix (manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert, welche Knoten des Graphen durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine -Matrix ergibt. Ein Eintrag in der i-ten Zeile und j-ten Spalte gibt hierbei an, ob eine Kante von dem i-ten zu dem j-ten Knoten führt. Steht an dieser Stelle eine 0, ist keine Kante vorhanden – eine 1 gibt an, dass eine Kante existiert, siehe Abbildung rechts. Es gibt unterschiedliche Varianten, abhängig von der Art des Graphen, z. B. für Mehrfachkanten. Die Repräsentation eines Graphen als Matrix erlaubt den Einsatz von Methoden der linearen Algebra. Die Anwendung und Untersuchung solcher Methoden bildet ein zentrales Thema in der spektralen Graphentheorie. Es bildet damit eine Schnittstelle zwischen Graphentheorie und linearer Algebra.