-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
500 lines (391 loc) · 33.9 KB
/
index.html
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
<!DOCTYPE html>
<html lang="de">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="icon" href="../../favicon.ico">
<title>Graphentheorie - Lernwebsite</title>
<meta name="description" content="Eine interaktive Einführung in die Welt der planaren Graphen mit verständlichen Erklärungen, Verständnis-, Beweis- und Knobelaufgaben.">
<meta name="author" content="Marcus Ding">
<meta name="keywords" content="graph, beweis, Knotengrad, Eulercharateristik, planar, eben dual, handshaking-lemma, euler" />
<!-- Include compressed CSS-Files -->
<link href="https://hpi.de/friedrich/docs/koetzing/units/graphs/css/bootstrap.min.css" rel="stylesheet">
<link href="https://hpi.de/friedrich/docs/koetzing/units/graphs/css/custom.min.css" rel="stylesheet">
<link href="css/graph_style.css" rel="stylesheet">
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body>
<!-- BEGIN: Info Modal -->
<div class="modal fade" id="infoModal" tabindex="-1" role="dialog" aria-labelledby="infoModalLabel" aria-hidden="true">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="infoModalLabel">Informationen</h4>
</div>
<div class="modal-body">
<h5>Deine Fortschrittsanzeige</h5>
<div class="progress">
<div id="fortschrittProgressBar" class="progress-bar progress-bar-success progress-bar-striped active" role="progressbar" aria-valuenow="3" aria-valuemin="0" aria-valuemax="100" style="width: 3%"></div>
</div>
<small>Der Balken beschreibt deinen Fortschritt beim Lösen aller Aufgaben. Schaffst du es, alle Fragen richtig zu beantworten?</small>
<hr>
<h5>Text-Legende</h5><small>
<table class="table table-hover table-condensed">
<thead><tr>
<td><strong>Hervorhebung im Text</strong></td>
<td><strong>Erklärung</strong></td>
</tr></thead>
<tr>
<td><mark>Begriff</mark></td>
<td>Begriffs-Definition/-Einführung</td>
</tr>
<tr>
<td><abbr data-toggle="tooltip" title="Erläuterung">Begriff</abbr></td>
<td>Extra Erläuterung als Popup</td>
</tr>
<tr>
<td><code>Ausdruck</code></td>
<td>Quelltext oder Zeichenkette</td>
</tr>
</table></small>
<hr>
</small>
</div>
</div>
</div>
</div>
<!-- END: Info Modal -->
<!-- BEGIN: Impressum Modal -->
<div class="modal fade" id="impressumModal" tabindex="-1" role="dialog" aria-labelledby="impressumModalLabel" aria-hidden="true">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="impressumModalLabel">Impressum</h4>
</div>
<div class="modal-body">
Für das allgemeine Impressum, siehe <a href="http://hpi.de/impressum.html">HPI-Impressum</a>.
Die vorliegende Lehrwebsite entstand im Rahmen eines Vortrags für das Seminar <i>Diskrete Strukturen</i> am HPI. Als Vorbild, was den Aufbau der Themen, einzelne Definitionen sowie Terminologie angeht, diente Douglas B. Wests <em>Introduction to Graph Theory, 2nd ed.</em>. Sollten etwaige Fehler auftreten oder Fragen bestehen, wenden Sie sich bitte an marcus.ding[at]student.hpi. Als Vorlage dient Dennis Kerzigs Lerneinheit zu Graphen. Im folgenden noch eine kurze Übersicht genutzter Frameworks und Bibliotheken:
<ul style="margin-top: 10px">
<li><a href="http://jquery.com" target="_blank">jQuery</a></li>
<li><a href="http://getbootstrap.com" target="_blank">Bootstrap</a></li>
<li><a href="http://www.mathjax.org" target="_blank">MathJax</a></li>
<li><a href="http://www.lesscss.de" target="_blank">LESS</a></li>
<li><a href="http://notifyjs.com" target="_blank">Notify.js</a></li>
<li><a href="http://js.cytoscape.org" target="_blank">Cytoscape.js</a></li>
</ul>
</div>
</div>
</div>
</div>
<!-- END: Impressum Modal -->
<!-- BEGIN: Main-Container -->
<div class="container">
<!-- Page-Heading -->
<div class="page-header">
<nav><ul class="nav nav-pills pull-right">
<li role="presentation">
<a href="#" title="Hinweise und Legende" data-toggle="modal" data-target="#infoModal"><span class="glyphicon glyphicon-info-sign" aria-hidden="true"></span></a>
</li>
<!--
<li role="presentation">
<a href="#quellenUndMaterial" title="Weiterführendes Material"><span class="glyphicon glyphicon-paperclip" aria-hidden="true"></span></a>
</li>
-->
<li role="presentation">
<a href="#" id="navigationDropdownMenu" title="Schnellnavigation" data-toggle="dropdown" aria-expanded="true"><span class="glyphicon glyphicon-book" aria-hidden="true" ></span></a>
<ul class="dropdown-menu dropdown-menu-right" role="menu" aria-labelledby="navigationDropdownMenu">
<li role="presentation"><a role="menuitem" tabindex="-1" href="#anchor_navigation-1" onclick="closeNavigationDropdown()">1. Was ist ein planarer Graph?</a></li>
<li role="presentation"><a role="menuitem" tabindex="-1" href="#anchor_navigation-2" onclick="closeNavigationDropdown()">2. Der duale Graph</a></li>
<li role="presentation"><a role="menuitem" tabindex="-1" href="#anchor_navigation-3" onclick="closeNavigationDropdown()">3. Die Euler-Charakteristik</a></li>
<li role="presentation" class="divider"></li>
<li role="presentation"><a role="menuitem" tabindex="-1" href="#anchor_navigation-sources" onclick="closeNavigationDropdown()">Weiterführendes Material</a></li>
</ul>
</li>
</ul></nav>
<h2>Planare Graphen <small>- Eine interaktive Einführung</small></h2>
</div>
<!-- Informationen zum Benutzen der Website --><!---->
<div class="alert alert-unobtrusive alert-info alert-dismissible" role="alert" id="firstVisitAlert">
<button type="button" class="close" data-dismiss="alert" aria-label="Close"><span aria-hidden="true">×</span></button>
<small><strong>Zum ersten mal da?</strong> Hinweise zur Benutzung der Website findest du unter dem <span class="glyphicon glyphicon-info-sign" aria-hidden="true"></span>-Symbol rechts oben. Am besten du nutzt zum Einarbeiten in das Themengebiet auch weiterführende Literatur, siehe dazu das <span class="glyphicon glyphicon-book" aria-hidden="true"></span>-Symbol.</small>
</div>
<!-- Abschnitt 1: Einführung, Grundlagen Graph -->
<h4 id="anchor_navigation-1">1. Was ist ein planarer Graph?</h4>
<p>
<div class="thumbnail pull-right" style="width: 250px;">
<div style="position: relative; width: 250px; height: 250px;">
<div id="k4" class="thumbnail-graph full-graph"></div>
<div id="k5" class="thumbnail-graph full-graph hidden-graph"></div>
<div id="k6" class="thumbnail-graph full-graph hidden-graph"></div>
<div id="k2_2" class="thumbnail-graph full-graph hidden-graph"></div>
<div id="k3_3" class="thumbnail-graph full-graph hidden-graph"></div>
<div id="k4_4" class="thumbnail-graph full-graph hidden-graph"></div>
</div>
<div class="caption">
Wähle einen Graphen. Ist er planar? Verschiebe die Knoten.
<!-- Radio-Buttons under class '.picture-switcher' -->
<div class="thumbnail-buttons graph-switcher" data-toggle="buttons">
<label class="btn btn-default btn-sm active">
<input type="radio" name="options" data-target=".full-graph" data-path="k4" autocomplete="off" checked> $$K_4$$
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target=".full-graph" data-path="k5" autocomplete="off"> $$K_5$$
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target=".full-graph" data-path="k6" autocomplete="off"> $$K_6$$
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target=".full-graph" data-path="k2_2" autocomplete="off"> $$K_{2,2}$$
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target=".full-graph" data-path="k3_3" autocomplete="off"> $$K_{3,3}$$
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target=".full-graph" data-path="k4_4" autocomplete="off"> $$K_{4,4}$$
</label>
</div>
</div>
</div>
Planare Graphen sind eine Unterkategorie von Graphen mit speziellen Eigenschaften, die sie zu interessanten Objekten mathematischer Betrachtung machen. Mit relativ einfachen Beweisen und Sätzen kann man erstaunlich mächtige Aussagen treffen. Doch dazu später mehr. Auch konkrete Anwendungen, wie etwa das Routing von PCB-Boards sind auf planare Graphen angewiesen.<br><br>
Wir wissen bereits, was ein Graph ist. Ein planarer Graph ist einfach gesagt ein Graph, welcher überkreuzungsfrei gezeichnet werden kann. Die folgende Definition ist nicht die formale Definition, sondern eine vereinfachte Variante.
<definition><h5>Definition planarer Graph</h5> Ein Graph $$G = (V , E )$$ heißt planar oder plättbar, wenn er eine Einbettung in die Ebene besitzt, so dass sich Kanten nur in einem Knoten schneiden.</definition>
Etwas trennschärfer wird das Konzept mit der Einführung des ebenen Graphen. Diese Unterscheidung wird später noch wichtig.
<definition><h5>Definition ebener Graph</h5> Ein ebener Graph $$G = (V , E )$$ ist eine konkrete, überkreuzungsfreie Einbettung eines planaren Graphen in die Ebene.</definition>
Betrachten wir hierzu ein Beispiel. <abbr data-toggle="tooltip" title="Dies bezeichnet den vollständigen bipartiten Graphen mit 2+2 Knoten.">$$K_{2,2}$$</abbr> ist ein planarer Graph, da es eine ebene Einbettung gibt. Klicke auf die grau eingefärbte Fläche, um die Animation zu starten: <button class="btn btn-micro" onclick="showPlaneExample()">Ebener Graph</button>. Aber es gibt auch eine nicht ebene Einbettung des planaren Graphen $$K_{2,2}$$, die Überkreuzungen enthält: <button class="btn btn-micro" onclick="showNonPlaneExample()">Nicht ebener Graph</button>.
Schauen wir uns <abbr data-toggle="tooltip" title="Dies bezeichnet den vollständigen Graphen mit 4 bzw. 5 usw. Knoten.">$$K_4, K_5, K_6, $$</abbr> <abbr data-toggle="tooltip" title="Dies bezeichnet den vollständigen bipartiten Graphen mit 3+3 bzw. 4+4 usw. Knoten.">$$K_{3,3}, K_{4,4}$$</abbr> an. Welche Graphen sind planar? Können wir einen ebenen Graphen finden, um dies zu zeigen? Wir können die Knoten beliebig verschieben.
Egal was wir versuchen, $$K_5, K_6, K_{3,3}, K_{4,4}$$ lassen sich nicht als ebener Graph darstellen. Es gibt keine überkreuzungsfreie Einbettung in die Ebene. Warum ist das so? Wie können wir das zeigen? Hierzu wird ein cleverer und dennoch einfacher Beweisansatz genutzt. Zeigen wir zuerst, dass $$K_{3,3}$$ nicht planar ist, also keine überkreuzungsfreie Einbettung in die Ebene existiert: <br><br>
$$K_{3,3}$$ enthält einen <abbr data-toggle="tooltip" title="Kreis, der alle Knoten enthält">Hamilton-Kreis $$K$$</abbr>: <button class="btn btn-micro" onclick="showK3_3ProofOne()">$$K$$ anzeigen</button>. Betrachten wir diesen Kreis $$K$$: Er zerteilt die Ebene in zwei Flächen, eine innere und eine äußere. Wir sehen, dass dem Subgraphen der $$K$$ enthält nun noch drei weitere Kanten hinzugefügt werden müssen, um $$K_{3,3}$$ zu enthalten. Wenn wir diese Kanten auf der gleichen Seite zeichnen, überschneiden sie sich alle. Die einzige Möglichkeit eine Überschneidung zu entfernen ist eine Verlagerung einer Kante auf die andere Seite. Doch bei drei im Konflikt stehenden Kanten und nur zwei Seiten ist dies nicht möglich. Also ist $$K_{3,3}$$ nicht planar.<br><br>
<!-- Clearfix beacuse of thumbnail -->
<div class="clearfix"></div>
</p>
<!-- Kontrollfragen: Abschnitt 1 -->
<div class="kontrollfragen panel-group" id="kontrollfragen_01" role="tablist" aria-multiselectable="false">
<!-- Beweisaufgabe 1-2 -->
<div class="panel panel-warning" id="frage_1_2">
<div class="panel-heading" role="tab" id="frage_heading_1_2" data-toggle="collapse" data-parent="#kontrollfragen_01" href="#frage_content_1_2" aria-expanded="false" aria-controls="frage_content_1_2">
<h4 class="panel-title collapsed"><span class="glyphicon glyphicon-edit"></span> Beweisaufgabe 1 - Kannst du's zeigen?</h4>
</div>
<div id="frage_content_1_2" class="panel-collapse collapse" role="tabpanel" aria-labelledby="frage_heading_1_2">
<div class="panel-body proof-question" data-hint-time="1" data-finish-time="2">
<!-- Beweisaufgabe -->
<div class="task">
$$K_5$$ ist nicht planar.
</div>
<!-- Hinweise --->
<div class="hint"> <h5>Hinweise</h5>
Der Beweis für $$K_5$$ funktioniert analog. Auch bei $$K_5$$ musst du nicht lange suchen, um einen <abbr data-toggle="tooltip" title="Kreis, der alle Knoten enthält">Hamilton-Kreis $$K$$</abbr> zu finden: <button class="btn btn-micro" onclick="showK5ProofOne()">Zeigs mir!</button>. Betrachten wir analog diesen Kreis $$K$$: Er zerteilt wieder die Ebene in zwei Flächen. Wir sehen, dass dem Subgraphen der $$K$$ enthält nun noch fünf weitere Kanten hinzugefügt werden müssen, um $$K_5$$ zu enthalten.
</div>
<!-- Musterlösung -->
<div class="solution"> <h5>Musterlösung</h5>
Wir fangen mit einem Kreis an: <button class="btn btn-micro" onclick="showK5ProofOne()">Zeigs mir!</button>. Wenn ich diese Kanten auf der gleichen Seite zeichne, überschneiden sie sich in einer Weise, dass sie durch Umverlegung unmöglich überkreuzungsfrei eingezeichnet werden können. Betrachten wir dazu den Konflikt zwischen $$\{c,e\}$$ und $$\{d,b\}$$. Dieser kann nur auf zwei Arten aufgelöst werden (Fallunterscheidung):<br><br>
<b>Fall 1:</b> Wir zeichnen $$\{c,e\}$$ aussen. <button class="btn btn-micro" onclick="showK5ProofTwo()">Zeigs mir!</button><br>
$$\Rightarrow$$ Wir können den Konflikt von $$\{b,d\}$$ u. $$\{a,c\}$$ <button class="btn btn-micro" onclick="showK5ProofThree()">Zeigs mir!</button> nur lösen, indem wir $$\{a,c\}$$ außen zeichnen, da $$\{b,d\}$$ mit dem nach außen verlagerten $$\{c,e\}$$ konfligiert. <button class="btn btn-micro" onclick="showK5ProofFour()">Zeigs mir!</button><br>
$$\Rightarrow$$ Der nun noch bestehende Konflikt zwischen $$\{a,d\}$$ u. $$\{b,e\}$$ ist nicht aufzulösen, da nun beide Kanten mit den außen gezeichneten Kanten konfligieren. <button class="btn btn-micro" onclick="showK5ProofFive()">Zeigs mir!</button><br>
$$\Rightarrow$$ Konflikt $$\{a,d\}$$ u. $$\{b,e\}$$ kann nicht aufgelöst werden.<br><br>
<b>Fall 2:</b> Wir zeichnen $$\{d,b\}$$ aussen.<br>
$$\Rightarrow$$ Fall aufgrund von Symmetrie von $$K_5$$ analog zu Fall 1, nur dass hierbei der Graph um $$72$$ Grad im Uhrzeigersinn gedreht ist und die Kanten entsprechend andere sind, da sie nun relativ zu $$\{d,b\}$$ liegen. <button class="btn btn-micro" onclick="showK5ProofSix()">Zeigs mir!</button><br>
$$\Rightarrow$$ Konflikt $$\{a,d\}$$ u. $$\{c,e\}$$ kann nicht aufgelöst werden.<br><br>
Fall 1 u. Fall 2. $$\Rightarrow$$ Wir können den Konflikt zwischen $$\{c,e\}$$ und $$\{d,b\}$$ nicht auflösen ohne neue unlösbare Konflikte zu erzeugen.<br>
$$\Rightarrow$$ $$K_5$$ hat keine überkreuzungsfreie Einbettung<br>
$$\Rightarrow$$ $$K_5$$ ist nicht planar
</div>
</div>
</div>
</div>
<!-- Beweisaufgabe 1-2 -->
<div class="panel panel-warning" id="frage_1_3">
<div class="panel-heading" role="tab" id="frage_heading_1_3" data-toggle="collapse" data-parent="#kontrollfragen_01" href="#frage_content_1_3" aria-expanded="false" aria-controls="frage_content_1_3">
<h4 class="panel-title collapsed"><span class="glyphicon glyphicon-edit"></span> Beweisaufgabe 2 - Kannst du's zeigen?</h4>
</div>
<div id="frage_content_1_3" class="panel-collapse collapse" role="tabpanel" aria-labelledby="frage_heading_1_3">
<div class="panel-body proof-question" data-hint-time="1" data-finish-time="2">
<!-- Beweisaufgabe -->
<div class="task">
Warum gilt, dass $$K_{n,m}$$ für $$n,m >= 3$$ und $$K_l$$ für $$l>=5$$ nicht planar sind?
</div>
<!-- Hinweise --->
<div class="hint"> <h5>Hinweise</h5>
Wie hängen $$K_{n,m}$$ und $$K_{3,3}$$ bzw. $$K_l$$ und $$K_5$$ zusammen?
</div>
<!-- Musterlösung -->
<div class="solution"> <h5>Musterlösung</h5>
$$K_{n,m}$$ sowie $$K_l$$ gehen durch Hinzufügung von Kanten sowie Knoten aus $$K_{3,3}$$ bzw. $$K_5$$ hervor. Somit werden die bestehenden Konflikte nicht aufgelöst. Der Graph ist somit weiterhin nicht planar.
</div>
</div>
</div>
</div>
</div>
<hr>
<!----------------------------------->
<!-- Abschnitt 2: Der duale Graph -->
<h4 id="anchor_navigation-2">2. Der duale Graph</h4>
<div class="thumbnail pull-right" style="width: 250px;">
<div style="position: relative; width: 250px; height: 250px;">
<div id="originGraph" class="thumbnail-graph dual-graph"></div>
<div id="dualGraph" class="thumbnail-graph dual-graph hidden-graph"></div>
</div>
<div class="caption">
Hier wird der Ausgangsgraph und später auch der zugehörige duale Graph eingezeichnet.
<!-- Radio-Buttons under class '.picture-switcher' -->
<div class="thumbnail-buttons dual-graph-switcher" data-toggle="buttons" id="dual-graph-switcher">
<label class="btn btn-default btn-sm active">
<input type="radio" name="options" data-target=".dual-graph" data-path="originGraph" autocomplete="off" checked> Graph
</label>
<label class="btn btn-default btn-sm hidden" id="dual-graph-button">
<input type="radio" name="options" data-target=".dual-graph" data-path="dualGraph" autocomplete="off"> Dualer Graph
</label>
</div>
</div>
</div>
Was mag nur ein dualer Graph sein? Wir werden ihn später verwenden, um ein Lemma zu zeigen. Doch bevor wir die zugehörige Definition verstehen, müssen wir zuerst definieren, was eine Facette bzw. Fläche eines ebenen Graphen ist.
<definition><h5>Definition Facette</h5> In einem ebenen Graph bezeichnet Facette (Fläche) einen von Kanten eingeschlossenen Bereich. Ebenfalls zählt hierzu die sog. äußere Facette, welche den Graphen umgibt.</definition>
Anstelle einer normalen Definition, zeigen wir an Hand eines Beispiels, wie man den dualen Graphen zu einem gegebenen planaren Graphen zeichnet. Betrachten wir den rechten Graphen, wie sieht der zugehörige duale Graph aus? Er würde wie folgt eingezeichnet: Als erstes zeichnen wir in jede Facette des Graphen einen neuen Knoten: <button class="btn btn-micro" onclick="showDualExampleOne();">Einzeichnen</button>. Dieser Graph hat also vier Facetten. Als nächstes wird für jeden eine Fläche repräsentierenden Knoten, wenn diese Fläche an eine andere Fläche angrenzt, eine entsprechende Kante zwischen den jeweiligen Knoten eingezeichnet: <button class="btn btn-micro" onclick="showDualExampleTwo()">Einzeichnen</button>. Nun sollte uns auch die formalere Definition verständlicher sein:
<definition><h5>Definition Dualer Graph</h5> Der zum ebenen Graphen $$G = (V , E )$$ ebenfalls ebene duale Graph $$G' = (V',E')$$ entsteht, indem in jeder Facette des Graphen $$G$$ neue Knoten $$v'$$ hinzugefügt werden und für jede Kante $$e \in E$$ eine neue Kante $$e'$$ erstellt wird, die die $$v'$$ der beiden angrenzenden Facetten verbindet.</definition>
Jede Facette besitzt eine Länge, die wie folgt definiert wird:
<definition><h5>Definition (Länge von Facetten)</h5>Die Länge einer Facette eines ebenen Graphen entspricht der Gradzahl des entsprechenden Knotens des zugehörigen dualen Graphen.</definition>
Wir bezeichnen die Facetten in obigem Beispiel der Einfachheit halber einfach mit dem Namen des korrespondierenden Knoten. In unserem Beispiel hat also die Facette $$a'$$ die Länge 2, $$b'$$ die Länge 3 usw..
<!-- Clearfix beacuse of thumbnail -->
<div class="clearfix"></div>
</p>
<!-- Kontrollfragen: Abschnitt 2 -->
<div class="kontrollfragen panel-group" id="kontrollfragen_02" role="tablist" aria-multiselectable="false">
<!-- Beweisaufgabe 2-2 -->
<div class="panel panel-warning" id="frage_2_2">
<div class="panel-heading" role="tab" id="frage_heading_2_2" data-toggle="collapse" data-parent="#kontrollfragen_02" href="#frage_content_2_2" aria-expanded="false" aria-controls="frage_content_2_2">
<h4 class="panel-title collapsed"><span class="glyphicon glyphicon-edit"></span> Beweisaufgabe</h4>
</div>
<div id="frage_content_2_2" class="panel-collapse collapse" role="tabpanel" aria-labelledby="frage_heading_2_2">
<div class="panel-body proof-question" data-hint-time="1" data-finish-time="2">
<!-- Beweisaufgabe -->
<div class="task">
Beweise das Duale Handshaking-Lemma: Sei $$l(F_i)$$ die Länge der Facette $$F_i$$ eines ebenen Graphen $$G$$, so gilt: $$\sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E (G )|$$
</div>
<!-- Hinweise --->
<div class="hint"> <h5>Hinweise</h5>
Betrachte das Handshaking-Lemma: $$\sum\limits_{v \in V(G)} deg(v) = 2 · |E(G)|$$, wie hängt es mit dem dualen Graphen zusammen?
</div>
<!-- Musterlösung -->
<div class="solution"> <h5>Musterlösung</h5>
Für einen Graphen $$G$$ gilt das Handshakinglemma: $$\underset{v \in V(G)}{\sum} deg(v) = 2 · |E(G)|$$<br><br>
Sei $$G^*$$ der duale Graph zu $$G$$<br><br>
$$\Rightarrow \sum\limits_{v \in V(G^*)} deg(v) = 2 · |E(G^*)|$$<br>
$$\Leftrightarrow \sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E(G^*)|$$<br>
$$\Leftrightarrow \sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E(G)|$$<br>
q.e.d.
</div>
</div>
</div>
</div>
</div>
<hr>
<!-- Abschnitt 3: ie Euler-Charakteristik -->
<h4 id="anchor_navigation-3">3. Die Euler-Charakteristik</h4>
<div class="thumbnail pull-right" style="width: 250px; height: 404px;">
<img id="graph-kreise-pfade-img" src="img/k6_blank.png">
<div class="caption">
Wir haben zuvor gezeigt, dass $$K_6$$ und $$K_7$$ nicht planar sind. Dies gilt jedoch nicht für $$K_6$$ in der <abbr data-toggle="tooltip" title="Ein Vergleich wäre die Ebene bei Snake. Oder die Innenfläche einer Kugel.">projektiven Ebene</abbr> oder etwa $$K_7$$ im <abbr data-toggle="tooltip" title="Ähnlich Innenseite eines Donuts."><a href="https://de.wikipedia.org/wiki/Torus">Torus</a>.
<!-- Radio-Buttons under class '.picture-switcher' -->
<div class="thumbnail-buttons picture-switcher" data-toggle="buttons">
<label class="btn btn-default btn-sm active">
<input type="radio" name="options" data-target="#graph-kreise-pfade-img" data-path="img/k6_blank.png" autocomplete="off">projektive Ebene
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target="#graph-kreise-pfade-img" data-path="img/k6.png" autocomplete="off">$$K_6$$ planar
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target="#graph-kreise-pfade-img" data-path="img/k7_blank.png" autocomplete="off" checked="">Torus
</label>
<label class="btn btn-default btn-sm">
<input type="radio" name="options" data-target="#graph-kreise-pfade-img" data-path="img/k7.png" autocomplete="off">$$K_7$$ planar
</label>
</div>
</div>
</div>
Eine für viele Beweise sehr hilfreiche Eigenschaft planarer Graphen ist, dass alle ebenen Einbettungen dieser die von Leonhard Euler 1750 (wieder-)entdeckte Formel erfüllen.
<definition><h5>Definition Euler-Charakteristik (f. planare Graphen)</h5>Für einen zusammenhängenden, ebenen Graphen $$G$$ mit $$n$$ Knoten, $$e$$ Kanten und $$f$$ Facetten gilt: $$n − e + f = 2$$</definition>
Der Beweis der Eulercharakteristik für einen ebene Graphen $$G$$ erfolgt per Induktion über die Kantenzahl $$e$$. Im Folgenden ist eine Beweisskizze dargestellt.<br><br>
IA: ($$e=0$$)<br><br>
Da der Graph zusammenhängend ist folgt hieraus, dass die Knotenzahl $$n=1$$ und somit die Facettenzahl $$f=1$$ ist. Also gilt $$n - e + f = 1 - 0 + 1 = 2$$ und somit die Euler-Charakteristik.<br><br>
IS: ($$e>=1$$)<br><br>
Ist $$G$$ ein Baum, dann ist $$e=n-1$$ und $$f=1$$ und somit gilt $$n - e + f = n - (n-1) + 1 = n-n+1+1 = 2$$. Ist $$G$$ kein Baum, so sei $$k$$ eine Kante, die auf einem Kreis von $$G$$ liegt. Graph $$G$$ muss einen Kreis enthalten, da er sonst nach Definition ein Baum wäre. Betrachte $$G' = G-k$$: Der zusammenhängende, ebene Graph $$G'$$ hat nun $$n$$ Knoten, $$e-1$$ Kanten und $$f-1$$ Facetten. Der Zusammenhang bleibt erhalten, da lediglich eine Kante aus einem Kreis entfernt wird und die durch diese Kante verbundenen Knoten über den Rest der Kanten im vorherigen Kreis weiterhin mit allen Knoten verbunden bleiben. Der Graph ist weiterhin eben, da dem Graphen lediglich eine Kante entfernt wird, also keine neue Kante eine Überkreuzung erzwingen kann. Die Facettenzahl reduziert sich um $$1$$, da das Entfernen der Kante einen Kreis öffnet und somit die vorherig von ihm eingeschlossene Facette nicht mehr besteht. Nach Induktionsvoraussetzung gilt für $$G'$$ die Euler-Charakteristik, also $$n - (e-1) + (f-1) = 2 \Leftrightarrow n - e + f = 2$$. Also gilt die Euler-Charakteristik auch für $$G$$.
<!-- Kontrollfragen: Abschnitt 3 -->
<div class="kontrollfragen panel-group" id="kontrollfragen_03" role="tablist" aria-multiselectable="false">
<!-- Beweisaufgabe 3-1 -->
<div class="panel panel-warning" id="frage_3_1">
<div class="panel-heading" role="tab" id="frage_heading_3_1" data-toggle="collapse" data-parent="#kontrollfragen_03" href="#frage_content_3_1" aria-expanded="false" aria-controls="frage_content_3_1">
<h4 class="panel-title collapsed"><span class="glyphicon glyphicon-edit"></span> Beweisaufgabe 3 - Kannst du's zeigen?</h4>
</div>
<div id="frage_content_3_1" class="panel-collapse collapse" role="tabpanel" aria-labelledby="frage_heading_3_1">
<div class="panel-body proof-question" data-hint-time="1" data-finish-time="2">
<!-- Beweisaufgabe -->
<div class="task">
Sei $$G$$ ein einfacher, ebener Graph mit mindestens drei Knoten, dann gilt $$|E (G )| \leq 3|V (G )| − 6$$.
</div>
<!-- Hinweise --->
<div class="hint"> <h5>Hinweise</h5>
Nutze das duale Handshake-Lemma: $$\sum l(F_i ) = 2 · |E (G )|$$, wobei $$l(F_i)$$ die Länge der Facette $$F_i$$ bezeichnet.
</div>
<!-- Musterlösung -->
<div class="solution"> <h5>Musterlösung</h5>
Wir wollen zeigen, dass $$e \leq 3n - 6$$. <br><br>
Aus $$\sum l(F_i ) = 2 · |E (G )|$$ folgt $$3 f \leq 2 · |E (G )|$$, da in einem einfachen Graphen – also ohne Mehrfachkanten – jede Facette von Mindestens 3 Kanten umschlossen wird.<br><br>
Betrachten wir nun die Eulercharakteristik und formen diese äquivalent um, um $$f$$ zu ersetzen: $$n - e + f = 2 \Leftrightarrow 3n - 3e + f = 6$$. Setzen wir nun obige Ungleichung ein: $$6 = 3n - 3e + 3f \leq 3n - 3e + 2e$$<br><br>
$$\Rightarrow 6 \leq 3n - 3e + 2e \Leftrightarrow e \leq 3n - 6$$.<br><br>
Somit haben wir mit Hilfe der Eulercharakteristik gezeigt, dass in jedem planaren Graphen die Kantenzahl durch die Knotenzahl linear beschränkt wird (anders als bei nichtplanaren Graphen).
</div>
</div>
</div>
</div>
</div>
<div class="content-resources-divider">
<hr>
Ende des Lehrinhalts, unten findest du weiterführendes Material
</div>
<!------------------------------------------------------->
<!-- Abschnitt I: Quellen und Weiterführendes Material -->
<h3 id="anchor_navigation-sources">I. Quellen und weiterführendes Material</h3>
<p>
Neben zahlreichen Wikipedia-Artikeln aus dem Themengebiet der <a href="http://de.wikipedia.org/wiki/Graphentheorie" target="_blank">Graphentheorie</a> existieren weitere Ressourcen, die ich zum tiefergehenden Studium besonders empfehle:
<dl>
<dt><a href="http://www.esi2.us.es/~mbilbao/pdffiles/DiestelGT.pdf" target="_blank">R. Diestel - Graphentheorie (Springer, 2000)</a></dt>
<dd>Standardwerk mit allen Termini, wichtigen Beweisen und Aufgaben.</dd>
<dt><a href="https://www.amazon.de/Introduction-Graph-Theory-Featured-Titles/dp/0130144002" target="_blank">Douglas B. Wests - Introduction to Graph Theory (Prentice Hall, 2001)</a></dt>
<dd>Standardwerk (Englisch) mit allen Termini, wichtigen Beweisen und Aufgaben.</dd>
</dl>
<!-- Clearfix beacuse of thumbnail -->
<div class="clearfix"></div>
</p>
<!-- BEGIN: Footer -->
<footer class="footer">
<p>© <a href="http://github.com/kryptokommunist" target="_blank">Marcus Ding</a></p>
<span class="impressum"><a href="#" data-toggle="modal" data-target="#impressumModal">Impressum</a></span>
</footer>
</div> <!-- END: Main-Container -->
<!-- Include Javascript-Resources -->
<script src="https://hpi.de/friedrich/docs/koetzing/units/graphs/js/jquery-2.1.3.min.js"></script>
<script src="https://hpi.de/friedrich/docs/koetzing/units/graphs/js/bootstrap.min.js"></script>
<script src="js/cytoscape.min.js"></script>
<script src="js/graph_code.js"></script>
<!-- Include MathJax via CDN and configure -->
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"> </script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config ( { tex2jax: {
inlineMath: [['$$','$$'], ['??','??']],
displayMath: [ ['$$$','$$$'], ['@@', '@@']],
} } );
</script>
<!-- Underscore -->
<!--<script src="js/underscore-min.js"></script>-->
<!-- Notify.js -->
<script src="https://hpi.de/friedrich/docs/koetzing/units/graphs/js//notify.min.js"></script>
<!-- Custom JavaScript -->
<script src="https://hpi.de/friedrich/docs/koetzing/units/graphs/js/custom.js"></script>
</body>
</html>