From 1cc24c040d12a725be56d4439d87f1201ff72be1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 16:41:10 +0100 Subject: Abbildung Graph mit Adj/Inz --- buch/chapters/70-graphen/beschreibung.tex | 9 +++++++++ 1 file changed, 9 insertions(+) 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. -- cgit v1.2.1