Adjazenzmatrizen

Adjazenzmatrizen sind eine fundamentale Darstellung von Graphen in der Graphentheorie. Für einen einfachen Graphen mit der Knotenmenge V = {v1, ..., vn} ist die Adjazenzmatrix A eine n×n-Matrix, wobei a_ij = 1, falls es eine Kante zwischen vi und vj gibt, andernfalls 0.

Bei ungerichteten Graphen ist A symmetrisch und die Diagonale enthält üblicherweise 0. Bei gerichteten Graphen gibt a_ij die gerichtete Kante von vi nach vj an; Schleifen sind durch nicht-null Einträge auf der Diagonalen möglich. Bei gewichteten Graphen entspricht a_ij dem Gewicht der Kante. In Multigraphen kann a_ij die Anzahl der Kanten von vi nach vj codieren.

Grundlegende Eigenschaften und Interpretationen: Der Grad eines Knotens i im ungerichteten Fall entspricht der Summe aller a_ij über j; bei gerichteten Graphen gilt der Out-Grad als Summe von a_ij über j und der In-Grad als Summe von a_ij über i. Die Potenzen der Adjazenzmatrix liefern Pfadinformationen: Der Eintrag (A^k)_{ij} gibt die Anzahl der Pfade der Länge k von vi nach vj an. Der Graphencharakter wird auch über die Ep eigenwerte von A untersucht; bei symmetrischer A ist A real und diagonalisierbar, wodurch sich spektrale Eigenschaften des Graphen ableiten lassen.

Anwendungen und Zusammenhang: Die Adjazenzmatrix wird in der Netzwerkanalyse, Pfad- und Reachability-Algorithmen sowie in der spektralen Graphentheorie genutzt. Sie ist eng verwandt mit anderen Repräsentationen wie der Gradmatrix D und dem Laplacian L = D − A, und dient als Grundlage vieler numerischer Verfahren und Modellierungen in der Informatik und Mathematik.