diff options
| -rw-r--r-- | buch/chapters/70-graphen/beschreibung.tex | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 174102a..70dc296 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -131,6 +131,13 @@ nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. \subsubsection{Adjazenzmatrix} +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/adjazenzu.pdf} +\caption{Adjazenz- und Inzidenzmatrix eines ungerichteten +Graphen mit $5$ Knoten und $7$ Kanten. +\label{buch:graphen:fig:adjazenzu}} +\end{figure} Eine naheliegende Beschreibung eines Graphen mit Hilfe einer Matrix kann man wie folgt erhalten. Zunächst werden die Knoten aus der Menge $V$ durch die Zahlen @@ -151,6 +158,8 @@ Die Matrix hat also genau dann einen von Null verschiedenen Eintrag in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$ im Graphen verbunden sind. Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch. +Ein Beispiel ist in Abbildung~\ref{buch:graphen:fig:adjazenzu} +dargestellt. Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert werden. |