aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/70-graphen/beschreibung.tex
blob: d066a4e1138722595edc30337ba3d4d01a1c3944 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
%
% beschreibung.tex -- Beschreibung von Graphen mit Matrizen
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Beschreibung von Graphen mit Matrizen
\label{buch:section:beschreibung-von-graphen-mit-matrizen}}
\rhead{Beschreibung mit Matrizen}
Als universelles kombinatorisches Modell sind Graphen für eine
Vielzahl von Problemlösungen interessant.
Zum Beispiel zeigt Kapitel~\ref{chapter:munkres}, wie man
ein Zuordnungsproblem als Graphenproblem formulieren kann.
Die Lösung erfolgt dann allerdings zweckmässigerweise unter
Verwendung einer Matrix.
Ziel dieses Abschnitts ist, Graphen und ihre zugehörigen Matrizen
zu definieren und erste Eigenschaften des Graphen mit algebraischen
Mitteln abzuleiten.
Die Präsentation ist allerdings nur ein erster Einstieg, tiefer
gehende Information kann in \cite{skript:brualdi} gefunden werden.

\subsection{Ungerichtete und gerichtete Graphen
\label{subsection:definition-von-graphen}}
In der Einleitung wurde bereits eine informelle
Beschreibung des Konzeptes eines Graphen gegeben.
Um zu einer Beschreibung mit Hilfe von Matrizen zu kommen,
wird eine exakte Definition benötigt.
Dabei werden sich einige Feinheiten zeigen, die für Anwendungen wichtig
sind und sich in Unterschieden in der Definition der zugehörigen Matrix 
äussern.

\subsubsection{Ungerichtete Graphen}
Die Grundlage für alle Arten von Graphen ist eine Menge $V$ von {\em Knoten},
auch {\em Vertizes} genannt.
\index{Knoten}%
\index{Vertex}%
Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten
mit sogenannten Kanten
\index{Kante}%
verbunden werden.
Bei einem ungerichteten Graphen sind die beiden Endpunkte einer Kante
gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der
Kante.
Eine Kante ist daher vollständig spezifiziert, wenn wir die
Menge der Endpunkte kennen.
Dies führt auf die folgende Definition eines ungerichteten Graphen.

\begin{definition}
\label{buch:def:ungerichteter-graph}
\index{Graph!ungerichteter}%
\index{ungerichteter Graph}%
Ein {\em ungerichteter Graph} ist eine endliche Menge $V$ von {\em Knoten}
und eine Menge $E$ von zweielementigen Teilmengen 
\[
E \subset \{\, \{a,b\}\subset V\,|\, a\ne b\}.
\]
Die Elemente von $E$ heissen {\em Kanten} (edges).
\end{definition}

Man beachte, dass es keine Kante gibt, die einen Knoten $a\in V$
mit sich selbst verbindet, da die zugehörige Menge $\{a,a\}=\{a\}$
nicht aus zwei verschiedenen Elementen besteht, wie die
Definition~\ref{buch:def:ungerichteter-graph} dies verlangt.
Es gibt also keine Schleifen an einem Knoten.

\begin{beispiel}
Ein elektrisches Netzwerk von ohmschen Widerständen kann mit Hilfe
eines ungerichteten Graphen beschrieben werden.
Ohmsche Widerstände hängen nicht von der Richtung des Stromflusses
durch die Widerstände ab.
Will man Spannungen und Ströme in einem solchen Netzwerk berechnen,
ist auch das Fehlen von Schleifen, die von $a$ zu $a$ führen, kein
Verlust.
Die Endpunkte solcher Widerstände wären immer auf dem gleichen Potential.
Folglich würde kein Strom fliessen und sie hätten keinen Einfluss auf
das Verhalten des Netzwerkes.
Sie können einfach weggelassen werden.
\end{beispiel}

\subsubsection{Gerichtete Graphen}
In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar.
In einem Strassennetz sind Einbahnstrassen nicht in beiden Richtungen
befahrbar.
Anfangs- und Endpunkt einer Kante müssen in einem solche Graphen
unterschieden werden.
Eine zweielementige Menge ist daher nicht mehr eine geeignete Abstraktion
für die Kante, ein (geordnetes) Paar von Vertizes passt besser.

\begin{definition}
\label{buch:def:gerichteter-graph}
\index{Graph!gerichteter}%
\index{gerichteter Graph}%
Ein {\em gerichteter Graph} ist eine endliche Menge $V$ von Knoten
und eine Menge $E \subset V\times V$ von gerichteten Kanten.
Ausserdem gibt es zwei Abbildungen
\[
\begin{aligned}
a&\colon E\to V: (p,q) \mapsto a((p,q)) = p
\\
e&\colon E\to V: (p,q) \mapsto e((p,q)) = q.
\end{aligned}
\]
Der Knoten $a(k)$ heisst der {\em Anfangspunkt} der Kante $k\in E$,
$e(k)$ heisst der {\em Endpunkt}.
\end{definition}

In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung.
Die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll
geworden.
Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom
Knoten $a$ wieder zu $a$ zurück führt.

Man kann einen ungerichteten Graphen in einen gerichteten Graphen
verwandeln, indem jede Kante $\{u,v\}$ durch zwei Kanten 
$(u,v)$ und $(v,u)$ ersetzt wird.
Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge
$E$ wird so der gerichtete Graph
$(V,E')$ mit der Kantenmenge
\begin{equation*}
E' 
=
\{
(u,v)
\,|\,
\{u,v\}\in E
\}.
\end{equation*}
Eine umgekehrte Zuordnung eines gerichteten zu einem ungerichteten
Graphen ist nicht möglich, da eine ``Schleife'' $(v,v)$ nicht in eine Kante
des ungerichteten Graphen abgebildet werden kann.

In einem gerichteten Graphen kann man sinnvoll von gerichteten Pfaden
sprechen.
\index{Pfad}%
Ein {\em Pfad} $\gamma$ in einem gerichteten Graphen $(V,E)$ ist eine Folge
$k_1,\dots,k_r\in E$ von Kanten derart, dass $e(k_i) = a(k_{i+1})$
für $i=1,\dots,r-1$.
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$.

\subsection{Adjazenzmatrix}
\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/adjazenzu.pdf}
\caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten
Graphen mit fünf Knoten und sieben 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
$1,\dots,n$ mit $n=|V|$ ersetzt.
Diese Zahlen werden dann als Zeilen- und Spaltenindizes interpretiert.
Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$
enthält die Einträge
\begin{equation}
a_{i\!j}
=
\begin{cases}
1&\qquad  \{j,i\} \in E\\
0&\qquad  \text{sonst.}
\end{cases}
\label{buch:graphen:eqn:adjazenzmatrix}
\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.
Ein Beispiel ist in Abbildung~\ref{buch:graphen:fig:adjazenzu}
dargestellt.

\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/adjazenzd.pdf}
\caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten
Graphen mit fünf Knoten und sieben Kanten.
Die roten Einträge in der Adjazenzmatrix $A(G)$ heben die
Unterschiede zur Adjazenzmatrix des gerichteten Graphen
von Abbildung~\ref{buch:graphen:fig:adjazenzu} hervor.
\label{buch:graphen:fig:adjazenzd}}
\end{figure}
Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert
werden wie dies in Abbildung~\ref{buch:graphen:fig:adjazenzd}
illustriert ist.
Ihre Einträge sind in diesem Fall definiert mit Hilfe der 
gerichteten Kanten als
\begin{equation}
A(G)_{i\!j}
=
a_{i\!j}
=
\begin{cases}
1&\qquad  (j,i) \in E\\
0&\qquad  \text{sonst.}
\end{cases}
\label{buch:graphen:eqn:adjazenzmatrixgerichtet}
\end{equation}
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.

\subsubsection{Adjazenzmatrix und die Anzahl der Pfade}
Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach
\eqref{buch:graphen:eqn:adjazenzmatrix} ermöglicht bereits, eine
interessante Aufgabe zu lösen.

\begin{satz}
\label{buch:graphen:pfade-der-laenge-n}
Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix
$A=A(G)$.
Dann gibt das Element $(A^n)_{ji}$ 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:adjazenzmatrix}
formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl
der Pfade der Länge $1$, die $i$ mit $j$ verbinden.
\end{satz}
\index{Anzahl der Pfade}%

\begin{proof}[Beweis]
Zur Unterscheidung der Matrix der Wegzahlen von $A^n$ 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 $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$.
Wir haben also zu zeigen, dass $A^n = A^{(n)}$.

Wir beweisen mit Hilfe von vollständiger Induktion,
dass $A^n$ Pfade der Länge $n$ zählt.
Es ist klar, dass $A^1$ die genannte Eigenschaft hat.
Der Fall $A^1$ dient daher als Induktionsverankerung.

Wir nehmen daher im Sinne einer Induktionsannahme an, dass bereits
bewiesen ist, dass das Element in Zeile
$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 $a_{k\!j}$ 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 $a_{k\!j}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$
nach $k$ führen, und als zweitletzten Knoten über den Knoten $j$ führen.
Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher
\[
a_{ki}^{(n)}
=
\sum_{j=1}^n a_{k\!j} a_{ji}^{(n-1)}.
\]
In Matrixschreibweise bedeutet dies
\[
A^{(n)}
=
A\cdot A^{(n-1)}
=
A\cdot A^{n-1}
=
A^n.
\]
Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme
verwendet.
Damit ist der Induktionsschritt vollzogen und der Satz bewiesen.
\end{proof}

Speziell geben die Diagonalelemente von $A^n$ die Zahl der geschlossenen
Pfade an.
$(A^n)_{ii}$ ist die Anzahl der geschlossenen Pfade, die $i$ enthalten.

Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen 
Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren.

\begin{definition}
\index{Durchmesser eines Graphen}%
\index{Graph!Durchmesser des}%
Der {\em Durchmesser} eines Graphen ist die kürzeste Länge $d$ derart, dass
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 $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 $A^n$ berechnen bis keine Einträge $0$ mehr vorhanden
sind.

\begin{beispiel}
\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/peterson.pdf}
\caption{Peterson-Graph mit zehn Knoten.
\label{buch:figure:peterson}}
\end{figure}
Der Peterson-Graph von Abbildung~\ref{buch:figure:peterson}
hat die Adjazenzmatrix
\[
G
=
\begin{pmatrix}
%1  2  3  4  5  6  7  8  9 10
 0& 0& 1& 1& 0& 1& 0& 0& 0& 0\\ %  1
 0& 0& 0& 1& 1& 0& 1& 0& 0& 0\\ %  2
 1& 0& 0& 0& 1& 0& 0& 1& 0& 0\\ %  3
 1& 1& 0& 0& 0& 0& 0& 0& 1& 0\\ %  4
 0& 1& 1& 0& 0& 0& 0& 0& 0& 1\\ %  5
 1& 0& 0& 0& 0& 0& 1& 0& 0& 1\\ %  6
 0& 1& 0& 0& 0& 1& 0& 1& 0& 0\\ %  7
 0& 0& 1& 0& 0& 0& 1& 0& 1& 0\\ %  8
 0& 0& 0& 1& 0& 0& 0& 1& 0& 1\\ %  9
 0& 0& 0& 0& 1& 1& 0& 0& 1& 0   % 10
\end{pmatrix}.
\]
Durch Nachrechnen kann man bestätigen, dass $G^3$ keine
Ausserdiagonalelemente $0$ enthält:
\[
G^3
=
\begin{pmatrix}
 0& 2& 5& 5& 2& 5& 2& 2& 2& 2\\
 2& 0& 2& 5& 5& 2& 5& 2& 2& 2\\
 5& 2& 0& 2& 5& 2& 2& 5& 2& 2\\
 5& 5& 2& 0& 2& 2& 2& 2& 5& 2\\
 2& 5& 5& 2& 0& 2& 2& 2& 2& 5\\
 5& 2& 2& 2& 2& 0& 5& 2& 2& 5\\
 2& 5& 2& 2& 2& 5& 0& 5& 2& 2\\
 2& 2& 5& 2& 2& 2& 5& 0& 5& 2\\
 2& 2& 2& 5& 2& 2& 2& 5& 0& 5\\
 2& 2& 2& 2& 5& 5& 2& 2& 5& 0
\end{pmatrix}
=
2(U-I) + 3G.
\]
Daraus kann man jetzt ablesen, dass der Durchmesser des Petersongraphen
$d=3$ ist.
Man kann aber noch mehr ablesen:
\begin{itemize}
\item
Es gibt keine geschlossenen Pfade der Länge $3$.
\item
Zwischen benachbarten Knoten gibt es jeweils $5$ Pfade der Länge $3$,
zwischen nicht benachbarten Knoten gibt es genau $2$ Pfade der Länge $3$.
\qedhere
\end{itemize}
\end{beispiel}

Das Beispiel illustriert, wie sich Zählaufgaben von Pfaden leicht mit dem
Matrizenprodukt erledigen lassen.
Trotzdem ist der Algorithmus nicht unbedingt effizient, da der Aufwand
zur Berechnung des Matrizenproduktes relativ gross sein kann.
Für den Peterson-Graphen können die gefundenen Aussagen über die Anzahl
von Pfaden durch Ausnützung der Symmetrien des Graphen leichter direkt
gefunden werden.


\subsection{Inzidenzmatrix
\label{buch:graphen: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.
Oder in der Elektrotechnik, wo jedes Bauteil in einem elektrischen
Netzwerk eine Impedanz hat.

\subsubsection{Beschriftete Graphen}
Ein beschrifteter Graph löst dieses Problem.

\begin{definition}
Eine {\em Beschriftung}
eines gerichteten oder ungerichteten Graphen $G=(V,E)$ 
mit Elementen der Menge $L$, den Labels,
ist eine Abbildung $l\colon E\to L$.
\index{Beschriftung}%
\end{definition}

Einen gerichteten, beschrifteten Graphen können wir 
statt mit einer Beschriftungsabbildung $l$ auch dadurch erhalten,
dass wir Kanten als Tripel betrachten, die ausser den Knoten auch
noch den Wert der Beschriftung enthalten.

\begin{definition}
\label{buch:graphen:def:beschriftetergraphgerichtet}
Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von 
Knoten und eine Menge von beschrifteten Kanten der Form
\[
E \{ (u,v,l)\in V^2\times L \mid \text{Eine Kante mit Beschriftung $l$ führt von $u$ nach $v$}\}.
\]
Die Menge $L$ enthält die möglichen Beschriftungen der Kanten.
\end{definition}

Diese Definition gestattet, dass zwischen zwei Knoten $u$ und $v$
mehrere Kanten vorhanden sind, die sich durch die Beschriftung
unterscheiden.

\subsubsection{Inzidenzmatrix}
Die Adjazenzmatrix bildet nur die Nachbarschaftsbeziehung ab,
sie sagt nichts aus über die ``Qualität'' der Verbindung, die durch
die Beschriftung einer Kante angezeigt wird.
Nach Definition~\ref{buch:graphen:def:beschriftetergraphgerichtet}
ist es auch möglich, dass mehrere Kanten von $a$ nach $e$ führen,
die Adjazenzmatrix kann diese ebenfalls nicht unterscheiden.
Die {\em Inzidenzmatrix}
löst dieses Problem.
\index{Inzidenzmatrix}%
Dazu werden zunächst zusätzlich die Kanten $1,\dots,m$
numeriert, wobei Kanten mit verschiedenen Beschriftungen separat
gezählt werden.
Die Matrixeinträge
\[
b_{i\!j} = \begin{cases}
1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$}
\\
0\qquad&\text{sonst}
\end{cases}
\]
der Inzidenzmatrix $B(G)$
stellen die Beziehung zwischen Kanten und Knoten her.
Für einen gerichteten Graphen wird in der Inzidenzmatrix für
den Anfangspunkt einer Kante $-1$ eingetragen und für den
Endpunkt $+1$.
Die Inzidenzmatrizen $B(G)$ für die Graphen der beiden Beispiele
in den Abbildungen~\ref{buch:graphen:fig:adjazenzu} und
\ref{buch:graphen:fig:adjazenzd} ist ebendort angegeben.

\subsubsection{Inzidenzmatrix und Adjazenzmatrix}
Sei $B(G)$ die Inzidenzmatrix eines ungerichteten 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 Information über die individuellen
Kanten wieder verloren.
Sie hat für $i\ne j$ die Einträge
\begin{align*}
(B(G)B(G)^t)_{i\!j}
&=
\sum_{\text{$k$ Kante}} b_{ik}b_{jk}
\\
&=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden}
\\
&=a_{i\!j}.
\end{align*}
Die Adjazenzmatrix eines Graphen lässt sich also aus der
Inzidenzmatrix berechnen.

\subsubsection{Gradmatrix}
\index{Gradmatrix}%
Die Diagonale von $B(G)B(G)^t$ eines ungerichteten Graphen $G$
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}
\label{buch:graphen:eqn:gradmatrix}
\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)$.
Für Beispiele siehe die Abbildungen~\ref{buch:graphen:fig:adjazenzu} und
\ref{buch:graphen:fig:adjazenzd}.

\subsubsection{Gerichtete Graphen}
Für einen gerichteten Graphen ändert sich an der Diagonalen
der Matrix $B(G)B(G)^t$ nichts.
Sei $k$ die Kante, die vom Knoten $j$ zum Knoten $i$ führt.
Die Einträge in der Inzidenzmatrix sind daher $b_{ik}=1$ und $b_{jk}=-1$.
Da es nur eine solche Kante gibt (der Graph ist nicht beschriftet),
ist $b_{ik}b_{jk}$ der einzige Term in der Summe, mit der das
Matrixelement
\begin{equation}
a_{i\!j}
=
(B(G)B(G)^t)_{i\!j}
=
\sum_{\kappa} b_{i\kappa}b_{j\kappa}
=
b_{ik}b_{jk}
=
-1
\label{buch:graphen:eqn:ausserdiagonal}
\end{equation}
berechnet wird.
Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente
negativ.

\subsubsection{Anwendung: Netlist}
Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen
ist eine elektronische 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 Laplace-Matrix
\label{subsection:laplace-matrix}}
Will man ein elektrisches Netzwerk modellieren oder den Transport
von Wärme durch eine Gitterstruktur berechnen, dann muss man zwar den
Kanten des Netzwerks eine ``Stromrichtung'' geben um ausdrücken zu können,
in welche Richtung der Strom oder die Wärmeenergie fliesst.
Trotzdem gestattet man natürlich auch den Stromfluss in Gegenrichtung.

Wir gehen also aus von einem ungerichteten Graphen $G$, aus dem
wir einen gerichteten Graphen $G'$ machen.
Zu jeder Kante $\{a,b\}$ von $G$ wählen wir genau eine der möglichen
Orientierungen $(a,b)$ oder $(b,a)$ im Graphen $G'$.
Aus der Inzidenzmatrix $B(G')$ lässt sich jetzt ein Operator konstruieren,
der für die Anwendungen besonders gut geeignet ist.

\begin{definition}
\label{buch:graphen:def:laplace-matrix}
Die {\em Laplace-Matrix} des Graphen $G$ ist
\[
L(G) = B(G')B(G')^t,
\]
wobei $G'$ ein wie oben konstruierter gerichteter Graph ist.
\end{definition}

Wir müssen uns davon überzeugen, dass diese Definition sinnvoll ist
und nicht etwa von der Wahl von $G'$ abhängt.
Diese klärt der folgende Satz.

\begin{satz}
Die Laplace-Matrix eines ungerichteten Graphen $G$ ist
\begin{equation}
L(G) = D(G) - A(G)
\label{buch:graphen:eqn:laplace-definition}
\end{equation}
und somit insbesondere unabhängig von der Wahl des Graphen $G'$,
der für die Definition von $L(G)$ verwendet wurde.
\end{satz}

\begin{proof}[Beweis]
Aufgrund der Konstruktion des Graphen $G'$ sind die Diagonalelemente
der Laplace-Matrix
$L(G)=B(G')B(G')^t$ nach \eqref{buch:graphen:eqn:gradmatrix} genau
die Elemente der Gradmatrix $D(G)$.
Die ausserdiagonalen Elemente sind nach
\eqref{buch:graphen:eqn:ausserdiagonal}
genau dann von $0$ verschieden, wenn es in $G$ eine Verbindung zwischen
den beiden Knoten gibt.
Im Produkt $B(G')B(G')^t$ summieren sie sich zu den ausserdiagonalen
Elementen von $-A(G)$.
Damit ist die Formel
\eqref{buch:graphen:eqn:laplace-definition}
nachgewiesen.
\end{proof}

Die Laplace-Matrix tritt zum Beispiel als Diskretisation des Laplace-Operators
in partiellen Differentialgleichungen auf.
Sie ist die Basis für die Untersuchungen der spektralen Graphentheorie
in Abschnitt~\ref{buch:section:spektrale-graphentheorie}.