aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/70-graphen/spektral.tex
blob: 5fb305622904b9a3b76a20dc8c9206535a6965c4 (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
%
% spektral.tex -- spektrale Graphentheorie
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Spektrale Graphentheorie
\label{buch:section:spektrale-graphentheorie}}
\rhead{Spektrale Graphentheorie}
Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch
die Laplace-Matrix codieren alle wesentliche Information eines
ungerichteten Graphen.
Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine
Komponente haben.
Dies eröffnet die Möglichkeit, den Graphen über die linearalgebraischen
Eigenschaften dieser Matrizen zu studieren.
Dieser Abschnitt soll diese Idee an dem ziemlich übersichtlichen Beispiel
der chromatischen Zahl eines Graphen illustrieren.

\subsection{Chromatische Zahl und Unabhängigkeitszahl
\label{buch:subsection:chromatische-zahl}}
Der Grad eines Knotens ist ein mass dafür, wie stark ein Graph
``vernetzt'' ist.
Je höher der Grad, desto mehr direkte Verbindungen zwischen Knoten gibt es.
Noch etwas präziser können diese Idee die beiden mit Hilfe der
chromatischen zahl und der Unabhängigkeitszahl erfasst werden.

\begin{definition}
Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist
die minimale Anzahl von Farben, die Einfärben der Knoten eines Graphen
nötig sind, sodass benachbarte Knoten verschiedene Farben haben.
\index{chromatische Zahl}
\end{definition}

\begin{definition}
Eine Menge von Knoten eines Graphen heisst {\em unabhängig}, wenn 
keine zwei Knoten im Graphen verbunden sind.
Die {\em Unabhängigkeitszahl} $\operatorname{ind}G$ eines Graphen $G$
ist die maximale Anzahl Knoten einer unabhängigen Menge.
\index{Unabhängigkeitszahl}
\end{definition}

Zwischen der chromatischen Zahl und der Unabhängigkeitszahl eines Graphen
muss es einen Zusammenhang geben.
Je mehr Verbingungen es im Graphen gibt, desto grösser wird die chromatische
Zahl.
Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein.

\begin{satz}
\label{buch:satz:chrind}
Ist $G$ ein Graph mit $n$ Knoten, dann gilt
$\operatorname{chr}G\cdot\operatorname{ind}G\ge n$.
\end{satz}

\begin{proof}[Beweis]
Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben
teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit
gleicher Farbe $f$ ein.
Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also
höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt,
also $|V_f|\le \operatorname{ind}G$.
Da die Menge aller Knoten die Vereinigung der Mengen $V_f$ ist,
ist die Gesamtzahl der Knoten 
\begin{align*}
V
&=
\bigcup_{\text{$f$ eine Farbe}} V_f
&&\Rightarrow&
n
&=
\sum_{\text{$f$ eine Farbe}} |V_f| 
\\
&
&&&
&\le
\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G
=
(\text{Anzahl Farben})\cdot \operatorname{ind}G
=
\operatorname{chr}G \cdot \operatorname{ind}G.
\end{align*}
Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt.
\qedhere
\end{proof}

\begin{beispiel}
In einem vollständigen Graphen ist jeder Knoten mit jedem anderen verbunden.
Jede Menge mit zwei oder mehr Knoten kann daher nicht unabhängig sein, die
Unabhängigkeitszahl ist daher $\operatorname{ind}G=1$.
Andererseits ist für jeden Knoten eine eigene Farbe nötig, daher ist die
chromatische Zahl $\operatorname{chr}G=n$.
Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar mit
Gleichheit.
Das Beispiel zeigt, dass die Ungleichung nicht ohne zusätzliche Annahmen
verbessert werden kann.
\end{beispiel}

\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/petersonchrind.pdf}
\caption{Chromatische Zahl und Unabhängigkeitszahl des Peterson-Graphen.
Die chromatische Zahl ist $3$, da der Graph sich mit drei Farben einfärben
lässt (links).
Die Unabhängigkeitszahl ist $4$, die vier grösseren Knoten im rechten
Graphen sind unabhängig.
Die Farben der kleinen Knoten sind die additive Mischung der Farben
der grossen Knoten, mit denen sie verbunden sind.
\label{buch:graphen:fig:chrindpeterson}}
\end{figure}

\begin{beispiel}
Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson}
hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl
$\operatorname{ind}P=4$.
Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar als
Ungleichung: $\operatorname{chr}P\cdot\operatorname{ind}P=3\cdot 4=12>10=n$.
\end{beispiel}

Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer
unabhängigen Menge von Punkten.
Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die
chromatische Zahl als ein Mass dafür, wieviele solche anabhängige 
Mengen in einem Graphen untergebracht werden können.

%
% Chromatische Zahl und maximaler Grad
%
\subsection{Chromatische Zahl und maximaler Grad
\label{buch:subsection:chr-und-maximaler-grad}}
Wenn kein Knoten mehr als $d$ Nachbarn hat, dann reichen
$d+1$ Farben immer, um diesen Knoten und seine Nachbarn einzufärben.
Das heisst aber noch nicht, dass dann auch $d+1$ Farben zur
Einfärbung des ganzen Graphen reichen.
Genau dies garantiert jedoch der folgende Satz.

\begin{definition}
Der maximale Grad
\(
\max_{v\in V} \deg(v)
\)
wird mit $d$ bezeichnet.
\end{definition}

\begin{satz}
\label{buch:graphen:satz:chrmaxgrad}
Ist $G$ ein Graph mit maximalem Grad $d$, dann gilt 
$\operatorname{chr}G \le d+1$.
\end{satz}

\begin{proof}[Beweis]
Wir führen den Beweis mit Hilfe von vollständiger Induktion nach der
Anzahl Knoten eines Graphen.
Ein Graph mit nur einem Knoten hat keine Kanten, der maximale Grad ist
daher $0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des
einen Knotens.

Wir nehmen jetzt an, die Behaupt sei für Graphen mit $n-1$ Knoten bereits
bewiesen, ein Graph $G'$ mit $n-1$ Knoten und maximalem Grad $d'$ erfüllt
also die Ungleichung $\operatorname{chr}G'\le d'+1$.

Wir wählen jetzt einen beleibigen Knoten $v$ des Graphen $G$ und bilden
den Graphen $G'$, der aus $G$ entsteht, indem man den Knoten $v$
entfernt: $G'=G\setminus\{v\}$.
Der maximale Grad $d'$ von $G'$ kann dabei nicht grösser werden, es ist
also $d'\le d$.
Da $G'$ genau $n-1$ Knoten hat, lässt er sich mit höchstens $d'+1\le d+1$
Farben einfärben.
Es muss jetzt also nur noch eine Farbe für den Knoten $v$ gefunden werden.
Da $d$ der maximale Grad ist, hat $v$ höchstens $d$ Nachbarn, die höchstens
$d$ verschiedene Farben haben können.
Von den $d+1$ zur Verfügung stehenden Farben bleibt also mindestens eine
übrig, mit der man den Knoten $v$ einfärben kann.
Damit ist der Induktionsschritt gelungen und somit der Satz bewiesen.
\end{proof}

Das Argument im Beweis von Satz~\ref{buch:graphen:satz:chrmaxgrad}
ist für alle Begriffe anwendbar, die sich bei der Bildung eines 
Untergraphen auf ``monotone'' Art ändern.
Die chromatische Zahl eines Untergraphen ist höchstens so gross wie die
des ganzen Graphen. 
Dann kann man eine Ungleichung für grosse Graphen schrittweise aus
entsprechenden Ungleichungen für die kleineren Teilgraphen gewinnen.
Ziel der folgenden Abschnitte ist zu zeigen, dass sich eine Grösse
mit ähnlichen Eigenschaften aus dem Eigenwertspektrum der Adjazenzmatrix
ablesen lässt.
Daraus ergibt sich dann eine bessere Abschätzung der chromatischen Zahl
eines Graphen.

%
% maximaler Eigenwert und maximaler Grad
%
\subsection{Maximaler Eigenwert von $A(G)$ und maximaler Grad
\label{buch:subsection:maximaler-eigenwert}}
Die Adjazenzmatrix $A(G)$ eines Graphen $G$  mit $n$ Knoten enthält unter
anderem auch die Information über den Grad eines Knotens.
Die Summe der Elemente einer Zeile oder einer Spalte ergibt einen Vektor,
der die Grade der Knoten als Komponenten enthält.
Ist $U$ ein $n$-dimensionaler Vektor aus lauter Einsen, dann ist
ist $A(G)U$ ein Spaltenvektor bestehend aus den Zeilensummen der Matrix 
$A(G)$ und
$U^tA(G)$ ein Zeilenvektor bestehend aus den Spaltensummen.
$A(G)U$ ist also der Vektor der Grade der Knoten.

Das Skalarprodukt von $A(G)U$ mit $U$ ist die Summe der Grade.
Somit ist
\begin{equation}
\frac{\langle A(G)U,U\rangle}{\langle U,U\rangle}
=
\frac{1}{\langle U,U\rangle}\sum_{v\in V}\deg(v)
=
\frac{1}{n}(d_1+\dots+d_n)
\label{buch:graphen:eqn:AUdavg}
\end{equation}
der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll.

Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar,
die Eigenwerte sind also alle reell.
Es ist ausserdem bekannt, dass der Eigenvektor $f$ zum grössten Eigenwert
$\alpha_{\text{max}}$ von $A(G)$
den Bruch
\[
\frac{\langle A(G)f,f\rangle}{\langle f,f\rangle}
\]
für Vektoren $f\ne 0$ maximiert.
Aus~\eqref{buch:graphen:eqn:AUdavg} folgt damit, dass
\begin{equation}
\overline{d}
\le
\alpha_{\text{max}}
\label{buch:graphen:eqn:dqueramax}
\end{equation}
ist.

In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver
Matrizen vorgestellt, welche einer Reihe interessanter Aussagen
über den betragsgrössten Eigenwert und den zugehörigen Eigenvektor
macht.
Die Adjazenz-Matrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$
ist der grösste Eigenwert, also genau die Grösse, auf die die
Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}
und \label{buch:wahrscheinlichkeit:satz:perron-frobenius2}
anwendbar sind.
Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend
ist damit, dass der Graph zusammenhängend ist.
Im folgenden soll dies daher jeweils angenommen werden.

\begin{satz}
Ist $G$ ein zusammenhänger Graph mit $n$ Knoten und maximalem Grad $d$,
dann gilt
\[
\frac1n\sum_{v\in V} \deg(v) 
=
\overline{d}
\le \alpha_{\text{max}} \le d.
\]
\end{satz}

\begin{proof}[Beweis]
Wir wissen aus \eqref{buch:graphen:eqn:dqueramax} bereits, dass
$\overline{d}\le\alpha_{\text{max}}$ gilt, es bleibt also nur noch
$\alpha_{\text{max}}\le d$ zu beweisen.

Sei $f$ der Eigenvektor zum Eigenwert $\alpha_{\text{max}}$.
Nach Satz~\label{buch:wahrscheinlichkeit:satz:perron-frobenius2}
ist $f$ ein positiver Vektor mit der Eigenschaft $A(G)f=\alpha_{\text{max}}f$.
Der Eigenvektor $f$ ist eine Funktion auf den Knoten des Graphen,
die $v$-Komponente des Vektors $f$ für einen Vertex $v\in V$ ist $f(v)$.
Die Eigenvektoreigenschaft bedeutet $(A(G)f)(v)=\alpha_{\text{max}} f(v)$.
Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ Einsen genau für diejenigen
Knoten $u\in V$, die zu $v$ benachbart sind.
Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist 
\[
(A(G)f)(v)
=
\sum_{u\sim v} f(u).
\]
Die Summe der Komponenten $A(G)f$ kann man erhalten durch Multiplikation
von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen, also
\begin{equation}
\begin{aligned}
\sum_{v\in V}\sum_{u\sim v}f(v)
&=
U^tA(G)f
=
(U^tA(G))f
=
\begin{pmatrix}d_1&d_2&\dots&d_n\end{pmatrix} f
\\
&=
\sum_{v\in V}\deg (v) f(v)
\le
\sum_{v\in V}df(v)
=
d
\sum_{v\in V}f(v).
\end{aligned}
\label{buch:graphen:eqn:sumkomp}
\end{equation}
Andererseits ist $A(G)f=\alpha_{\text{max}}f$, die linke Seite
von~\eqref{buch:graphen:eqn:sumkomp} ist daher
\begin{equation}
\sum_{v\in V}\sum_{u\sim v}f(v)
=
U^tA(G)f
=
\alpha_{\text{max}}
U^tf
=
\alpha_{\text{max}} \sum_{v\in V}f(v).
\label{buch:graphen:eqn:sumkomp2}
\end{equation}
Die Ungleichung~\eqref{buch:graphen:eqn:sumkomp}
und die Gleichung~\eqref{buch:graphen:eqn:sumkomp2} ergeben zusammen
die Ungleichung
\[
\alpha_{\text{max}} \sum_{v\in V}f(v)
\le d\sum_{v\in V}f(v)
\qquad\Rightarrow\qquad
\alpha_{\text{max}} \le d,
\]
da die Summe der Komponenten des positiven Vektors $f$ nicht verschwinden
kann.
Damit ist die Ungleichung bewiesen.
\end{proof}

%
% alpha_max eines Untergraphen
%
\subsection{$\alpha_{\text{max}}$ eines Untergraphen
\label{buch:subsection:alphamax-eines-untergraphen}}
Der grösste Eigenwert $\alpha_{\text{max}}$ ist ein potentieller 
Anwärter für eine bessere Abschätzung der chromatischen Zahl.
Bereits früher wurde bemerkt, dass dies auch bedeutet, dass man 
das Verhalten des grössten Eigenwerts bei einem Übergang zu einem
Untergraphen verstehen muss.

\begin{satz}
\label{buch:graphen:satz:amaxuntergraph}
Sei $G'$ ein echter Untergraph von $G$ mit Adjazenzmatrix $A(G')$ und
grösstem Eigenwert $\alpha_{\text{max}}'=\varrho(A(G'))$, dann ist
$\alpha_{\text{max}}' \le \alpha_{\text{max}}$.
\end{satz}

\begin{proof}[Beweis]
Sei $f'$ der positive Eigenvektor zum Eigenwert $\alpha_{\text{max}}'$
der Matrix $A(G')$.
$f'$ ist definiert auf der Menge $V'$ der Knoten von $G'$.
Aus $f'$ lässt sich ein Vektor $g$ mit den Werten
\[
g(v)
=
\begin{cases}
f'(v)&\qquad v\in V'\\
    0&\qquad\text{sonst}
\end{cases}
\]
konstruieren, der auf ganz $V$ definiert ist.

Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch
$\langle f',f'\rangle = \langle g,g\rangle$.
Die Matrixelemente von $A(G')$ und $A(G)$ auf gemeinsamen Knoten $u,v\in V'$ 
erfüllen $A(G')_{uv}\le A(G)_{uv}$, da jede Kante von $G'$ auch in $G$ ist.
Daher gilt
\[
\langle A(G')f',f'\rangle
\le
\langle A(G)g,g\rangle,
\]
woraus sich die Ungleichung
\[
\alpha_{\text{max}}'
=
\frac{\langle A(G')f',f'\rangle}{\langle f',f'\rangle}
=
\frac{\langle A(G)g,g\rangle}{\langle g,g\rangle}
\le
\alpha_{\text{max}}
\]
ergibt, da $\alpha_{\text{max}}$ das Maximum von
$\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist.
\end{proof}

%
% Der Satz von Wilf
%
\subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf
\label{buch:subsection:chr-und-alpha-max}}
Die in Satz~\ref{buch:graphen:satz:amaxuntergraph} beschriebene
Eigenschaft von $\alpha_{\text{max}}$ beim Übergang zu einem Untergraphen
ermöglich jetzt, eine besser Abschätzung für die chromatische Zahl
zu finden.

\begin{satz}[Wilf]
\label{buch:graphen:satz:wilf}
Sie $G$ ein zusammenhängder Graph und $\alpha_{\text{max}}$ der grösste
Eigenwert seiner Adjazenzmatrix. Dann gilt
\[
\operatorname{chr}G\le \alpha_{\text{max}}+1.
\]
\end{satz}

\begin{proof}[Beweis]
Wie der Satz~\ref{buch:graphen:satz:chrmaxgrad} kann auch der Satz von Wilf
mit Hilfe von vollständiger Induktion über die Anzahl $n$ der Knoten
bewiesen werden.

Ein Graph mit nur einem Knoten hat die $0$-Matrix als Adjazenzmatrix,
der maximale Eigenwert ist $\alpha_{\text{max}}=0$, und tatsächlich reicht
$\alpha_{\text{max}}+1=1$ Farbe, um den einen Knoten einzufärben.

Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits
beweisen.
Wir müssen dann zeigen, dass der Satz dann auch für Graphen mit $n$ Knoten
gilt.

Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus{v}$ der
Untergraph, der entsteht, wenn der Knoten $v$ entfernt wird.
Da $G'$ genau $n-1$ Knoten hat, gilt der Satz von Wilf für $G'$
und daher kann $G'$ mit höchstens
\[
\operatorname{chr}G' \le 1 + \alpha_{\text{max}}'
\]
Farben eingefärbt werden.
Nach Satz~\ref{buch:graphen:satz:amaxuntergraph} ist
$\alpha_{\text{max}}'\le \alpha_{\text{max}}$,
Also kann $G'$ mit höchstens $\alpha_{\text{max}}+1$ Farben eingefärbt werden.

Da $v$ ein Knoten minimalen Grades ist, ist sein Grad
$d(v)\le \overline{d}\le \alpha_{\text{max}}$.
Die Nachbarn von $v$ haben also hächstens $\alpha_{\text{max}}$ verschiedene
Farben, mit einer weiteren Farbe lässt sich also auch $G$ einfärben.
Daraus folgt $\operatorname{chr}G\le \alpha_{\text{max}}+1$.
\end{proof}

\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/nine.pdf}
\caption{Beispiel für einen Graphen, für den der
Satz~\ref{buch:graphen:satz:wilf} von Wilf die bessere
Abschätzung für die chromatische Zahl eines Graphen gibt als der
maximale Grad.
\label{buch:graphen:fig:wilfexample}}
\end{figure}

\begin{beispiel}
Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9
Knoten, daher ist $\overline{d}\le \frac{24}{9}$.
Der maximale Grad ist $4$ und durch explizite Rechnung mit Hilfe zum Beispiel
von Octave ergibt, dass $\alpha_{\text{max}}\approx 2.9565$.
Aus dem Satz von Wilf folgt, dass
$\operatorname{chr}G\le \alpha_{\text{max}}+1$, und daraus ergibt sich
$\operatorname{chr}G\le 3$.
Tatsächlich ist die chromatische Zahl $\operatorname{chr}G=3$, da 
der Graph mindestens ein Dreieck enthält.
Der maximale Grad ist 4, somit gibt der
Satz~\ref{buch:graphen:satz:chrmaxgrad}
die Schranke 
$\operatorname{chr}G\le 4+1=5$
für die chromatische Zahl.
Der Satz von Wilf ist also eine wesentliche Verbesserung, er liefert in
diesem Fall den exakten Wert der chromatischen Zahl.
\end{beispiel}