From b8f090eb8c7b621a98fc58ce50d0af1fe246f684 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 16:37:34 +0100 Subject: add new graph --- buch/chapters/70-graphen/beschreibung.tex | 199 +++++++++++++++++++++----- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/adjazenzu.pdf | Bin 0 -> 19952 bytes buch/chapters/70-graphen/images/adjazenzu.tex | 87 +++++++++++ 4 files changed, 251 insertions(+), 40 deletions(-) create mode 100644 buch/chapters/70-graphen/images/adjazenzu.pdf create mode 100644 buch/chapters/70-graphen/images/adjazenzu.tex (limited to 'buch') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 2dcc78f..174102a 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -130,14 +130,36 @@ Dies bedeutet, dass der Endpunkt jeder Kante mit dem Anfangspunkt der nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. -Eine naheliegende Beschreibung eines gerichteten Graphen mit Hilfe einer +\subsubsection{Adjazenzmatrix} +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 $1,\dots,n$ mit $n=|V|$ ersetzt. Diese Zahlen werden dann als Zeilen- uns Spaltenindizes interpretiert. -Die zum Graphen gehörige Matrix enthält die Einträge +Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$ +enthält die Einträge \begin{equation} -g_{ij} +a_{ij} += +\begin{cases} +1&\qquad \{j,i\} \in E\\ +0&\qquad \text{sonst.} +\end{cases} +\label{buch:graphen:eqn:linkmatrix} +\end{equation} +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. + +Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert +werden. +Ihre Einträge sind in diesem Fall definiert mit Hilfe der +gerichteten Kanten als +\begin{equation} +A(G)_{ij} += +a_{ij} = \begin{cases} 1&\qquad (j,i) \in E\\ @@ -145,18 +167,22 @@ g_{ij} \end{cases} \label{buch:graphen:eqn:linkmatrix} \end{equation} -Die Matrix $G$ hat also genau dann einen nicht verschwindenden +Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung von Knoten $j$ zu Knoten $i$ gibt. + % XXX Abbildung Graph und Verbindungs-Matrix -Die Beschreibung des Graphen mit der Matrix $G$ nach + +\subsubsection{Adjazenzmatrix und die Anzahl der Pfade} +Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach \eqref{buch:graphen:eqn:linkmatrix} ermöglicht bereits, eine interessante Aufgabe zu lösen. \begin{satz} \label{buch:graphen:pfade-der-laenge-n} -Der gerichtete Graph $([n],E)$ werde beschrieben durch die Matrix $G$. -Dann gibt das Element in Zeile $j$ und Spalte $i$ von $G^n$ die Anzahl +Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix +$A=A(G)$. +Dann gibt das Element in Zeile $j$ und Spalte $i$ von $A^n$ die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix} formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl @@ -164,57 +190,49 @@ der Pfade der Länge $1$, die $i$ mit $j$ verbinden. \end{satz} \begin{proof}[Beweis] -Es ist klar, dass $G^1$ die genannte Eigenschaft hat. -Wir beweisen, dass $G^n$ Pfade der Länge $n$ zählt, mit Hilfe von +Es ist klar, dass $A^1$ die genannte Eigenschaft hat. +Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von vollständiger Induktion. -Zur Unterscheidung schreiben wir $G^{(n)}$ für die Matrix, die in Zeile +Zur Unterscheidung schreiben wir $A^{(n)}$ für die Matrix, die in Zeile $j$ und Spalte $i$ die Anzahl der Pfade der Länge $n$ von $i$ nach $j$ enhält. -Die zugehörigen Matrixelemente schreiben wir $g_{ji}^{n}$ bzw.~$g_{ji}^{(n)}$. -Wir haben also zu zeigen, dass $G^n = G^{(n)}$. +Die zugehörigen Matrixelemente schreiben wir $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$. +Wir haben also zu zeigen, dass $A^n = A^{(n)}$. Wir nehmen daher an, dass bereits bewiesen ist, dass das Element in Zeile -$j$ und Spalte $i$ von $G^{n-1}$ die Anzahl der Pfade der Länge $n-1$ -zählt, dass also $G^{n-1}=G^{(n-1)}$. +$j$ und Spalte $i$ von $A^{n-1}$ die Anzahl der Pfade der Länge $n-1$ +zählt, dass also $A^{n-1}=A^{(n-1)}$. Dies ist die Induktionsannahme. Wir bilden jetzt alle Pfade der Länge $n$ von $i$ nach $k$. Ein Pfad der Länge besteht aus einem Pfad der Länge $n-1$, der von $i$ zu einem beliebigen Knoten $j$ führt, gefolgt von einer einzelnen Kante, die von $j$ nach $k$ führt. -Ob es eine solche Kante gibt, zeigt das Matrixelement $g_{kj}$ an. -Das Element in Zeile $j$ und Spalte $i$ der Matrix $G^{(n-1)}$ gibt +Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{kj}$ an. +Das Element in Zeile $j$ und Spalte $i$ der Matrix $A^{(n-1)}$ gibt die Anzahl der Wege von $i$ nach $j$ an. -Es gibt also $g_{kj}\cdot g_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ +Es gibt also $a_{kj}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ nach $k$ führen, aber als zweitletzten Knoten über den Knoten $j$ führen. Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher \[ -g_{ki}^{(n)} +a_{ki}^{(n)} = -\sum_{j=1}^n g_{kj} g_{ji}^{(n-1)}. +\sum_{j=1}^n a_{kj} a_{ji}^{(n-1)}. \] In Matrixschreibweise bedeutet dies \[ -G^{(n)} +A^{(n)} = -G\cdot G^{(n-1)} +A\cdot A^{(n-1)} = -G\cdot G^{n-1} +A\cdot A^{n-1} = -G^n. +A^n. \] Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme verwendet. \end{proof} -Die Definition~\eqref{buch:graphen:eqn:linkmatrix} der Matrix, die den -Graphen beschreibt, lässt sich natürlich auch auf einen ungerichteten -Graphen verallgemeinern. -Die entstehende Matrix hat dann aber die zusätzlichen Eigenschaften, dass -alle Diagonalelemente $0$ sind und dass die Matrix symmetrisch ist. -Auch im Fall eines ungerichteten Graphen kann die Matrix dazu verwendet -werden, die Anzahl der Pfade zu zählen. - Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren. @@ -226,11 +244,11 @@ es zwischen zwei beliebigen Knoten einen Pfad der Länge $\le d$ gibt. \end{definition} Der Durchmesser $d$ eines Graphen ist der kleinste Exponent derart, -dass $G^d$ keine ausserdiagonalen Einträge $0$ hat. -Die Diagonalelemente von $G^n$ zählen die Anzahl der geschlossenen Pfade +dass $A^d$ keine ausserdiagonalen Einträge $0$ hat. +Die Diagonalelemente von $A^n$ zählen die Anzahl der geschlossenen Pfade der Länge $n$, die durch einen Knoten führen. Diese können für den Durchmesser ignoriert werden. -Man kann also Potenzen $G^n$ berechnen bis keine Einträge $0$ mehr vorhanden +Man kann also Potenzen $A^n$ berechnen bis keine Einträge $0$ mehr vorhanden sind. \begin{beispiel} @@ -240,7 +258,7 @@ sind. \caption{Peterson-Graph mit zehn Knoten. \label{buch:figure:peterson}} \end{figure} -Der Peterson-Graph hat die Matrix +Der Peterson-Graph hat die Adjazenzmatrix \[ G = @@ -309,7 +327,110 @@ eines gerichteten oder ungerichteten Graphen $G=(V,E)$ ist eine Abbildung $l\colon E\to L$. \end{definition} -\subsection{Die Adjazenz-Matrix und Laplace-Matrix +\subsection{Inzidenzmatrix} +Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise +mit den Kanten verbunden ist, nicht mehr darstellen. +Dies tritt zum Beispiel in der Informatik bei der Beschreibung +endlicher Automaten auf, wo zu jeder gerichteten Kante auch noch +Buchstaben gehören, für die der Übergang entlang dieser Kante +möglich ist. + +Die {\em Inzidenzmatrix} löst dieses Problem. +Dazu werden zunächst die Kanten numeriert $1,\dots,m$ +numeriert. +Die Matrixeinträge +\[ +a_{ij} = \begin{cases} +1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} +\\ +0\qquad&\text{sonst} +\end{cases} +\] +stellen die Beziehung zwischen Kanten und Knoten her. + +\subsubsection{Beschriftete Graphen} +Die Inzidenzmatrix kann auch einen erweiterten Graphenbegriff abbilden, +in dem zwischen zwei Kanten mehrere Verbindungen möglich sind. +Graphen mit beschrifteten Kanten gehören dazu. + +\begin{definition} +Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von +Knoten und eine Menge von beschrifteten Kanten der Form +\[ +E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}. +\] +\end{definition} + +Für einen gerichteten Graphen wird in der Inzidenzmatrix für +den Anfangspunkt einer Kante $-1$ eingetragen und für den +Endpunkt $+1$. +% XXX Beispiel + +\subsubsection{Inzidenzmatrix und Adjazenzmatrix} +Sei $B(G)$ die Inzidenzmatrix eines Graphen $G$. +Die Spalten von $B(G)$ sind mit den Kanten des Graphen indiziert. +Die Matrix $B(G)B(G)^t$ ist eine quadratische Matrix, deren +Zeilen und Spalten mit den Knoten des Graphen indiziert sind. +In dieser Matrix geht die Informatione über die individuellen +Kanten wieder verloren. +Sie hat für $i\ne j$ die Einträge +\begin{align*} +(B(G)B(G)^t)_{ij} +&= +\sum_{\text{$k$ Kante}} b_{ik}b_{jk} +\\ +&=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden} +\\ +&=a_{ij} +\end{align*} +Die Adjazenzmatrix eines Graphen lässt sich also aus der +Inzidenzmatrix berechnen. + +\subsubsection{Gradmatrix} +Die Diagonale von $B(G)B(G)^t$ enthält die Werte +\begin{align*} +(B(G)B(G)^t)_{ii} +&= +\sum_{\text{$k$ Kante}} b_{ik}^2 += +\text{Anzahl Kanten, die im Knoten $i$ enden} +\end{align*} +Der {\em Grad} eines Knoten eines Graphen ist die Anzahl der +\index{Grad eines Knotens}% +Kanten, die in diesem Knoten enden. +Die Diagonalmatrix die aus den Graden der Knoten besteht, heisst die +Gradmatrix $D(G)$ des Graphen. +Es gilt daher $B(G)B(G)^t = A(G) + D(G)$. + +\subsubsection{Gerichtete Graphen} +Für einen gerichteten Graphen ändert sich an der Diagonalen +der Matrix $B(G)B(G)^t$ nichts. +Da es in einem gerichteten Graphen nur eine einzige Kante $k$ gibt, die zwei +Knoten $i$ und $j$ verbinden kann, muss das zugehörige +Ausserdiagonalelement +\[ +a_{ij} +=b_{ik}b_{jk} += +-1 +\] +sein. +Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente +negativ und es gilt $B(G)B(G)^t = D(G)-A(G)$. + +\subsubsection{Anwendung: Netlist} +Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen +ist eine eletronische Schaltung. +Die Knoten des Graphen sind untereinander verbundene Leiter, sie werden +auch {\em nets} genannt. +Die beschrifteten Kanten sind die elektronischen Bauteile, die solche +Nets miteinander verbinden. +Die Inzidenzmatrix beschreibt, welche Anschlüsse eines Bauteils mit +welchen Nets verbunden werden müssen. +Die Informationen in der Inzidenzmatrix werden also in einer +Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben. + +\subsection{Die Adjazenzmatrix und Laplace-Matrix \label{subsection:adjazenz-und-laplace-matrix}} Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix} ``vergisst'' den ``Namen'' der Kante, die eine Verbindung zwischen zwei @@ -319,12 +440,12 @@ Matrixbeschreibung zuzuführen. Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden Knoten miteinander verbindet. -Dies führt zur sogenannten Adjazenz-Matrix. +Dies führt zur sogenannten Adjazenzmatrix. \begin{definition} \label{buch:def:adjazenz-matrix} Ist $G=(V,E)$ ein gerichteter Graph mit $n=|G|$ Vertizes und $m=|E|$ Kanten, -dann ist die zugehörige {\em Adjazenz-Matrix} $A=A(G)$ eine $n\times m$-Matrix. +dann ist die zugehörige {\em Adjazenzmatrix} $A=A(G)$ eine $n\times m$-Matrix. In der Spalte $k$ wird der Anfangspunkt der Kante $k$ mit $-1$, der Endpunkt mit $+1$ angezeigt, die übrigen Einträge sind $0$. $A$ hat also die Matrixelemente @@ -346,7 +467,7 @@ Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten eine Kante beginnt oder endet. -Es ist natürlich möglich, aus der Adjazenz-Matrix auch die Link-Matrix +Es ist natürlich möglich, aus der Adjazenzmatrix auch die Link-Matrix zu rekonstruieren. Dazu muss für jedes Paar $(j,i)$ von Knoten festgestellt werden, ob die Adjazenzmatrix eine entsprechende Verbindung enthält, also ob der diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index 2199ddc..9e61446 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,8 +3,11 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf +all: peterson.pdf adjazenzu.pdf peterson.pdf: peterson.tex pdflatex peterson.tex +adjazenzu.pdf: adjazenzu.tex + pdflatex adjazenzu.tex + diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf new file mode 100644 index 0000000..c24335a Binary files /dev/null and b/buch/chapters/70-graphen/images/adjazenzu.pdf differ diff --git a/buch/chapters/70-graphen/images/adjazenzu.tex b/buch/chapters/70-graphen/images/adjazenzu.tex new file mode 100644 index 0000000..29e094f --- /dev/null +++ b/buch/chapters/70-graphen/images/adjazenzu.tex @@ -0,0 +1,87 @@ +% +% adjazenzu.tex -- Adjazenz-Matrix für einen ungerichten Graphen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\r{1.8} + +\begin{scope} +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +\node at ($0.5*(A)+0.5*(B)$) [above right] {$1$}; +\node at ($0.5*(B)+0.5*(C)$) [above left] {$2$}; +\node at ($0.5*(C)+0.5*(D)$) [left] {$3$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$4$}; +\node at ($0.5*(E)+0.5*(A)$) [below right] {$5$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$6$}; +\node at ($0.4*(B)+0.6*(D)$) [left] {$7$}; + +\end{scope} + +\begin{scope}[xshift=3cm,yshift=-1.1cm] +\node at (0,0) [right] {$\displaystyle +B(G) += +\begin{pmatrix} +1&0&0&0&1&0&0\\ +1&1&0&0&0&1&0\\ +0&1&1&0&0&0&1\\ +0&0&1&1&0&1&0\\ +0&0&0&1&1&0&1 +\end{pmatrix}$}; +\end{scope} + +\begin{scope}[xshift=3cm,yshift=1.1cm] +\node at (0,0) [right] {$\displaystyle +A(G) += +\begin{pmatrix} +0&1&1&0&1\\ +1&0&1&1&0\\ +1&1&0&1&0\\ +0&1&1&0&1\\ +1&0&0&1&0 +\end{pmatrix}$}; +\end{scope} + +\end{tikzpicture} +\end{document} + -- cgit v1.2.1