Adjazenzmatrix

	${\begin{array}{r|c}&{\begin{matrix}1&2&3&4\end{matrix}}\\\hline {\begin{matrix}1\\2\\3\\4\end{matrix}}&{\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&0\\0&1&0&0\\\end{pmatrix}}\end{array}}$
Ungerichteter Graph ohne Kantengewichte und ohne Mehrfachkanten	4x4-Adjazenzmatrix zum Graphen links, mit den 3 Kanten (1,2), (2, 3) und (2, 4) die durch 1 gekennzeichnet sind

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 $n\times n$-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.

Varianten

Die folgenden Definitionen gelten für Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E)} , deren Knoten mit den Zahlen 1 bis n durchgehend nummeriert sind. Je nachdem, ob man einen Graphen mit Kantengewichten oder Mehrfachkanten betrachtet, unterscheidet sich die Definition der Adjazenzmatrix leicht. Hypergraphen sowie kantengewichtete Graphen mit Mehrfachkanten besitzen keine Darstellung als Adjazenzmatrix.

Graphen ohne Kantengewichte, ohne Mehrfachkanten

In einem Graphen ohne Kantengewichte und ohne Mehrfachkanten ist die Kantenmenge durch eine Menge 2-Tupeln Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i,j)} gegeben, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} die Nummern der Anfangs- und der Endknoten der Kanten sind. Handelt es sich um einen ungerichteten Graphen ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i,j)} in der Kantenmenge genau dann wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (j,i)} in der Kantenmenge ist. Die Adjazenzmatrix ist für ungerichtete Graphen also immer symmetrisch. In diesem Fall genügt es, nur die obere Hälfte der Matrix zu speichern. Es müssen also nur die Matrixelemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{i,j}} mit Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle i\leq j} gespeichert werden.

Die Adjazenzmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=[a_{ij}]} des Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist durch seine Einträge definiert als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{ij}= \begin{cases} 1 \; \text{falls} \; (i,j) \in E, \\ 0 \; \text{sonst}. \end{cases} }

Ein Beispiel für einen ungerichteten Graphen ohne Kantengewichte und ohne Mehrfachkanten ist in der Abbildung oben zu sehen. Daneben ist die dazugehörige, symmetrische Adjazenzmatrix. Selbstkanten, von einem Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} zum gleichen Knoten $n$ erkennt man an der entsprechenden 1 auf der Hauptdiagonale.

Graphen ohne Kantengewichte, mit Mehrfachkanten

Handelt es sich bei dem Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} um einen Multigraphen ohne Kantengewichte, dann wird die Menge seiner Kanten als Multimenge $E$ von Knotenpaaren beschrieben.

Die Adjazenzmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=[a_{ij}]} des Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist durch seine Einträge definiert als

$a_{ij}={\begin{cases}|K(i,j)|,\;{\text{falls}}\;(i,j)\in E,\\0\;{\text{sonst}}.\end{cases}}$

Hierbei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |K(i,j)|} die Anzahl aller Kanten, welche die Knoten mit Nummer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} verbinden.

Graphen mit Kantengewichten, ohne Mehrfachkanten

	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=\begin{pmatrix} 0 & 0 & 12 & 60 & 0\\ 10 & 0 & 0 & 0 & 0\\ 0 & 20 & 0 & 32 & 0\\ 0 & 0 & 0 & 0 & 0\\ 7 & 0 & 0 & 0 & 0\\ \end{pmatrix}}
Gerichteter Graph mit Kantengewichten und ohne Mehrfachkanten	Adjazenzmatrix zum Graphen links

Für einen kantengewichteten Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E,c)} mit Kantengewicht $c$ ist seine Adjazenzmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=[a_{ij}]} über ihre Einträge definiert als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{ij}= \begin{cases} c_{ij} \; \text{falls} \; (i,j) \in E, \\ 0 \; \text{sonst}. \end{cases} }

Gelegentlich wird anstelle einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \infty} in die Adjazenzmatrix eingetragen. Das bietet sich insbesondere an, wenn die Adjazenzmatrix für Algorithmen genutzt werden soll, für deren Zwecke fehlende Verbindungen als „unendlich teuer“ aufgefasst werden können. Das ist etwa für alle Kürzeste-Wege-Algorithmen der Fall.

Eigenschaften

Datei:Adjazenzgraph.svg	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=\begin{pmatrix} 0 & 3 & 0 & 0\\ 2 & 0 & 4 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 2 & 0\\ \end{pmatrix}}
Gerichteter Graph mit Kantengewichten und mit Mehrfachkanten	reduzible Adjazenzmatrix zum schleifenfreien Graphen links

Einige Eigenschaften eines Graphen lassen sich leicht aus seiner Adjazenzmatrix ermitteln:

• Ist der Graph ungerichtet, so ist die Adjazenzmatrix symmetrisch.
• Sind alle Einträge entlang der Hauptdiagonale der Adjazenzmatrix 0, so ist der Graph schleifenfrei, siehe Abbildung.
• Die Adjazenzmatrix eines gerichteten Graphen ist genau dann irreduzibel, wenn der Graph stark zusammenhängend ist. Analog ist die Adjazenzmatrix eines ungerichteten Graphen genau dann irreduzibel, wenn der Graph zusammenhängend ist.
• Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A } die Adjazenzmatrix eines gerichteten Graphen und ist die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^T+A } irreduzibel, so ist der Graph schwach zusammenhängend. Die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^T+A } entspricht dann (bis auf Gewichte) der Adjazenzmatrix des dem gerichteten Graphen zu Grunde liegenden ungerichteten Graphen
• Sind zwei Adjazenzmatrizen gleich, so sind die Graphen isomorph. Isomorphe Graphen können aber verschiedene Adjazenzmatrizen besitzen, denn die Adjazenzmatrix ändert sich, wenn die Knoten umnummeriert werden.
• Sei für einen ungerichteten und ungewichteten Graphen die zugehörige Inzidenzmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B = (b_{i, j})} gegeben. Dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B B^T= A + \Delta} , wo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta} eine Diagonalmatrix darstellt und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B^T = (b_{j, i})} die Transponierte. Für schleifenfreie Graphen ist daher Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B B^T - \operatorname{diag}(B B^T) = A} .
• Aus der Adjazenzmatrix lässt sich mit Hilfe der Knotengrade die Anzahl aller aufspannenden Bäume für den zugehörigen Graphen bestimmen. Diese beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \det (A')} Stück, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A'} bestimmt ist durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{diag}(\operatorname{deg}(v_{1}),\operatorname{deg}(v_{2}),...,\operatorname{deg}(v_{n}))-A} .

Verwendung

Speicherung von Graphen im Computer

Adjazenzmatrizen können auch zur Speicherung von Graphen im Computer dienen. Sie sind besonders leicht zu implementieren und der Zugriff erfolgt in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(1)} (vgl. Landau-Symbole). Allerdings benötigen sie Speicher von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n^2)} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n } die Anzahl der Knoten des Graphen ist. Deshalb wird diese Speicherungsart für Graphen in der Praxis selten genutzt. Wenn allerdings ein Graph im Vergleich zur Anzahl der Knoten nur wenige Kanten besitzt, kann die Adjazenzmatrix als dünnbesetzte Matrix implementiert werden. Alternativ kann man, um nur Nachbarschaftsbeziehungen darzustellen, auch eine Inzidenzmatrix verwenden. Deren Größe hängt direkt von der Anzahl der Kanten ab.

Spektrale Graphentheorie

→ Hauptartikel: Spektrum (Graphentheorie)

Adjazenzmatrizen werden auch in der spektralen Graphentheorie verwendet. Hierbei geht es insbesondere darum, mittels der verschiedenen Eigenschaften der Adjazenzmatrix Rückschlüsse auf gewisse Eigenschaften des repräsentierten Graphen zu ziehen.

Konstruktion von Ranking-Algorithmen

Die Adjazenzmatrix findet auch in der Konstruktion von zahlreichen Ranking-Algorithmen Verwendung wie z. B. dem PageRank-Algorithmus oder dem Konzept der Hubs und Authorities. Beide Methoden werden hauptsächlich auf die Verlinkung von Homepages im Internet angewandt (daher wird die Adjazenzmatrix in diesem Zusammenhang auch oft Linkmatrix genannt), können aber allgemeiner auch als Methoden zur Berechnung der relativen Wichtigkeit eines Knotens in einem Graphen interpretiert werden. Beim PageRank wird z. B. die Adjazenzmatrix schrittweise modifiziert, um eine stochastische Matrix zu gewinnen, welche auch Google-Matrix genannt wird.

Pfadlänge in Graphen berechnen

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E)} ein gerichteter Graph ohne Mehrfachkanten und ohne Kantengewichte und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} die dazugehörige Adjazenzmatrix, so lässt sich die Anzahl der Pfade von Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} nach Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} , welche genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Kanten enthalten, folgendermaßen bestimmen: berechne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^k} und betrachte den Eintrag in der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Zeile und der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} -ten Spalte. Dieser ist die Anzahl der Pfade von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} , welche genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Kanten enthalten.

Der Vektorraum, der von den Spalten der Adjazenzmatrix aufgespannt wird, wird auch Adjazenzraum des Graphen genannt.

Beispiel

Betrachte folgende ungewichtete Adjazenzmatrix:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A= \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} }

Gesucht wird die Anzahl der Pfade von Knoten 2 nach Knoten 3, mit Pfadlänge 3. Dazu muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^3} berechnet werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^2= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} } Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^3= \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} }

Es gibt also zwei Pfade im Graphen, welche von Knoten 2 nach Knoten 3 gehen und genau 3 Kanten enthalten: Der erste ist 2-1-2-3, der zweite 2-3-4-3.

Erreichbare Knoten ermitteln

Um die Knoten zu ermitteln, die von einem Ausgangsknoten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schritten erreichbar sind, summiert man zunächst die ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Potenzen einer Adjazenzmatrix inklusive der Einheitsmatrix als nullter Potenz auf. Anschließend ersetzt man alle Elemente ungleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} . So erhält man eine Matrix, die für jeden Knoten angibt, welche Knoten von ihm aus in höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schritten erreichbar sind.

Ändert sich diese Matrix vom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten auf den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n+1)} -ten Schritt nicht, hat man so die Erreichbarkeitsmatrix des Graphen ermittelt.

Beispiel

Es wird weiterhin folgende ungewichtete Adjazenzmatrix betrachtet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A= \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} }

Berechnet man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{n=0}^4A^n} und ersetzt alle Einträge, die nicht 0 sind, durch 1, so ergibt sich die Matrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_4= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix} }

Analoges Vorgehen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{n=0}^5A^n} liefert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_4=K_5 } . Die Matrix ändert sich also nicht mehr, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_4 } ist daher bereits die Erreichbarkeitsmatrix des Graphen.

Alternativ zur Adjazenzmatrix kann für Entfernungen zwischen Punkten in Graphen auch eine Entfernungstabelle verwenden. Diese hat ebenfalls für jeden Knoten eine Zeile und eine Spalte, enthält aber die Entfernung zwischen 2 Knoten, unabhängig davon ob diese direkt oder über mehrere Kanten verbunden sind.

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5. 
• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer Spektrum, Berlin u a. 2013, ISBN 978-3-642-32185-6. 
• Volker Turau: Algorithmische Graphentheorie. 3., überarbeitete Auflage. Oldenbourg, München 2009, ISBN 978-3-486-59057-9.