WEBVTT

00:00.000 --> 00:03.380
Zuerst vor Ankündigung, wir haben gesehen, dass Sie offenbar

00:03.380 --> 00:06.080
Schwierigkeiten mit Chomsky-Grammatiken haben.

00:06.640 --> 00:09.420
Daher wird der Herr Gilhausen noch eine extra Übung zu diesem Zweck

00:09.420 --> 00:13.260
veranstalten, um da sämtliche Fragen zu beantworten.

00:15.400 --> 00:19.360
Wir waren stehen geblieben bei Relationen und Graphen.

00:20.240 --> 00:24.820
Und die Aussichten heute sind trübe, wie das bei da draußen.

00:26.380 --> 00:29.620
Ich habe jede Menge Stoff, der zum Auswendiglernen ist.

00:30.860 --> 00:34.020
Relativ wenig Sachen, bei denen man Einsicht zeigen muss, die sind

00:34.020 --> 00:34.940
dann allerdings schwierig.

00:35.800 --> 00:39.580
Aber überwiegend ist das also alles Stoff, den man in sich aufnehmen

00:39.580 --> 00:44.320
muss und bei dem sich dann hinterher herausstellt, dass die ganzen

00:44.320 --> 00:48.720
Begriffe, die man dabei lernt, mit der Zeit plastische Bedeutung

00:48.720 --> 00:50.800
bekommen und vielfache Anwendung haben.

00:51.680 --> 00:57.340
Zunächst waren wir stehen geblieben bei Graphen und hatten uns also

00:57.340 --> 01:02.960
mit dem Begriff Eingangsgrad und Ausgangsgrad von Ecken in gerichteten

01:02.960 --> 01:06.520
Graphen beschäftigt, nämlich wie viele Kanten gehen rein, wie viele

01:06.520 --> 01:07.540
Kanten gehen raus.

01:08.040 --> 01:11.500
Und haben dann festgestellt, bei ungerichteten Graphen müssen diese

01:11.500 --> 01:16.700
Zahlen identisch sein, weil jede Ecke, Kante, die rausgeht, natürlich

01:16.700 --> 01:18.700
auch eine Kante ist, die reingeht.

01:18.700 --> 01:23.800
Und daher sprechen wir an dieser Stelle nur vom Grad der Ecke und

01:23.800 --> 01:25.560
nicht mehr von Eingangs- und Ausgangsgrad.

01:26.940 --> 01:31.320
Und an dem Beispiel, was ich jetzt nicht weiter vorführe, hatten wir

01:31.320 --> 01:32.100
das schon gesehen.

01:35.180 --> 01:37.800
Dann gibt es den Begriff des vollständigen Graphen.

01:38.900 --> 01:45.080
Das ist ein Graph, bei dem jede Ecke mit jeder anderen verbunden ist.

01:48.540 --> 02:00.080
Der figuriert in der Literatur unter dem Namen eines K mit Index n,

02:00.140 --> 02:01.180
wenn er n Ecken hat.

02:02.320 --> 02:05.660
Und die Frage lautet, wie viele Kanten hat denn dieser Graph?

02:13.300 --> 02:14.520
Und wie rechne ich das aus?

02:18.600 --> 02:19.580
2n, sagt er.

02:20.880 --> 02:23.180
Da bin ich nicht so ganz zufrieden.

02:26.660 --> 02:28.800
n mal n minus 1 halbe.

02:33.240 --> 02:38.920
Begründung, von jeder Ecke, die ich hier habe, gehen n minus 1 Kanten

02:38.920 --> 02:42.340
aus, nämlich zu jeder anderen Ecke.

02:44.320 --> 02:48.860
Und da ich insgesamt n Ecken habe, habe ich also zunächst mal n mal n

02:48.860 --> 02:49.640
minus 1.

02:51.080 --> 02:54.220
Aber jetzt habe ich ganz offensichtlich jede Kante doppelt gezählt.

02:55.600 --> 03:00.180
Nämlich ich habe gezählt, diese Kante hier beispielsweise geht von

03:00.180 --> 03:03.420
dieser Ecke aus, und dann habe ich sie aber auch bei dieser Ecke

03:03.420 --> 03:03.960
gezählt.

03:04.960 --> 03:06.700
Also ich habe jede Kante doppelt gezählt.

03:07.440 --> 03:10.280
Also muss ich n mal n minus 1 noch halbieren.

03:13.340 --> 03:16.100
Auf jeden Fall merken wir uns, die Zahl ist quadratisch.

03:18.470 --> 03:22.730
Wir werden spezifisch auf den K5 hinterher nochmal zurückkommen.

03:26.060 --> 03:31.160
Wenn ich einen Graphen habe, mit mehreren Ecken,

03:38.360 --> 03:43.340
dann kann ich, je nachdem wie die Kantenlage ist, natürlich jetzt

03:43.340 --> 03:50.540
sagen, nicht nur diese Ecke hier ist mit dieser Ecke verbunden,

03:50.540 --> 03:53.800
sondern da gibt es unter Umständen noch einen Weg, der ein zweiter

03:53.800 --> 03:54.800
geht zu dieser Ecke.

03:58.850 --> 04:03.450
Ich kann also einzelne Kanten miteinander verketten, um eine Übersicht

04:03.450 --> 04:09.070
zu gewinnen, wohin kannst du überall kommen, wenn du einzelnen Kanten

04:09.070 --> 04:11.050
von einer Ecke zur nächsten folgst.

04:11.470 --> 04:17.910
Es kann auch mehrere Wege geben von dieser Ausgangsecke zu dieser

04:17.910 --> 04:18.250
Ecke.

04:18.250 --> 04:24.010
Nämlich wenn zum Beispiel auch noch diese Kanten existieren sollten.

04:24.990 --> 04:28.190
Und das führt insgesamt zum Begriff des Weges.

04:28.870 --> 04:34.990
Ein Weg der Länge n ist eine Folge von Ecken, E0 bis En, mit der

04:34.990 --> 04:40.950
Eigenschaft, dass jeweils eine Ecke, Ei, mit der darauffolgenden Ecke

04:40.950 --> 04:43.090
durch eine Kante verbunden ist.

04:43.090 --> 04:49.570
Wir sagen dann oft auch, wenn es solche Wege gibt, En ist erreichbar

04:49.570 --> 04:50.210
von E0.

04:51.570 --> 04:55.630
Und selbstverständlich, wenn es also einen solchen Weg gibt von E0

04:55.630 --> 05:10.110
nach En, dann ist auch E0 bis En-1 ein Weg und E0 bis En-2 ist ein Weg

05:10.110 --> 05:10.850
und so weiter.

05:10.850 --> 05:14.870
Also alle Teile sind ebenfalls Wege.

05:15.790 --> 05:18.930
Und natürlich auch von E1 nach En gibt es dann also einen Weg.

05:22.190 --> 05:26.070
Solche Wege könnten unter Umständen im Kreis herum führen.

05:28.950 --> 05:35.150
Nämlich dann, wenn die letzte Ecke des Weges, En, dieselbe Ecke ist

05:35.150 --> 05:36.990
wie die Ausgangsecke, E0.

05:36.990 --> 05:41.350
Dann führt der Weg im Kreis herum und dann sprechen wir in einem

05:41.350 --> 05:44.290
gerichteten Graphen von einem Zyklus.

05:45.450 --> 05:49.550
In ungerichteten Graphen finden Sie gelegentlich auch die Bezeichnung

05:49.550 --> 05:54.250
Zyklus, aber häufiger finden Sie dabei die Bezeichnung Kreis.

05:55.830 --> 06:00.430
Denn selbstverständlich den Begriff des Weges können Sie auch

06:00.430 --> 06:03.470
übertragen auf ungerichtete Graphen.

06:04.690 --> 06:09.870
Hier unten sind eine Reihe von Beispielen aufgeführt, von Wegen, da

06:09.870 --> 06:12.910
gehe ich jetzt nicht weiter darauf ein.

06:13.750 --> 06:21.370
Wichtig ist, sich diesen Weg nochmal anzusehen und die Länge und die

06:21.370 --> 06:23.290
Anzahl der Ecken in Relation zu setzen.

06:24.150 --> 06:31.050
Der Weg hat N plus 1 Ecken, gezählt von 0 bis N in diesem Beispiel.

06:32.850 --> 06:38.070
Aber es sind nur N Kanten, also die Anzahl der Kanten ist 1 geringer

06:38.070 --> 06:40.150
als die Anzahl der Ecken des Weges.

06:40.670 --> 06:45.130
Und wir rechnen dann also als Länge N die Anzahl der Kanten, nicht die

06:45.130 --> 06:45.830
Anzahl der Ecken.

06:46.990 --> 06:54.910
Das ist eine Quelle häufiger Zählfehler und in der Informatik ist das

06:54.910 --> 06:57.150
als das Gattenzaun-Problem bekannt.

06:57.150 --> 06:59.790
Wenn Sie also einen schönen Gattenzaun haben,

07:07.550 --> 07:10.910
dann ist die Frage, wie viele Pfähle hat das Ding?

07:11.030 --> 07:15.030
Also in diesem Beispiel 5 und wie viele Zwischenräume gibt es

07:15.030 --> 07:15.490
dazwischen?

07:15.890 --> 07:16.250
4.

07:19.850 --> 07:23.050
Und es ist nicht andersherum und die Anzahl der Pfähle ist nicht

07:23.050 --> 07:24.810
gleich der Anzahl der Zwischenräume.

07:25.310 --> 07:29.610
Das ist ein häufiger Rechenfehler, auch beim praktischen

07:29.610 --> 07:30.250
Programmieren.

07:31.850 --> 07:36.070
Und wenn man als so verdacht trägt, dass man solche Rechenfehler

07:36.070 --> 07:42.430
macht, dann ist es zweckmäßig N gleich 1 oder maximal 2 zu setzen.

07:42.830 --> 07:44.390
Dann kann man es noch abzählen.

07:46.670 --> 07:51.350
Und das ist ein Ratschlag, wenn Sie Programme vor sich haben, die aus

07:51.350 --> 07:53.850
irgendeinem Grunde nicht ganz so funktionieren, wie Sie wollen.

07:53.850 --> 07:57.930
Dann schauen Sie sich erst mal Ihre Indizes an und stellen fest, dass

07:57.930 --> 08:01.250
Sie unter Umständen Zählfehler drin haben könnten.

08:01.750 --> 08:05.610
Und dann versuchen Sie es erst mal mit N gleich 1 oder N gleich 2, wo

08:05.610 --> 08:09.750
Sie es genau abzählen können, um festzustellen, ob da solch ein

08:09.750 --> 08:11.170
Gattenzaun -Problem vorliegt.

08:17.160 --> 08:23.280
Neben den Wegen kann ich noch einige andere Variationen betrachten.

08:24.160 --> 08:31.360
Zunächst mal, ich habe bisher unterstellt, dass die Ecken verschieden

08:31.360 --> 08:31.560
sind.

08:31.680 --> 08:33.420
Zumindest habe ich das Gegenteil nicht gesagt.

08:34.460 --> 08:38.860
Ich kann selbstverständlich auch Graphen betrachten, bei denen es

08:38.860 --> 08:43.640
Kanten gibt, die von einer Ecke, wie zum Beispiel C hier, rundum

08:43.640 --> 08:44.800
führen wie der Nachtsee.

08:47.120 --> 08:52.540
Das ist ein Zyklus, beziehungsweise ein Kreis, wenn ich es ungerichtet

08:52.540 --> 08:53.080
betrachte.

08:55.400 --> 08:57.100
Eingangsecke und Ausgangsecke.

08:58.620 --> 09:01.500
Und solch ein Zyklus hat also dementsprechend immer die Länge 1.

09:04.340 --> 09:10.820
Übersetzt in Relationen theoretische Aussachen, heißt Schlinge der

09:10.820 --> 09:17.960
Länge 1 An dieser Ecke ist zunächst einmal die Relation reflexiv.

09:19.680 --> 09:24.140
X, in diesem Fall C, steht in Beziehung mit sich selbst, wie ich sehe,

09:24.320 --> 09:26.400
weil ich da direkt wieder nach C komme.

09:26.980 --> 09:30.900
Die Relation ist genau dann reflexiv, wenn jede Ecke diese Eigenschaft

09:30.900 --> 09:31.280
hat.

09:35.400 --> 09:38.460
Es könnten also einzelne Ecken die Eigenschaften haben und dann ist

09:38.460 --> 09:42.720
die darüber hinausgehende Frage, haben alle Ecken diese Eigenschaften?

09:42.720 --> 09:46.320
Dann nenne ich die Relation reflexiv.

09:46.820 --> 09:50.120
Beim Graph habe ich keine solche Bezeichnung.

09:52.340 --> 09:55.820
Ich rede dann nur einfach davon, dass ich an jeder Ecke eine Schlinge

09:55.820 --> 09:56.080
habe.

09:58.000 --> 10:03.520
Wenn ich jetzt diesen Graphen mit oder ohne die Schlingen nochmal

10:03.520 --> 10:08.420
betrachte, wir kennen das Beispiel ja schon, dann kann ich den Begriff

10:08.420 --> 10:10.560
Weg noch verallgemeinern.

10:10.560 --> 10:15.360
Und zwar zunächst einmal zum Begriff des Semiwegs, das ist eine Folge

10:15.360 --> 10:22.080
von Ecken, mit der Eigenschaft, dass ich im gerichteten Graph immer

10:22.080 --> 10:26.900
von der einen Ecke zur anderen komme oder umgekehrt.

10:27.680 --> 10:35.480
Also beispielsweise, Sie kommen hier ganz offensichtlich von C nach B

10:35.480 --> 10:41.660
auf einem Semiweg, in dem Sie beispielsweise sagen, ja, du kannst ja

10:41.660 --> 10:47.360
auch die umgekehrte Richtung gehen, also von C nach B direkt, oder du

10:47.360 --> 10:51.800
könntest von C auf den umgekehrten Weg nach A gehen und dann von A

10:51.800 --> 10:52.280
nach B.

10:54.260 --> 10:55.740
Beide sind Semiwege.

10:56.710 --> 11:02.000
Wenn ich die Pfeile weglasse und denselben Graphen ungerichtet

11:02.000 --> 11:07.160
betrachte, dann gibt es offensichtlich den Begriff des Semiwegs nicht.

11:07.760 --> 11:10.160
Denn dann kann ich ja jede Kante in jede Richtung gehen.

11:13.180 --> 11:20.160
Und das bedeutet, dass ich dann jeden solchen Semiweg im gerichteten

11:20.160 --> 11:24.120
Graphen direkt als Weg auffassen kann, im ungerichteten Graphen.

11:24.920 --> 11:29.340
Wir merken uns also, im gerichteten Graphen gibt es die Unterscheidung

11:29.340 --> 11:31.180
zwischen Weg und Semiweg.

11:33.020 --> 11:35.900
Und im ungerichteten Graphen gibt es diese Unterscheidung nicht,

11:36.020 --> 11:37.700
sondern beide Begriffe fallen einfach zusammen.

11:39.060 --> 11:42.120
Umgekehrt, wenn Sie wissen, was ein Weg in einem ungerichteten Graphen

11:42.120 --> 11:47.380
ist und Schwierigkeiten haben im gerichteten Graphen, dann sagen Sie

11:47.380 --> 11:51.060
ja alles, was im ungerichteten Graphen als Weg zählt.

11:51.840 --> 11:54.820
Das ist mindestens ein Semiweg im gerichteten Graphen.

11:55.080 --> 11:55.720
Sie hatten eine Frage?

12:02.640 --> 12:07.700
Sie dürfen, so steht es hier, gegen die Pfeilrichtung gehen im

12:07.700 --> 12:08.280
Semiweg.

12:11.140 --> 12:16.440
Entweder können Sie von EI nach IEI plus 1 kommen oder die Umkehrung.

12:19.200 --> 12:22.820
Und das heißt, Sie dürfen also auf dem Semiweg von C nach A gehen,

12:22.940 --> 12:25.780
obwohl es da keinen gerechten Weg gibt.

12:26.260 --> 12:27.960
Und Sie können von A nach B gehen.

12:29.200 --> 12:32.340
Beides zusammen ist ein Semiweg, aber C nach A ist auch schon ein

12:32.340 --> 12:32.840
Semiweg.

12:34.780 --> 12:35.440
Noch Fragen?

12:42.980 --> 12:49.560
Ja, eine der Fragestellungen, die wir dann haben, lautet, wenn Sie

12:49.560 --> 12:51.160
jetzt irgendeinen Graphen haben,

12:55.350 --> 12:59.010
mit irgendwelchen Wegen, ob gerichtet oder ungerichtet, ist mir jetzt

12:59.010 --> 13:00.490
vollkommen gleichgültig,

13:12.600 --> 13:16.700
Frage, ich kann ja also in diesem Graphen von jeder Ecke zu jeder

13:16.700 --> 13:20.020
anderen kommen, aber ich kann das auf mehreren Wegen.

13:24.970 --> 13:31.730
Gibt es vermutlich eine Möglichkeit, in diesem Graphen einen Weg

13:31.730 --> 13:39.490
auszuzeichnen, um zu sagen, auf dem Weg kommst du durch alle Ecken

13:39.490 --> 13:39.910
durch.

13:40.670 --> 13:44.390
Also zum Beispiel, du könntest von hier nach hier gehen, dann von hier

13:44.390 --> 13:51.010
nach hier, dann von hier nach hier, nach hier und darunter.

13:51.510 --> 13:54.630
Und dann habe ich sämtliche Ecken aufgefädelt.

13:55.070 --> 13:58.270
Das ist nicht die einzige Möglichkeit, das zu tun, aber es ist eine

13:58.270 --> 13:58.930
der Möglichkeiten.

13:59.670 --> 14:03.830
Und wenn ich solch einen Weg habe, dann sage ich, dieser Weg spannt

14:03.830 --> 14:05.170
den Graphen auf.

14:06.230 --> 14:10.650
Also der Begriff spannender Weg hat nichts zu tun mit Kriminalromanen,

14:12.150 --> 14:16.210
sondern kommt davon, dass das wie ein Regenschirm den ganzen Graphen

14:16.210 --> 14:16.810
aufspannt.

14:18.810 --> 14:24.030
Wir werden hinterher sehen, das wird sich also im Studium noch öfters

14:24.030 --> 14:28.810
beschäftigen, dass uns nicht nur spannende Wege, sondern bestimmte

14:28.810 --> 14:35.210
Teilgraphen interessieren, die sämtliche Ecken erreichen und dass man

14:35.210 --> 14:36.530
die praktisch berechnen muss.

14:36.530 --> 14:40.370
Also beispielsweise, wenn Sie eine Implementierung von Java oder

14:40.370 --> 14:42.810
ähnlichen Dingen haben, dann gibt es da drin einen Programm namens

14:42.810 --> 14:50.090
Speicherbereiniger und dessen zentraler Algorithmus besteht darin, in

14:50.090 --> 14:54.490
einem Graphen, der unter Umständen 100.000 oder eine Million Ecken

14:54.490 --> 15:00.890
hat, solche spannenden Wege zu berechnen, bei der ich jede Ecke genau

15:00.890 --> 15:02.110
einmal mitnehme.

15:03.690 --> 15:07.750
Das heißt, hinter dem Begriff spannender Weg verbirgt sich hinterher

15:07.750 --> 15:13.010
ein Programmierproblem, was im großen Stil zu lösen ist, wenn man

15:13.010 --> 15:15.610
Programmiersprachen praktisch auf den Rechner bringt.

15:22.900 --> 15:25.860
Wenn Sie zweimal durch eine Ecke gehen, dann ist das nach dieser

15:25.860 --> 15:27.200
Definition kein spannender Weg.

15:28.900 --> 15:30.080
Sie gehen einmal durch jede Ecke.

15:32.520 --> 15:37.080
Das führt uns zu Globaleigenschaften von Graphen.

15:38.340 --> 15:47.000
Nämlich, wenn ich diesen

15:56.330 --> 15:57.450
Graphen zeichne,

16:01.980 --> 16:05.300
dann können Sie sich auf zwei verschiedene Standpunkte stellen.

16:06.140 --> 16:09.420
Sie können zunächst mal sagen, der hat zwei Graphen gezeichnet.

16:09.420 --> 16:11.080
Mit je zwei Ecken.

16:12.460 --> 16:13.720
Die Aussage ist richtig.

16:15.100 --> 16:20.060
Sie können aber auch sagen, er hat einen Graph gezeichnet und er hat

16:20.060 --> 16:20.580
vier Ecken.

16:22.340 --> 16:24.880
Der zerfällt aber offensichtlich in zwei Teile.

16:30.050 --> 16:33.550
Die Unterschiede zwischen diesen Begriffen führen zum Begriff des

16:33.550 --> 16:34.870
zusammenhängenden Graphen.

16:35.110 --> 16:39.190
Das ist ein ungerichteter Graph, in dem jede Ecke E von jeder anderen

16:39.190 --> 16:44.190
Ecke aus erreichbar ist und dieser Graph hat offensichtlich diese

16:44.190 --> 16:45.190
Eigenschaft nicht.

16:46.650 --> 16:50.510
Sondern er besteht aus zwei zusammenhängenden Graphen.

16:51.730 --> 16:56.170
Wir nennen diese zwei Einzelstücke dann hinterher jeweils eine

16:56.170 --> 16:57.430
Zusammenhangskomponente.

16:58.290 --> 17:04.930
Wenn ich das ganze Ding gerichtet zeichne, dann würde ich jetzt Pfeile

17:04.930 --> 17:05.590
anfügen.

17:06.790 --> 17:07.670
Zum Beispiel so.

17:08.810 --> 17:16.410
Und dann sehe ich, dass nach dieser Definition hier der Graph stark

17:16.410 --> 17:18.130
zusammenhängende heißt.

17:18.930 --> 17:21.410
Auf Englisch heißt es stark, strongly.

17:27.430 --> 17:31.310
Wenn ich von jeder Ecke aus jede andere erreichen kann.

17:32.830 --> 17:34.930
Von jeder Ecke jede andere.

17:35.430 --> 17:38.630
Also erstens mal, das Ding besteht schon wieder aus zwei Teilen.

17:38.630 --> 17:42.330
Ich kann also bestenfalls einen Teil betrachten, um diese Frage zu

17:42.330 --> 17:42.650
klären.

17:43.270 --> 17:46.650
Dann ist es aber immer noch nicht stark zusammenhängend.

17:46.830 --> 17:50.290
Denn ich kann zwar von dieser Ecke aus diese Ecke hier unten

17:50.290 --> 17:50.770
erreichen.

17:51.930 --> 17:54.410
Aber das Umgekehrte geht nur auf dem Semiweg.

17:58.230 --> 18:00.430
Und daher ist das ganze Ding nicht stark zusammenhängend.

18:01.150 --> 18:07.830
Ich habe also hier jetzt, wenn ich es gerichtet zeichne, einen

18:07.830 --> 18:12.470
Graphen, der aus vier Ecken besteht.

18:13.990 --> 18:17.150
Und jede für sich ist eine starke Zusammenhangskomponente.

18:18.090 --> 18:18.650
Vier Stück.

18:19.670 --> 18:26.330
Wenn ich die ganze Geschichte anders malen würde und auch noch einen

18:26.330 --> 18:31.410
Weg so herum hinzeichnen würde, dann wäre mindestens dieser Teil jetzt

18:31.410 --> 18:32.450
stark zusammenhängend.

18:32.710 --> 18:35.450
Denn jetzt komme ich von oben nach unten und von unten nach oben.

18:41.690 --> 18:42.250
Ja,

18:45.690 --> 18:50.070
ich schließe den jetzt mal wieder aus und komme zum nächsten Begriff,

18:50.210 --> 18:52.630
einseitiger Zusammenhang.

18:52.630 --> 18:58.250
Ich rede von einem einseitig zusammenhängenden Graphen, wenn ich von

18:58.250 --> 19:03.130
zwei beliebigen Ecken jeweils entweder von der einen in die andere

19:03.130 --> 19:04.790
Richtung oder umgekehrt gehen kann.

19:05.490 --> 19:06.570
Aber nicht beides.

19:07.550 --> 19:08.550
Das habe ich nicht gefordert.

19:09.750 --> 19:15.850
Das heißt, dieser Graph hier wäre jetzt, wenn ich diesen roten Pfeil

19:15.850 --> 19:18.690
wieder streiche, einseitig zusammenhängend.

19:18.890 --> 19:20.350
Denn von oben komme ich nach unten.

19:21.230 --> 19:26.030
Und von unten brauche ich nicht nach oben kommen.

19:26.970 --> 19:30.090
Es muss mindestens eine Richtung gehen, die andere ist nicht verlangt.

19:34.630 --> 19:38.990
Frage, jetzt male ich einen Graphen mit drei Ecken, so,

19:44.580 --> 19:46.660
ist der einseitig zusammenhängend?

19:51.920 --> 19:55.720
Ich komme doch von der mittleren Ecke aus in die beiden anderen.

19:58.970 --> 20:03.770
Und ich komme auch von der linken in die mittlere, bei einseitigem

20:03.770 --> 20:04.410
Zusammenhang.

20:05.430 --> 20:08.150
Aber von Semiweg hat niemand was gesagt.

20:09.290 --> 20:11.930
Und ich habe verlangt, dass ich es direkt machen kann.

20:12.390 --> 20:16.710
Und in Vorhersagen komme ich von dieser Ecke nicht darüber, mit

20:16.710 --> 20:18.430
einseitigem Zusammenhang.

20:18.810 --> 20:21.670
Also dieser Graph ist nicht einseitig zusammenhängend.

20:30.790 --> 20:33.870
Und wenn ich das jetzt auch noch erreichen will, dann muss ich also

20:33.870 --> 20:35.750
die Definition noch weiter abschwächen.

20:36.150 --> 20:38.650
Und dann spreche ich von einem schwach zusammenhängenden Graph.

20:38.970 --> 20:42.250
Das ist ein gerichteter Graph, in dem zwischen je zwei Ecken ein

20:42.250 --> 20:43.370
Semiweg existiert.

20:43.710 --> 20:47.090
Und natürlich, also von hier komme ich nach da drüben auf einem

20:47.090 --> 20:47.650
Semiweg.

20:47.810 --> 20:52.430
Denn der Semiweg war ja per Definition in einer, bei dem zwischen je

20:52.430 --> 20:56.170
zwei beteiligten Ecken man in die eine Richtung oder in die andere

20:56.170 --> 20:57.030
Richtung gehen kann.

20:58.000 --> 21:00.270
Und das kann ich hier zusammenhängend ersetzen.

21:05.590 --> 21:09.850
Diese Begriffe, besonders die Begriffe zusammenhängend, stark

21:09.850 --> 21:13.950
zusammenhängend und einseitig zusammenhängend, die werden Sie noch an

21:13.950 --> 21:17.210
vielen Stellen sehen und Sie werden auch noch jede Menge Algorithmen

21:17.210 --> 21:17.830
kennenlernen.

21:17.830 --> 21:24.970
Gegeben ein Graph, berechne die sämtlichen Teilgraphen, die in sich

21:24.970 --> 21:29.090
zusammenhängend, beziehungsweise stark zusammenhängend oder einseitig

21:29.090 --> 21:30.530
oder schwach zusammenhängend sind.

21:31.470 --> 21:35.050
Das heißt also, die Definitionen sehen zunächst mathematisch aus,

21:35.390 --> 21:38.130
haben aber hinterher beträchtliche praktische Bedeutung.

21:41.390 --> 21:46.730
Hier ist nochmal unser Standardbeispielgraph.

21:50.850 --> 21:55.490
Der ist nicht stark zusammenhängend, er ist gerichtet, also

21:55.490 --> 21:59.390
Zusammenhang ohne Beisatz ist hier nicht anwendbar.

21:59.750 --> 22:04.410
Er ist aber offenbar nicht stark zusammenhängend, denn Sie sehen von

22:04.410 --> 22:09.410
der Ecke C aus kommen Sie in keine der anderen Ecken, nach Definition

22:09.410 --> 22:10.690
des starken Zusammenhangs.

22:12.870 --> 22:17.470
Aber Sie kommen von der Ecke C aus und genauso von allen anderen Ecken

22:17.470 --> 22:22.510
in jede andere Ecke, wenn Sie das Recht haben, statt in die

22:22.510 --> 22:24.970
Pfeilrichtung auch in umgekehrter Pfeilrichtung zu gehen.

22:27.130 --> 22:32.170
Ja und wenn irgendetwas einseitig zusammenhängend ist, dann ist es

22:32.170 --> 22:34.390
selbstverständlich auch schwach zusammenhängend, denn das ist eine

22:34.390 --> 22:35.170
schwächere Forderung.

22:36.430 --> 22:42.610
Also der Graph ist nicht stark zusammenhängend, wohl aber schwach und

22:42.610 --> 22:44.030
einseitig zusammenhängend.

22:44.830 --> 22:47.690
Nun hatte ich also darauf hingewiesen bereits, da gibt es den Begriff

22:47.690 --> 22:54.110
der Zusammenhangskomponente und schwach und einseitig bildet dieser

22:54.110 --> 22:57.350
Graph komplett eine Zusammenhangskomponente.

22:58.090 --> 23:04.090
Schauen wir uns das ganze Ding mal jetzt an unter Gesichtspunkten des

23:04.090 --> 23:05.730
starken Zusammenhangs.

23:06.350 --> 23:12.730
Dann sehen wir, dass wir also von C aus nirgends hinkommen und in den

23:12.730 --> 23:18.590
Vorhinein ist C für sich alleine eine Zusammenhangskomponente.

23:25.360 --> 23:28.980
Von A kommen wir nach D, von D kommen wir nach B, also von A kommen

23:28.980 --> 23:29.800
wir überall hin.

23:30.280 --> 23:35.940
Von D aus kommen wir aber nicht nach A, wie sich zeigt.

23:37.820 --> 23:42.160
Und in Folge dessen ist das eine andere starke

23:42.160 --> 23:42.800
Zusammenhangskomponente.

23:47.750 --> 23:48.610
Das A fällt aus.

23:49.490 --> 23:54.670
Von D kommen Sie nach B und umgekehrt kommen Sie von B nach D.

23:59.400 --> 24:00.360
Auch nicht.

24:01.640 --> 24:02.280
Pech.

24:04.760 --> 24:08.080
Also dieses Ding fällt auch aus und dann ist klar, dass das noch eine

24:08.080 --> 24:08.400
ist.

24:08.900 --> 24:12.340
Also unter Gesichtspunkten starker Zusammenhangskomponenten zerfällt

24:12.340 --> 24:16.060
dieses Beispiel in vier Zusammenhangskomponenten.

24:20.460 --> 24:24.620
Empfehlung, malen Sie sich zu Hause irgendein Bildchen auf und

24:24.620 --> 24:27.580
versuchen das herauszufinden und die ganzen Eigenschaften zu

24:27.580 --> 24:27.960
bestimmen.

24:27.960 --> 24:31.980
Wie das Bildchen aussieht, ist völlig belanglos, aber es sollte

24:31.980 --> 24:33.720
wenigstens vier oder fünf Ecken haben.

24:33.880 --> 24:37.500
Bei dreien ist die Sache noch ziemlich langweilig.

24:40.700 --> 24:47.260
Diese ganzen Begriffe gehen zurück auf einen Herrn namens Leonhard

24:47.260 --> 24:47.700
Euler.

24:48.720 --> 24:53.080
Das war ein Schweizer, in Basel geboren, aber den größten Teil seines

24:53.080 --> 24:56.960
Lebens hat er in St. Petersburg und in Königsberg verbracht.

24:56.960 --> 25:00.980
Und als er Professor in Königsberg war, hat er sich folgende Frage

25:00.980 --> 25:01.540
gestellt.

25:02.160 --> 25:06.960
Gegeben sei der Stadtplan von Königsberg, da gibt es einen Fluss, die

25:06.960 --> 25:09.520
Pregel, in der gibt es eine Insel.

25:10.640 --> 25:12.640
Da steht der Dom drauf oder stand der Dom drauf.

25:13.760 --> 25:21.160
Und jetzt war die Frage, kann man einen Weg fabrizieren, bei dem man

25:21.160 --> 25:23.620
genau einmal über sämtliche Brücken läuft.

25:24.620 --> 25:28.040
Und zum Ausgangspunkt zurückkehrt.

25:30.980 --> 25:35.920
Jede Kante dieses Grafen, den ich hier eingezeichnet habe, führt über

25:35.920 --> 25:39.780
eine Brücke und übersetzt in grafentheoretische Terminologie, heißt

25:39.780 --> 25:49.280
diese Frage, gibt es in diesem Grafen einen Weg, der sämtliche Kanten

25:49.280 --> 25:50.240
mitnimmt.

25:52.340 --> 25:55.680
Und zwar genau einmal jede Kante.

26:00.410 --> 26:03.250
Diese Fragestellung war in Wahrheit der Ausgangspunkt der

26:03.250 --> 26:05.370
Grafentheorie, vorher gab es das nicht.

26:06.370 --> 26:10.410
Und die Leute haben sehr lange darüber nachgedacht, ob dieses Problem

26:10.410 --> 26:11.170
lösbar ist.

26:11.290 --> 26:15.310
Kann man also über diese sieben Brücken gehen und über keine Brücke

26:15.310 --> 26:19.090
zweimal und anschließend wieder am Ausgangspunkt zurückkommen.

26:19.090 --> 26:24.050
Die Antwort lautet, man kann nicht.

26:28.310 --> 26:31.670
Und zwar sieht man das leicht folgendermaßen ein.

26:33.210 --> 26:34.670
Wir betrachten die Ecken.

26:35.460 --> 26:46.470
Wenn Sie in irgendeiner Ecke anfangen, in diesem Grafen, und zu

26:46.470 --> 26:52.890
irgendeiner anderen Ecke gehen, und dann nach irgendwelchen Wegen zum

26:52.890 --> 26:55.390
Schluss wieder an diese Stelle zurückkommen.

26:59.080 --> 27:04.380
Dann ist ganz offensichtlich, dass der Eingangsgrad hier gleich dem

27:04.380 --> 27:05.640
Ausgangsgrad sein muss.

27:05.640 --> 27:11.420
Also als ungerichteter Graf betrachtet, der Grad muss gerade sein.

27:11.520 --> 27:17.900
Es muss zwei Kanten geben, die ein- und ausgehen von dieser einen

27:17.900 --> 27:18.160
Ecke.

27:19.280 --> 27:26.400
Sollten Sie auf irgendeine andere Art und Weise nochmal da hinkommen,

27:26.840 --> 27:29.840
aber den Weg da unten noch nicht gegangen sein, dann haben Sie ja noch

27:29.840 --> 27:31.020
nicht alle Kanten erreicht.

27:32.520 --> 27:35.580
Sprich, dann müsste es also eine Möglichkeit geben, wenn Sie da oben

27:35.580 --> 27:39.980
wieder reingekommen sind, nochmal da rauszukommen, um auch noch die

27:39.980 --> 27:41.880
restlichen Kanten mit zu erreichen.

27:44.380 --> 27:48.840
Bei vollständiger Induktion kann man jetzt nachweisen, dass das

27:48.840 --> 27:54.960
verallgemeinerbar ist und dass für jede Ecke gelten muss, dass der

27:54.960 --> 28:01.820
Grad im ungerichteten Grafen gerade sein muss.

28:01.920 --> 28:04.300
Sie müssen aus jeder Ecke, in die Sie reingehen, auch wieder

28:04.300 --> 28:04.860
rauskommen.

28:06.160 --> 28:08.240
Es muss also immer noch eine Kante geben, aus der Sie wieder

28:08.240 --> 28:08.680
rauskommen.

28:10.840 --> 28:14.860
Und selbstverständlich, der Graf muss zusammenhängend sein.

28:14.860 --> 28:18.860
Wenn er nicht zusammenhängend ist, dann habe ich ja zwei Teile, kann

28:18.860 --> 28:23.740
nicht von einer Ecke des einen Teils in eine Ecke des anderen Teils

28:23.740 --> 28:24.060
kommen.

28:26.840 --> 28:29.620
Und dann ist also die Aufgabe sowieso unlösbar.

28:30.260 --> 28:34.180
Daher also die Feststellung, einen Eulaschengreis gibt es genau dann,

28:34.940 --> 28:41.900
wenn der Graf zusammenhängend ist und wenn der Grad, also die Anzahl

28:41.900 --> 28:47.500
der Kanten, die in einer Ecke ein- und ausgehen, für alle Ecken gerade

28:47.500 --> 28:47.860
ist.

28:48.760 --> 28:52.060
Das kann ich durch vollständige Induktion leicht beweisen.

28:52.220 --> 28:55.760
Und jetzt schauen Sie sich das Bild an und stellen fest, hier haben

28:55.760 --> 28:59.200
wir fünf Kanten, hier haben wir drei Kanten, hier haben wir drei

28:59.200 --> 29:00.980
Kanten, hier haben wir drei Kanten.

29:00.980 --> 29:02.900
Es ist vollkommen hoffnungslos.

29:05.340 --> 29:08.860
Der Eulaschengreis kann nicht konstruiert werden.

29:09.380 --> 29:12.520
Also das Königsberger Brückenproblem, wie dieses Problem heißt, ist

29:12.520 --> 29:13.360
nicht lösbar.

29:17.150 --> 29:20.530
Wie gesagt, das war historisch der Ausgangspunkt der Grafentheorie.

29:22.870 --> 29:32.590
Wenn man die ganze Geschichte jetzt für Kanten betrachtet hat, also

29:32.590 --> 29:37.630
kann ich einen Kreis konstruieren, bei dem jede Kante genau einmal

29:37.630 --> 29:42.350
vorkommt, liegt natürlich nahe, auch die umgekehrte Frage zu stellen,

29:42.830 --> 29:47.230
kann ich einen Weg konstruieren, bei dem jede Ecke genau einmal

29:47.230 --> 29:49.450
vorkommt und der einen Kreis darstellt.

29:50.230 --> 29:52.850
Das nennt man dann einen Hamilton'schen Kreis.

29:53.830 --> 30:00.330
Ich habe wieder einen ungerichteten Grafen und der Kreis heißt

30:00.330 --> 30:04.570
Hamilton'sch, wenn er sämtliche Ecken genau einmal enthält.

30:06.350 --> 30:13.190
Das interessante ist, während es leicht einziehbar ist und leicht zu

30:13.190 --> 30:16.330
konstruieren ist, wie ich zu Eulaschengreisen komme, weil ich auch

30:16.330 --> 30:23.950
eine einfache Bedingung habe, ist die Frage, enthält ein ungerichteter

30:23.950 --> 30:28.950
Graf einen Hamilton'schen Kreis, eine Frage, die nur mit riesigem

30:28.950 --> 30:32.490
Rechenaufwand nachgeprüft werden kann und die keine einfach

30:32.490 --> 30:33.910
nachprüfbare Bedingung hat.

30:36.620 --> 30:41.420
Sprich, wenn Sie einen Grafen vorgelegt bekommen und die Frage dazu,

30:41.440 --> 30:45.240
ist da ein Hamilton'scher Kreis, dann kann ich nur empfehlen, werfen

30:45.240 --> 30:48.940
Sie Ihren Rechner an, haben Sie einen entsprechenden Algorithmus und

30:48.940 --> 30:50.620
gehen Sie dann anschließend erst spazieren.

30:50.700 --> 30:52.320
Der Algorithmus wird furchtbar lange rechnen.

30:54.680 --> 30:56.460
Und besichtigen Sie dann hinterher das Ergebnis.

30:57.560 --> 30:59.760
Der Aufwand ist exponentiell in der Anzahl der Ecken.

31:03.010 --> 31:06.750
Das heißt also, der Hamilton'sche Kreis, das ist ein sehr

31:06.750 --> 31:11.750
kompliziertes Thema, während der Eulaschengreis ein sehr einfaches

31:11.750 --> 31:12.330
Thema ist.

31:12.330 --> 31:16.310
Leichte Veränderung der Fragestellung und schon haben wir ein sehr

31:16.310 --> 31:17.090
schwieriges Problem.

31:20.760 --> 31:24.700
Eulaschengreise spielen in der Parallelverarbeitung eine große Rolle.

31:26.020 --> 31:32.540
Bei der Frage, wie kann ich irgendeine Aufgabenstellung auf N

31:32.540 --> 31:37.260
Prozessoren, die parallel arbeiten, verteilen.

31:37.840 --> 31:41.360
Hamilton'sche Kreise haben nur Spezialanwendungen im Bereich der

31:41.360 --> 31:42.440
Kombinatorik.

31:45.590 --> 31:48.830
Soviel zu Grafen und gerichteten Grafen im Allgemeinen.

31:49.970 --> 31:53.330
Und nun schränken wir die ganze Geschichte ein und betrachten

31:53.330 --> 31:54.650
azyklische Grafen.

31:55.610 --> 31:59.250
Das sind Grafen, die, wie der Name sagt, keinen Zyklus enthalten.

32:02.310 --> 32:06.710
Wir können das gerichtet wieder betrachten oder ungerichtet.

32:09.310 --> 32:13.270
Die Standardmethode ist zunächst mal den gerichteten azyklischen

32:13.270 --> 32:14.350
Grafen zu betrachten.

32:15.430 --> 32:18.310
Auf Englisch heißt er ein Directed

32:22.370 --> 32:31.150
Acyclic Graf und wird in der Literatur oft mit seinen

32:31.150 --> 32:32.950
Anfangsbuchstaben abgekürzt.

32:32.950 --> 32:39.270
Sie finden also dann in der Literatur eine Aussage, gegeben sei ein

32:39.270 --> 32:39.610
DAG.

32:42.470 --> 32:44.650
Und dann muss man wissen, was die Abkürzung bedeutet.

32:46.730 --> 32:49.210
Das ist nämlich meistens an dieser Stelle dann nicht erklärt.

32:49.830 --> 32:52.030
Das heißt also gerichteter azyklischer Graf.

32:57.730 --> 33:01.030
Wir schauen wieder unser Standardbeispiel an und stellen fest, der hat

33:01.030 --> 33:02.090
genau diese Eigenschaft.

33:02.190 --> 33:03.210
Der hat nämlich keinen Zyklus.

33:05.370 --> 33:09.410
Sie können zwar von A nach B auf zwei verschiedene Weisen kommen, das

33:09.410 --> 33:10.190
ist unschädlich.

33:13.350 --> 33:14.810
Aber Sie können nicht zurückkommen.

33:15.070 --> 33:17.170
Bei keiner Ecke sind Sie in der Lage zurückzukommen.

33:19.090 --> 33:25.790
Wenn ich dasselbe Ding ungerichtet betrachte und hier beispielsweise

33:25.790 --> 33:29.570
also jetzt die Pfeilrichtung wegnehmen würde, all das nur noch als

33:29.570 --> 33:34.970
Kanten zeichne, dann habe ich natürlich Kreise, die Hülle und Fülle.

33:35.330 --> 33:37.210
Denn dann dürfen Sie ja vorwärts und rückwärts gehen.

33:39.730 --> 33:45.390
Und dann ist das also keineswegs ein Graf ohne Kreise, nur gerichtet

33:45.390 --> 33:46.770
ist es ein Graf ohne Kreise.

33:49.350 --> 33:55.170
Und ungerichtet bezeichne ich dann einen solchen Graf, der keine

33:55.170 --> 33:55.990
Kreise hat.

33:55.990 --> 33:59.130
Kreis war die Korrespondenz zu Zyklus als ein Wald.

34:04.570 --> 34:07.470
Und was habe ich denn hier hingezeichnet?

34:08.730 --> 34:15.050
Wenn ich das alles zusammennehme, dann habe ich einen Wald

34:15.050 --> 34:15.930
hingezeichnet.

34:19.530 --> 34:24.250
Niemand hat verlangt, dass ein Wald eine einzige

34:24.250 --> 34:25.630
Zusammenhangskomponente ist.

34:26.730 --> 34:28.670
Der kann also aus mehreren Teilen bestehen.

34:29.750 --> 34:33.550
Wenn ich diese Forderung zusätzlich erhebe, dass ich nur eine

34:33.550 --> 34:38.310
Zusammenhangskomponente habe, dann rede ich nicht von einem Wald,

34:38.430 --> 34:39.290
sondern von einem Baum.

34:41.030 --> 34:44.350
Das ist ein Wald, in dem je zwei Ecken durch einen Weg verbunden sind

34:44.350 --> 34:46.950
und da es ungerichtet ist, heißt das, dass es eine

34:46.950 --> 34:48.450
Zusammenhangskomponente ist.

34:48.830 --> 34:54.630
Also sehen wir hier ein Beispiel eines Waldes und jeder der beiden

34:54.630 --> 34:56.710
Teilgrafen ist für sich ein Baum.

34:59.310 --> 35:03.190
Ich bekomme also die bekannte Aussage, ein Wald besteht aus Bäumen.

35:04.010 --> 35:05.310
Die kann ich auch beweisen.

35:13.880 --> 35:18.160
Nun gibt es eine ganz merkwürdige Geschichte noch.

35:18.460 --> 35:20.760
Bäume genauso wie Wälder haben Blätter.

35:22.500 --> 35:27.470
Und unter einem Blatt verstehe ich jeweils eine Ecke mit Grad 1.

35:28.580 --> 35:35.720
Sprich also, das hier ist ein Blatt, das hier ist ein Blatt, das hier

35:35.720 --> 35:42.460
ist ein Blatt, und das, das, das, das.

35:44.510 --> 35:50.820
Alle anderen Ecken haben zwei oder mehr Kanten, eignen sich also nicht

35:50.820 --> 35:51.380
als Blätter.

35:57.200 --> 36:03.600
Das ist in dem Zusammenhang zunächst eine sehr ungewohnte und

36:03.600 --> 36:04.780
merkwürdige Begriffsbildung.

36:04.780 --> 36:11.140
Wir werden aber dann hinterher sehen, dass wir jetzt gleich diesem

36:11.140 --> 36:13.860
Begriff Blatt eine sehr plastische Bedeutung geben können.

36:15.160 --> 36:19.800
Bevor wir das aber tun, schauen wir uns einmal Bäume an und stellen

36:19.800 --> 36:27.300
uns die Frage, wenn du die Anzahl der Ecken hast, in diesem Beispiel,

36:27.480 --> 36:31.660
für einen der beiden Bäume, wie viele Kanten gibt es denn dann?

36:33.740 --> 36:35.260
Zählen wir es also mal ab.

36:35.560 --> 36:40.460
Wir haben hier 5 Ecken und 1, 2, 3, 4 Kanten.

36:41.700 --> 36:47.200
Wir haben hier 6 Ecken und 1, 2, 3, 4, 5 Kanten.

36:48.620 --> 36:50.580
Frage, können wir das verallgemeinern?

36:50.720 --> 36:52.400
Und die Antwort lautet Ja.

36:53.280 --> 36:58.360
In einem umgerichteten Baum ist die Anzahl der Ecken stets um 1 größer

36:58.360 --> 36:59.680
als die Anzahl der Kanten.

37:05.500 --> 37:07.080
Das kann ich ganz leicht beweisen.

37:07.960 --> 37:10.860
Wenn ich nur eine Ecke habe, dann gibt es überhaupt keine Kante.

37:13.320 --> 37:15.200
Und infolge dessen ist die Aussage richtig.

37:16.400 --> 37:20.320
Also, Mächtigkeit von E gleich 1, Anzahl der Kanten gleich 0.

37:22.220 --> 37:26.980
Jetzt nehme ich mal an, dass ich irgendeinen Baum habe, den habe ich

37:26.980 --> 37:29.020
hier eingesperrt, ich zeige ihn Ihnen gar nicht hin.

37:31.240 --> 37:33.900
Von dem weiß ich bereits, dass diese Aussage gilt.

37:35.380 --> 37:36.820
Und er habe N Ecken.

37:38.980 --> 37:41.120
Also ist die Anzahl der Kanten N minus 1.

37:43.280 --> 37:45.240
Jetzt füge ich eine neue Ecke hinzu.

37:46.240 --> 37:50.680
Ich gehe also über zu einem Baum mit N plus 1 Ecken.

37:51.460 --> 37:53.400
Und das zeichne ich jetzt explizit außen hin.

37:57.830 --> 38:00.770
Ja, da das ja ein Baum sein soll, muss das eine

38:00.770 --> 38:03.050
Zusammenhangskomponente sein.

38:03.570 --> 38:07.690
Also auf irgendeine Art und Weise muss der mit einer Ecke verbunden

38:07.690 --> 38:07.990
sein.

38:08.370 --> 38:10.730
Mindestens eine Kante ist auch dazu gekommen.

38:11.170 --> 38:13.370
Also eine Ecke mehr, eine Kante mehr.

38:14.010 --> 38:14.690
Die Aussage stimmt.

38:16.590 --> 38:24.420
Frage, könnte es denn nicht sein, dass ich auch in der Lage bin, noch

38:24.420 --> 38:26.060
eine zweite Kante da rein zu malen?

38:32.790 --> 38:35.270
Antwort, das geht nicht, dann ist es kein Baum mehr.

38:36.710 --> 38:44.170
Denn wenn diese erste Kante an dieser Stelle endig und eine etwaige

38:44.170 --> 38:51.430
zweite an einer anderen Stelle, dann weiß ich ja, laut Definition des

38:51.430 --> 38:55.490
Baumes, du kannst von jeder Ecke zu jeder anderen kommen.

38:55.610 --> 39:00.430
Das heißt also, es gibt dann einen Weg, um von hier nach hier oder

39:00.430 --> 39:01.330
umgekehrt zu kommen.

39:03.030 --> 39:08.290
Ja, aber was ich jetzt insgesamt gezeichnet habe, ist ganz

39:08.290 --> 39:09.310
offensichtlich ein Kreis.

39:09.710 --> 39:12.930
Da, da und dann darum.

39:16.310 --> 39:19.370
Das heißt also, wenn ich die Annahme mache, dass ich eine zweite Kante

39:19.370 --> 39:23.750
zeichnen könnte, ausgehend von meiner neuen Ecke, dann lande ich

39:23.750 --> 39:24.910
sofort in einem Kreis.

39:25.710 --> 39:28.810
Kreise kommen in Bäumen nicht vor, also gibt es diese zweite Kante

39:28.810 --> 39:29.130
nicht.

39:30.310 --> 39:34.150
Daraus folgt also, es gibt für jede neue Ecke, die ich hinzufüge,

39:34.750 --> 39:36.470
genau eine neue Kante.

39:38.330 --> 39:41.970
Und da war am Anfang die Aussage, dass jede Anzahl der Ecken gleich

39:41.970 --> 39:44.010
die Anzahl der Kanten plus eins hat.

39:44.570 --> 39:47.930
Und jetzt jeweils eine Ecke und eine Kante hinzufügen, bleibt die

39:47.930 --> 39:48.810
Aussage erhalten.

39:49.930 --> 39:55.390
Das ist endlich der Induktionsbeweis, dass also diese Aussage hier

39:55.390 --> 39:57.330
oben universell gültig ist.

39:58.610 --> 40:01.350
In Bäumen kann ich das also ganz einfach abzählen.

40:06.480 --> 40:11.920
Schön, bei umgerichteten Graphen wusste ich also, und das kann ich auf

40:11.920 --> 40:14.940
die gleiche Weise nachrechnen, wie ich gerade diese Aussage über Bäume

40:14.940 --> 40:18.140
bewies, ein Wald besteht aus Bäumen.

40:19.060 --> 40:23.740
Bei gerichteten Wäldern stimmt das nicht mehr.

40:25.560 --> 40:26.820
Da habe ich größere Probleme.

40:29.460 --> 40:35.560
Unter einem gerichteten Wald verstehe ich einen Graphen, bei dem jede

40:35.560 --> 40:37.180
Ecke die Eigenschaft hat,

40:40.360 --> 40:43.500
dass ich auf genau einen Weg reinkomme.

40:44.140 --> 40:51.140
Ich kann eventuell auf mehrere Arten und Weisen rauskommen, aber es

40:51.140 --> 40:53.860
gibt nur eine Möglichkeit reinzukommen oder gar keine.

40:54.500 --> 40:57.020
Also es kann auch eine Ecke geben, in die es überhaupt nicht

40:57.020 --> 40:57.520
reinkommt.

40:59.240 --> 41:03.880
Das ist gemeint mit der Aussage, Eingangsgrad jeder Ecke ist keiner

41:03.880 --> 41:05.800
gleich eins, also null oder eins.

41:08.850 --> 41:12.450
Wenn ich eine Ecke habe mit Eingangsgrad null, also zum Beispiel diese

41:12.450 --> 41:14.310
Ecke hier oben, dann nenne ich das eine Wurzel.

41:22.010 --> 41:25.210
Und jetzt kann ich die Wälder sofort wieder spezialisieren zu Bäumen.

41:25.970 --> 41:31.090
Ein gerichteter Graph stellt einen Wald dar, der genau eine Wurzel

41:31.090 --> 41:31.390
hat.

41:31.990 --> 41:36.230
Also es gibt keine Möglichkeit, an einer zweiten Stelle anzufangen.

41:36.830 --> 41:43.510
Und Blätter sind umgekehrt dann die Ecken, bei denen ich zwar

41:43.510 --> 41:45.130
reinkommen kann, aber nicht mehr raus.

41:45.130 --> 41:48.750
Sprich also, wenn ich den Graphen jetzt vervollständige und sage, das

41:48.750 --> 41:56.130
ist ein gerichteter Graph mit fünf Ecken, dann hat der eine Wurzel und

41:56.130 --> 41:57.290
er hat drei Blätter.

42:00.680 --> 42:02.320
Ja, warum heißt das Kind Baum?

42:02.820 --> 42:07.900
Sie würden es also vielleicht lieber gesehen haben, wenn ich das ganze

42:07.900 --> 42:09.100
Ding so gemalt hätte.

42:10.520 --> 42:13.300
Bäume haben, soweit ich weiß, in der Natur ihre Wurzel unten.

42:14.000 --> 42:16.680
Und dann hätte ich es also so malen müssen.

42:27.070 --> 42:30.970
Die Grafentheoretiker und die Informatiker, diese verqueren Menschen,

42:31.510 --> 42:35.010
haben sich aber beschlossen, dass sie sich auf den Kopf stellen.

42:36.910 --> 42:42.210
Bäume werden in der Informatik grundsätzlich gezeichnet mit der Wurzel

42:42.210 --> 42:42.650
oben.

42:44.090 --> 42:50.570
Wenn Sie sowas hinmalen, dann müssen Sie schon dazu schreiben, aus

42:50.570 --> 42:54.030
welchem Grund Sie das genau gezeichnet haben.

42:54.610 --> 42:58.330
Die Normaldarstellung wäre die Darstellung, bei der die Wurzel oben

42:58.330 --> 42:58.690
ist.

43:00.230 --> 43:04.050
Und für den Fall also, dass Sie das ganze Ding so gezeichnet haben

43:04.050 --> 43:19.820
sollten und die Pfeile vergessen haben, dann wird jeder Informatiker

43:19.820 --> 43:24.740
automatisch ergänzen, aha, was der meint, ist ein Baum und zwar

43:24.740 --> 43:28.300
möglicherweise sogar ein gerichteter und er hat also lediglich die

43:28.300 --> 43:29.140
Pfeile vergessen.

43:31.460 --> 43:33.960
Und ganz richtig hätte das also so sein müssen.

43:36.180 --> 43:41.060
Das wird so automatisch ergänzt, dass Sie also in vielen Büchern und

43:41.060 --> 43:44.980
sonst wo Bäume gezeichnet finden, da steht dann im Text, ist ein

43:44.980 --> 43:47.700
gerichteter Baum, jetzt schauen Sie nach, da steht doch gar kein Pfeil

43:47.700 --> 43:47.960
da.

43:49.640 --> 43:51.220
Da hat er das einfach vergessen.

43:52.220 --> 43:55.160
Weil er unterstellt hat, dass alle Leute wissen, dass man Bäume von

43:55.160 --> 43:58.080
oben nach unten zeichnet und dass die Pfeile immer von oben nach unten

43:58.080 --> 43:58.360
gehen.

44:02.680 --> 44:07.560
Das sollte man also wissen, wie das interpretiert wird.

44:07.680 --> 44:11.880
Und das heißt also umgekehrt, wenn Sie in irgendeiner Prüfung

44:11.880 --> 44:15.300
aufgefordert werden, einen Baum zu zeichnen und Sie lassen aus

44:15.300 --> 44:19.240
Versehen die Pfeile weg, dann wissen Sie jetzt, wie der Prüfer das

44:19.240 --> 44:19.700
ergänzt.

44:20.620 --> 44:23.080
Er zeichnet die Pfeile immer von oben nach unten.

44:24.280 --> 44:25.300
Ganz automatisch.

44:28.080 --> 44:32.560
Ja, und jetzt bekommt also der Begriff Blatt plötzlich eine plastische

44:32.560 --> 44:33.200
Bedeutung.

44:33.640 --> 44:38.440
Blätter sind, wenn ich den Baum so zeichne, offensichtlich die Enden

44:38.440 --> 44:39.860
der ganzen Angelegenheit.

44:41.280 --> 44:45.340
Ja, und bei einem normalen Baum sind an den Enden von Zweigen ja

44:45.340 --> 44:46.080
gewöhnlich Blätter.

44:46.080 --> 44:53.320
Von daher also die Bezeichnung Blatt für die Ecken, deren Ausgangsgrad

44:53.320 --> 44:54.120
Null ist.

44:55.800 --> 44:59.520
Und das erklärt also rückwirkend auch den Begriff Blatt bei den

44:59.520 --> 45:00.460
ungerichteten Grafen.

45:04.050 --> 45:13.130
Ja, wenn ich jetzt, egal ob in dieser oder in jener Weise gezeichnet,

45:13.830 --> 45:21.290
die Höhe eines solchen Baumes definieren will, dann könnten Sie also

45:21.290 --> 45:26.350
sagen, ja der hat Wurzel, der hat dann hier eine Verzweichungsstelle

45:26.350 --> 45:28.390
und dann hat er Blätter, also drei.

45:32.170 --> 45:36.750
Aber das, was wir zählen, ist wiederum lediglich die Weglänge, sprich

45:36.750 --> 45:43.550
also für diese ganze Geschichte definieren wir die Höhe als zwei.

45:45.990 --> 45:51.370
Und jetzt können wir umgekehrt oder weitergehend sagen, unter Höhe

45:51.370 --> 45:55.450
verstehen wir nicht nur die Weglänge von der Wurzel zu einem Blatt,

45:55.790 --> 46:01.310
sondern ich kann auch die Höhe von dieser Ecke aus bis zu einem Blatt

46:01.310 --> 46:01.890
messen.

46:02.650 --> 46:06.310
Und das ist dann offensichtlich die Weglänge 1, also Höhe 1.

46:09.090 --> 46:12.690
Also von hier nach da runter habe ich Höhe 1.

46:15.290 --> 46:20.350
Ja und wenn ich also immer zu einem Blatt zähle, was mache ich denn

46:20.350 --> 46:23.970
dann, wenn ich die Weglänge wissen will von der Wurzel zu einer

46:23.970 --> 46:29.070
beliebigen Ecke, die mittendrin ist, dann spreche ich von der Tiefe

46:29.070 --> 46:36.060
dieser Ecke und habe also hier die Tiefe 1.

46:40.500 --> 46:45.540
Woraus die Rechenregel folgt, wenn du eine beliebige Ecke in der Mitte

46:45.540 --> 46:52.800
wählst und Tiefe dieser Ecke und Höhe dieser Ecke zusammenzählst, dann

46:52.800 --> 46:55.360
hast du die Höhe des ganzen Baumes, dann geht es nämlich von der

46:55.360 --> 46:57.280
Wurzel bis zum Blatt.

47:04.090 --> 47:13.850
Und ich habe hier jetzt einen Grafen angegeben, einen Baum mit einer

47:13.850 --> 47:20.270
Menge Ecken und habe jeweils die Höhe hingeschrieben, die da existiert

47:20.270 --> 47:28.310
und weiß also sofort, wenn da Höhe 0 steht, laut Definition ist das

47:28.310 --> 47:31.210
die maximale Länge eines Wegs von E zu einem Blatt.

47:31.590 --> 47:39.470
Wenn diese maximale Länge 0 ist, dann muss also C, E, J, H, J und K,

47:39.510 --> 47:40.450
das müssen Blätter sein.

47:43.630 --> 47:46.310
Das kann ich sofort hier ablesen.

47:48.590 --> 47:52.970
Empfehlung, damit Sie das üben, nehmen Sie dieses Beispiel zu Hause

47:52.970 --> 48:01.790
und versuchen mal aufzumalen mindestens einen Baum, bei dem die Höhen

48:01.790 --> 48:04.350
genau so angegeben sind, wie hier steht.

48:05.710 --> 48:08.990
Und dann stellen Sie sich die Frage, ist das der einzige oder kann ich

48:08.990 --> 48:10.590
noch mehrere Möglichkeiten angeben?

48:11.270 --> 48:14.350
Wie viele verschiedene Möglichkeiten gibt es, Bäume zu zeichnen,

48:14.710 --> 48:17.570
sodass genau diese Höhen herauskommen?

48:24.820 --> 48:29.620
In einer anderen Interpretation interessiert mich jetzt also noch die

48:29.620 --> 48:34.500
Frage, da habe ich irgendeine Ecke und dann habe ich einen Nachfolger.

48:36.900 --> 48:40.340
Und da muss man sich einfach daran gewöhnen, dass es also verschiedene

48:40.340 --> 48:41.940
Bezeichnungen gibt.

48:42.320 --> 48:45.620
Wenn es in einem Baum solch

48:50.150 --> 48:59.180
eine Verbindung gibt, dann nenne ich das einen Nachfolger der oberen

48:59.180 --> 49:06.860
Ecke oder ich nenne das ein Kind der oberen Ecke oder, und jetzt wird

49:06.860 --> 49:10.360
es chauvinistisch, Töchter habe ich noch nicht gesehen in diesem

49:10.360 --> 49:13.440
Zusammenhang, aber der Begriff Sohn kommt häufiger vor.

49:17.150 --> 49:23.370
Und umgekehrt heißt diese Ecke da oben dann Vorgänger oder

49:26.760 --> 49:27.400
Vater.

49:29.840 --> 49:34.920
Mütter sind offenbar wichtiger als die Töchter, das heißt also der

49:34.920 --> 49:36.640
Begriff Mutter kommt hier auch vor.

49:38.260 --> 49:41.680
Und manchmal, erstaunlicherweise, gibt es sogar Alleinerziehende.

49:42.460 --> 49:48.100
Wir wissen ja also, dass in einem Baum jede Ecke nur einen Eingang

49:48.100 --> 49:48.380
hat.

49:48.380 --> 49:52.700
Also es kann nur einen Vorgänger geben und trotzdem wird er dann als

49:52.700 --> 49:53.720
Eltern bezeichnet.

49:59.080 --> 50:03.300
Es gibt also eine ganze Varietät von verschiedenen Bezeichnungen, die

50:03.300 --> 50:07.200
alle immer das gleiche wiedergeben, nämlich in einem Baum die

50:07.200 --> 50:11.160
Beziehung zwischen einer Ecke und seinem Nachfolger.

50:14.480 --> 50:16.420
Gibt es Fragen zu dieser ganzen Geschichte?

50:25.470 --> 50:31.710
Die Wurzel in dem Beispiel hier unten, das dürfen Sie sich überlegen.

50:33.670 --> 50:35.230
Die Auskunft gebe ich Ihnen jetzt nicht.

50:42.860 --> 50:46.620
Die Wurzel muss höher liegen als alle anderen, das heißt also sie muss

50:46.620 --> 50:50.400
sich auszeichnen durch maximale Höhe.

50:51.140 --> 50:54.860
Und das Rätsel dieses Beispiels ist natürlich, dass die maximale Höhe

50:54.860 --> 50:56.580
3 zweimal vorkommt.

50:56.580 --> 50:58.640
Jetzt müssen Sie sich überlegen, was das bedeutet.

51:09.530 --> 51:10.510
Mehr sage ich dazu nicht.

51:16.680 --> 51:24.140
Soviel zu den Grundbegriffen der Graphentheorie.

51:26.220 --> 51:34.320
Und nun zu der Frage Zusammenhang zwischen Graphentheorie und

51:34.320 --> 51:35.400
Relationen.

51:35.400 --> 51:39.200
Und eine der interessantesten Fragestellungen, die ich dabei habe,

51:39.720 --> 51:47.080
lautet, wennst du eine endliche Relation hast, also eine Relation über

51:47.080 --> 51:48.340
einem endlichen Universum,

51:51.500 --> 51:53.900
dann kannst du das ganze Ding ja aufmalen als Graph.

51:55.080 --> 51:57.880
Mit Kanten zwischen den einzelnen Ecken.

52:03.060 --> 52:08.280
Und dann sind also manche Kanten, die erscheinen überflüssig.

52:08.360 --> 52:19.320
Wenn ich also zum Beispiel Teilerrelationen hinmale und etwa die Zahl

52:19.320 --> 52:24.680
12 hernehme und frage, was die für Teiler hat, dann hat sie den Teiler

52:24.680 --> 52:33.940
6 und sie hat den Teiler 3 und sie hat den Teiler 4 und sie hat den

52:33.940 --> 52:35.040
Teiler 2.

52:37.240 --> 52:41.940
Und 2 teilt auch noch 4 und 2 teilt natürlich auch noch 6.

52:45.700 --> 52:49.460
Und das heißt also, ich muss eine Unzahl verschiedener Kanten

52:49.460 --> 52:55.420
einzeichnen, obwohl ich möglicherweise nur an der Frage interessiert

52:55.420 --> 52:59.740
bin, kommst du von 2 auf irgendeine Art und Weise zu der 12.

53:01.740 --> 53:04.960
Und wenn jetzt einige Leute sich beschweren, selbstverständlich, ich

53:04.960 --> 53:09.520
habe noch bei weiblich zu wenig eingezeichnet, denn nicht nur die 6

53:09.520 --> 53:13.620
teilt die 12, die 3 teilt auch noch die 12, die 2 teilt auch noch die

53:13.620 --> 53:14.060
12.

53:18.700 --> 53:19.580
Und...wie bitte?

53:21.220 --> 53:23.680
Oh, Entschuldigung, das ist natürlich falsch, ja.

53:25.240 --> 53:26.280
2 teilt 3 nicht.

53:31.630 --> 53:36.770
Also eine verwirrende Vielzahl von Kanten und die Frage, die ich

53:36.770 --> 53:41.830
hätte, lautet zunächst einmal, komme ich mit weniger Kanten aus, um

53:41.830 --> 53:44.490
mir ein Bild zu machen, was da insgesamt passiert.

53:49.920 --> 53:53.060
Muss ich die denn alle einzeichnen, um zu sehen, was da los ist?

53:54.360 --> 53:55.240
Das ist die eine Frage.

53:56.180 --> 54:00.080
Na dann komme ich auf die Idee zu sagen, ja, das geht natürlich mit

54:00.080 --> 54:07.780
weniger, da haben wir die 2, die 3, die 6 und die 4.

54:08.920 --> 54:12.100
Und alle teilen 12.

54:17.640 --> 54:24.820
Und außerdem teilt die 2 die 4 und die 3 die 6 und die 2 die 6.

54:24.920 --> 54:26.300
Und jetzt habe ich schon einfach Respekt.

54:26.760 --> 54:27.900
Ich habe noch nicht all das hinter sich.

54:28.480 --> 54:30.220
Ich kann noch weniger hinmalen.

54:30.500 --> 54:31.820
Und kriege immer noch die gleiche Geschichte.

54:32.860 --> 54:37.820
Wenn ich das in Relationentheorie übersetze, dann lautet diese Frage,

54:39.300 --> 54:44.520
gegeben es eine Relation, bestimmt doch mal bitte die reflexive,

54:44.660 --> 54:49.120
transitive Hülle dieser Reflexion, dieser Relation.

54:50.400 --> 54:54.180
Das wäre nämlich dann die Relation, die sagt, und jetzt habe ich alle

54:54.180 --> 54:57.260
Kanten eingezeichnet, bei denen es einen Weg gibt.

55:00.330 --> 55:02.890
Aber ich habe die Wege nicht alle einzeln eingezeichnet.

55:05.370 --> 55:07.870
Die Wege nicht alle als Kanten eingezeichnet.

55:13.340 --> 55:17.120
Das sollte eigentlich einiges weniger haben, aber Sie haben recht, ich

55:17.120 --> 55:18.560
komme mit noch viel weniger aus.

55:22.220 --> 55:31.360
Ich kann also beispielsweise diese hier auslassen und ich kann diese

55:31.360 --> 55:32.300
hier auslassen.

55:35.600 --> 55:37.720
Und ja, das wäre es.

55:40.680 --> 55:47.240
Es ist jetzt die Frage, wie berechnen wir transitive Hüllen von

55:47.240 --> 55:51.240
irgendwelchen Relationen, von denen wir entweder voraussetzen, dass

55:51.240 --> 55:53.640
sie nicht transitiv sind oder dass sie nicht wissen.

55:56.380 --> 56:02.560
Ja, und dann stellt sich heraus, das kann man zwar berechnen, aber im

56:02.560 --> 56:07.200
ersten Anlauf, das was der Unbedarfte macht, das hat einen riesigen

56:07.200 --> 56:07.640
Rechenaufwand.

56:08.980 --> 56:13.680
Wenn ich eine Relation betrachte mit N Ecken oder einen Graphen mit N

56:13.680 --> 56:18.660
Ecken und unbedarft an die Fragestellung heran gehe, dann ist

56:18.660 --> 56:22.820
Berechnung der transitiven Hülle verbunden mit einem Aufwand von N

56:22.820 --> 56:26.380
hoch N Rechenoperationen.

56:27.000 --> 56:29.660
Wir werden das gleich noch sehen, wie diese Zahl N hoch N zustande

56:29.660 --> 56:29.960
kommt.

56:32.400 --> 56:33.620
Und das ist mir zu groß.

56:35.460 --> 56:38.020
Und die Frage lautet, geht es nicht billiger?

56:40.180 --> 56:43.760
Und die Antwort lautet, es geht billiger, es geht immer mit N hoch 3.

56:44.620 --> 56:47.340
Also statt N hoch N, N hoch 3.

56:48.460 --> 56:51.160
N hoch 3 ist der Aufwand, den ich für eine Matrixmultiplikation

56:51.160 --> 56:51.900
brauche, beispielsweise.

56:55.180 --> 57:04.060
Und dieses ganze Kapitel hat jetzt die Aufgabe, dafür zu sorgen, dass

57:04.060 --> 57:09.300
wir einsehen, wie kommen wir runter auf einen Aufwand N hoch 3 in der

57:09.300 --> 57:11.480
Berechnung von transitiven Hüllen.

57:13.000 --> 57:18.760
Dazu schauen wir uns zunächst einmal an die Frage, wie kann ich denn

57:18.760 --> 57:21.040
überhaupt begründen, dass es mit N hoch N geht.

57:21.760 --> 57:29.320
Und ich begründe es so, wenn ich eine endliche Relation habe über eine

57:29.320 --> 57:35.440
endlichen Eckenmenge, dann kann ich zunächst mal feststellen, dass

57:35.440 --> 57:40.360
Rohstern, das heißt die reflexive transitive Hülle, sich berechnen

57:40.360 --> 57:46.480
lässt als identische Relation vereinigt mit Roh, das ganze hoch N.

57:51.340 --> 57:54.640
Das ist erst mal die Aussage, es geht auf jeden Fall mit N hoch N.

57:55.940 --> 58:04.000
Um das einzusehen, male ich mir mal Wege auf und gehe aus von der

58:04.000 --> 58:05.420
Eigenschaft reflexiv.

58:05.420 --> 58:08.080
Und wenn ich dann also einen Weg habe,

58:13.740 --> 58:15.740
hier der Länge 5,

58:19.300 --> 58:25.040
dann habe ich ja bei der Wegdefinition an keiner Stelle gesagt, alle

58:25.040 --> 58:26.280
Ecken müssen verschieden sein.

58:27.100 --> 58:28.340
Die könnten auch identisch sein.

58:29.720 --> 58:35.040
Also kann ich zum Beispiel auch jeden Weg der Länge 1 als Weg der

58:35.040 --> 58:36.000
Länge 5 darstellen.

58:37.020 --> 58:43.220
Ich gehe nämlich einfach von meiner Ecke E zu meiner Ecke E' und dann

58:43.220 --> 58:45.000
laufe ich bei E' im Kreis herum.

58:49.530 --> 58:53.970
Und wenn Ihnen das nicht passt, dann hätten Sie es auch anders machen

58:53.970 --> 59:01.700
können, Sie gehen bei E erstmal im Kreis spazieren und irgendwo

59:01.700 --> 59:07.560
zwischendrin gehen Sie dann nochmal nach E' und dann bleiben Sie bei

59:07.560 --> 59:08.140
E'.

59:16.910 --> 59:23.310
Also erste Einsicht, wenn ich die sämtlichen Wege einer Länge N

59:23.310 --> 59:33.750
betrachte in einer reflexiven Relation, dann sind auch sämtliche Wege

59:33.750 --> 59:35.410
einer Länge kleiner als N.

59:36.490 --> 59:39.430
Damit inbegriffen, weil ich einfach hinten dran noch Zyklen setzen

59:39.430 --> 59:43.030
kann oder vorne dran Zyklen setzen kann oder mit dem drinnen im Kreis

59:43.030 --> 59:43.950
spazieren gehen kann.

59:45.170 --> 59:46.230
Erste Einsicht.

59:48.910 --> 59:55.030
Umgekehrt, wenn ich jetzt mal meine Eckenbezeichnung wieder wegnehme

01:00:03.220 --> 01:00:08.960
und sage in meinem Graphen, gibt es einen Weg, wie wir hier sehen, der

01:00:08.960 --> 01:00:09.580
Länge 4.

01:00:11.920 --> 01:00:18.080
Wie viele verschiedene Ecken gibt es denn dann in diesem Graphen?

01:00:20.120 --> 01:00:22.020
Wenn das ganze Ding reflexiv ist?

01:00:25.260 --> 01:00:25.740
Mindestens.

01:00:35.010 --> 01:00:36.450
Wie viele Ecken gibt es da?

01:00:39.460 --> 01:00:41.340
Die Antwort lautet, es gibt mindestens eine.

01:00:43.080 --> 01:00:46.340
Und mehr kann ich nicht sagen, denn ich könnte natürlich also von

01:00:46.340 --> 01:00:49.880
meiner Ecke E ausgehen, die ganze Zeit nur im Kreis herumlaufen.

01:00:51.120 --> 01:00:52.600
Dann wäre ich auch wieder bei der Ecke E.

01:00:57.390 --> 01:00:58.250
Weitergehende Frage.

01:00:59.670 --> 01:01:07.670
Jetzt nehme ich mal an, dass es in meinem Graphen tatsächlich 4 Ecken

01:01:07.670 --> 01:01:08.190
gäbe.

01:01:10.190 --> 01:01:12.410
Und ich habe diesen Weg hier hingeschrieben.

01:01:15.190 --> 01:01:18.610
Was wissen Sie über die Ecken, die da vorkommen können?

01:01:19.770 --> 01:01:21.510
Sind die alle verschieden auf diesem Weg?

01:01:29.710 --> 01:01:33.190
Es muss mindestens eine doppelt vorkommen, ganz offensichtlich, denn

01:01:33.190 --> 01:01:40.330
wenn ich nur 4 Ecken habe und 5 Kandidaten, dann muss ich 2 Ecken mit

01:01:40.330 --> 01:01:41.530
dem gleichen Namen versehen.

01:01:42.070 --> 01:01:42.950
Es geht nicht anders.

01:01:47.270 --> 01:01:47.470
Ja.

01:01:49.630 --> 01:01:52.330
Infolge dessen habe ich jetzt folgende Feststellungen getroffen.

01:01:52.470 --> 01:01:56.390
Ich habe erstmal gesehen, dass Delta vereinigt Rohhoch I.

01:01:56.510 --> 01:01:58.730
Das wäre also Wege der Länge I.

01:01:59.730 --> 01:02:08.670
Auf jeden Fall enthalten ist in Delta vereinigt Rohhoch N, wenn N die

01:02:08.670 --> 01:02:09.990
Eckenzahl Minus 1 ist.

01:02:12.930 --> 01:02:18.030
Denn umgekehrt, und das bedeutet also, weil wir ja gesehen haben, alle

01:02:18.030 --> 01:02:22.090
Wege kürzerer Länge sind da drin enthalten, dass Delta vereinigt

01:02:22.090 --> 01:02:26.710
Rohhoch N die Vereinigung der sämtlichen Relationen Delta vereinigt

01:02:26.710 --> 01:02:27.590
Rohhoch I ist.

01:02:31.610 --> 01:02:39.170
Zweitens, haben wir festgestellt, wenn N plus 1 die Eckenzahl ist, und

01:02:39.170 --> 01:02:42.370
ich habe Wege der Länge größer gleich N plus 1, das habe ich gerade

01:02:42.370 --> 01:02:48.190
hier mit 4 vorgemacht, muss mindestens eine Ecke mehrfach vorkommen.

01:02:50.630 --> 01:02:55.950
Sprich also zu deutsch, Rohstern ist ja die Beziehung, die sagt, du

01:02:55.950 --> 01:03:03.290
kannst auf einem Weg beliebiger Länge versuchen von A nach B zu

01:03:03.290 --> 01:03:03.550
kommen.

01:03:05.270 --> 01:03:07.030
Denn Rohstern ist transitiv.

01:03:07.690 --> 01:03:09.490
Du kannst alle Noten einschließen.

01:03:09.950 --> 01:03:14.030
Und jetzt stelle ich also fest, sobald du bei Länge N plus 1

01:03:14.030 --> 01:03:17.350
angekommen bist, dann hast du schon eine Ecke doppelt gehabt.

01:03:19.670 --> 01:03:20.430
Anders geht das nicht.

01:03:22.370 --> 01:03:25.810
Also brauchst du nur Wege der Länge kleiner gleich N betrachten.

01:03:26.530 --> 01:03:30.910
Dann hast du vollkommene Auskunft darüber, wie kommt man von A nach B.

01:03:35.500 --> 01:03:37.520
Also übertragen Sie sich das in die Geografie.

01:03:38.340 --> 01:03:41.200
Sie betrachten 10 Städte.

01:03:43.520 --> 01:03:47.440
Und da gibt es also eine Eisenbahnverbindung oder es gibt vielleicht

01:03:47.440 --> 01:03:48.760
auch keine Eisenbahnverbindung.

01:03:49.820 --> 01:03:56.240
Und jetzt möchten Sie gerne wissen, kann ich von einer beliebig

01:03:56.240 --> 01:04:00.300
herausgegriffenen Stadt per Eisenbahn jede andere Stadt erreichen?

01:04:02.440 --> 01:04:07.480
Und die Konklusion, die wir hier jetzt ziehen, lautet, du brauchst nur

01:04:07.480 --> 01:04:10.320
Wege der Länge 9 betrachten.

01:04:10.440 --> 01:04:11.840
Eins weniger, als wir Ecken haben.

01:04:15.350 --> 01:04:23.030
Wenn du nicht mit 8 Zwischenstationen maximal überall hinkommst, dann

01:04:23.030 --> 01:04:26.710
kann ich dir garantieren, dass eine der Städte abgehängt ist von

01:04:26.710 --> 01:04:27.670
diesem Eisenbahnnetz.

01:04:28.890 --> 01:04:30.250
Mehr brauchen wir nicht betrachten.

01:04:31.370 --> 01:04:33.150
Das ist die praktische Konklusion.

01:04:34.710 --> 01:04:39.750
Und das ist das, was hier drinnen steckt, in dieser Aussage.

01:04:41.270 --> 01:04:51.230
Rho-Stern ist auf jeden Fall delta-vereinigt Rho hoch N, wo N eins

01:04:51.230 --> 01:04:54.150
weniger als die Anzahl der Ecken ist.

01:04:54.770 --> 01:04:58.070
Ich habe nicht gesagt, dass es vielleicht mit noch weniger geht.

01:04:58.070 --> 01:05:03.010
Wenn nämlich Rho gleich Rho-Stern ist, weil Rho selbst schon reflexiv

01:05:03.010 --> 01:05:07.470
und transitiv ist, dann hätte ich in Wahrheit N gleich 1 wählen

01:05:07.470 --> 01:05:07.750
können.

01:05:09.910 --> 01:05:13.610
Also kleiner geht es unter Umständen, aber N ist das Maximum, was ich

01:05:13.610 --> 01:05:13.950
brauche.

01:05:15.190 --> 01:05:18.530
Ich brauche nicht mehr, das ist die Aussage, die ich zunächst habe.

01:05:19.990 --> 01:05:23.650
Bevor ich das weiter vertiefe, noch einige weitere Eigenschaften von

01:05:23.650 --> 01:05:24.050
Grafen.

01:05:25.790 --> 01:05:29.470
Zunächst gibt es da die sogenannten Bipartiten oder in der deutschen

01:05:29.470 --> 01:05:31.770
Literatur heißt das auch ein Paragraf.

01:05:32.830 --> 01:05:39.950
Das ist ein Graf mit der Eigenschaft, dass ich die Eckenmenge in zwei

01:05:39.950 --> 01:05:41.190
Teile zerlegen kann.

01:05:43.210 --> 01:05:47.990
In diesem Fall ist das der obere Teil und der untere Teil.

01:05:48.670 --> 01:05:52.970
Und ich stelle fest, irgendeine Ecke des oberen Teils ist nur mit

01:05:52.970 --> 01:05:55.870
einer Ecke des unteren Teils verknüpft und umgekehrt.

01:05:55.950 --> 01:06:00.430
Aber es gibt keine direkte Verbindung zwischen Ecken des oberen Teils

01:06:00.430 --> 01:06:01.050
untereinander.

01:06:02.950 --> 01:06:09.470
Und es gibt keine zwei Ecken des unteren Teils, die mit sich verknüpft

01:06:09.470 --> 01:06:09.690
werden.

01:06:12.990 --> 01:06:17.710
Diese Paragrafen kommen also vor in vielen Modellierungsaufgaben.

01:06:17.790 --> 01:06:19.730
Wir werden das noch bei Petri Netzen kennenlernen.

01:06:20.370 --> 01:06:27.750
In vielen kombinatorischen Problemen finden wir bipartite Grafen als

01:06:27.750 --> 01:06:31.850
Quelle von Zuordnungsproblemen.

01:06:32.650 --> 01:06:39.750
Hier ist ein ganz elementares, was auf den Herrn Hall 1935 zurückgeht

01:06:39.750 --> 01:06:44.450
und was das Heiratsproblem betitelt ist.

01:06:45.010 --> 01:06:47.710
Gegeben sind also N Jungs und N Mädchen.

01:06:47.930 --> 01:06:49.670
Leider Gottes ist die Zahl hier nicht gleich.

01:06:53.050 --> 01:06:55.230
Dann hat jeder Junge eine Menge Freundinnen.

01:06:56.210 --> 01:06:57.630
Ich habe das ein bisschen abgeschwächt.

01:06:58.350 --> 01:07:01.750
Und jedes Mädchen hat eine bestimmte Menge von Freunden.

01:07:02.210 --> 01:07:08.250
Und jetzt ist die Frage, können sie Heiratsvermittler spielen und Ehen

01:07:08.250 --> 01:07:14.030
stiften, so dass immer nur Paare zusammenkommen, die sich gegenseitig

01:07:14.030 --> 01:07:14.350
mögen.

01:07:16.070 --> 01:07:18.110
Und unter welchen Bedingungen können sie das?

01:07:21.930 --> 01:07:25.110
Und das ist genau ein bipartiter Graf.

01:07:25.190 --> 01:07:31.660
Da haben sie auf der einen Seite die Jungs und an der anderen Wand,

01:07:31.740 --> 01:07:35.800
wie in der Tanzschule, sitzen die Mädchen.

01:07:38.580 --> 01:07:41.860
Und die Marktbeziehung geht nur von oben nach unten bzw.

01:07:42.180 --> 01:07:43.320
unten nach oben.

01:07:52.220 --> 01:07:55.500
Und für diesen Grafen können sie also ganz offensichtlich kein

01:07:55.500 --> 01:07:56.940
Heiratsvermittler spielen.

01:07:57.720 --> 01:07:59.360
Da funktioniert das nicht.

01:08:01.460 --> 01:08:06.560
Der HH auch hat 1935 eine vollständige Bedingung bewiesen, unter denen

01:08:06.560 --> 01:08:12.540
das Heiratsproblem lösbar ist, nämlich für jede beliebige Teilmenge

01:08:12.540 --> 01:08:13.480
von Mädchen,

01:08:17.750 --> 01:08:22.070
und zwar von K-Mädchen, muss ich mindestens K-Jungen identifizieren

01:08:22.070 --> 01:08:23.750
können, die damit befreundet sind.

01:08:24.570 --> 01:08:25.930
Und das gilt auch umgekehrt.

01:08:26.850 --> 01:08:30.010
Wenn die Bedingung erfüllt ist, dann und nur dann ist das

01:08:30.010 --> 01:08:31.170
Heiratsproblem lösbar.

01:08:33.050 --> 01:08:37.670
Und das ist die praktische oder eher esoterische Formulierung der

01:08:37.670 --> 01:08:38.050
Geschichte.

01:08:38.790 --> 01:08:43.930
Sie finden in der Praxis sehr viele Beispiele einfacherer oder sogar

01:08:43.930 --> 01:08:48.570
komplizierterer Bauart für solche Zuordnungsprobleme, die alle direkt

01:08:48.570 --> 01:08:51.090
oder indirekt über bipartite Grafen gelöst werden.

01:08:51.090 --> 01:08:55.290
Das bekannteste und elementarste, gleichzeitig aber auch eines der

01:08:55.290 --> 01:09:01.810
schwierigsten Probleme ist das Stundenplanproblem, bei dem Sie nicht

01:09:01.810 --> 01:09:06.830
zwei, sondern drei Einheiten zusammenbringen müssen, nämlich Lehrer,

01:09:07.070 --> 01:09:07.990
Klasse und Stunde.

01:09:09.370 --> 01:09:13.190
Und jetzt mit allen möglichen Nebenbedingungen, keine Freistunden für

01:09:13.190 --> 01:09:20.530
die Klasse, keine Freistunden für die Lehrer, Doppelstunde, damit man

01:09:20.530 --> 01:09:24.250
da drinnen eine schriftliche Arbeit schreiben kann und lauter solche

01:09:24.250 --> 01:09:28.090
Nebenbedingungen, soll man also jetzt Schulstundenpläne aufstellen.

01:09:30.050 --> 01:09:34.850
Die Lösung funktioniert genau mit diesem Satz von Hall, allerdings

01:09:34.850 --> 01:09:40.310
kriegt man dann normalerweise nur Lösungen, die zu 95 oder 98 Prozent

01:09:40.310 --> 01:09:43.790
stimmen, den Rest muss man dann mit Hand korrigieren oder mit

01:09:43.790 --> 01:09:45.510
Hilfsmitteln der künstlichen Intelligenz.

01:09:45.750 --> 01:09:50.550
Das als Beispiel, wofür solche Dinge als Zuordnungsprobleme geeignet

01:09:50.550 --> 01:09:50.770
sind.

01:09:51.570 --> 01:09:56.590
Zum Thema Stundenplanplanung gibt es eine reichhaltige Literatur, die

01:09:56.590 --> 01:09:57.990
Sie auf dem Internet finden können.

01:10:01.900 --> 01:10:12.110
Wir nennen einen Graph markiert, wenn es eine Menge von Marken gibt

01:10:14.390 --> 01:10:18.750
und Markierungsfunktionen entweder für die Ecken oder für die Kanten

01:10:18.750 --> 01:10:19.510
oder beide,

01:10:23.770 --> 01:10:30.990
die es mir erlauben, den Kanten oder Ecken bestimmte Eigenschaften

01:10:30.990 --> 01:10:31.410
zuzuweisen.

01:10:31.410 --> 01:10:35.570
Als elementarstes Beispiel, wenn ich meinen Standardgraph wieder

01:10:35.570 --> 01:10:38.890
betrachte, dann ist das in Wahrheit ein markierter Graph gewesen.

01:10:39.010 --> 01:10:41.850
Ich habe nämlich sämtliche Ecken mit Namen versehen.

01:10:42.190 --> 01:10:44.210
Und das ist eine solche Markierungsfunktion.

01:10:44.770 --> 01:10:47.570
Wir geben eine Ecke, bestimmen den Namen der Ecke.

01:10:49.250 --> 01:10:54.910
Natürlich könnte ich genauso die Kanten auf diese Art und Weise

01:10:54.910 --> 01:10:55.490
markieren.

01:10:55.490 --> 01:11:01.810
In Wahrheit sind so ziemlich alle Graphen, die wir benutzen, in

01:11:01.810 --> 01:11:03.450
irgendeiner Art und Weise markiert.

01:11:03.590 --> 01:11:04.630
Nehmen Sie z.B.

01:11:04.770 --> 01:11:07.310
einen Kantorowitschbaum, den wir schon gehabt haben.

01:11:08.490 --> 01:11:11.930
Das ist erstens ein Baum im Sinne der Definition, die wir hier haben.

01:11:12.750 --> 01:11:16.110
Und wenn Sie da jetzt anschauen, was ich da hingemalt habe, da habe

01:11:16.110 --> 01:11:23.450
ich gesagt plus AB und ganz offensichtlich habe ich hier die Ecken

01:11:23.450 --> 01:11:23.990
markiert.

01:11:26.790 --> 01:11:29.450
Für den Menschen ist es also ganz selbstverständlich, dass er immer

01:11:29.450 --> 01:11:30.230
Ecken markiert.

01:11:32.410 --> 01:11:36.770
Kanten werden etwas seltener markiert im Normalleben, aber in der

01:11:36.770 --> 01:11:39.890
praktischen Anwendung kommt das ebenfalls sehr häufig vor.

01:11:40.290 --> 01:11:42.770
Ich zeige das hier am Beispiel eines Netzplans vor.

01:11:42.770 --> 01:11:50.790
Ein Netzplan ist eine Aussage darüber, wie bestimmte

01:11:50.790 --> 01:11:53.910
Aufgabenstellungen, wie lange die Zeit brauchen.

01:11:55.250 --> 01:11:59.210
In der Praxis sind da oft Minimum- und Maximumangaben da.

01:12:00.190 --> 01:12:05.230
Und jetzt stelle ich die Frage, wenn diese einzelnen Aufgaben so und

01:12:05.230 --> 01:12:09.370
so viel Zeit brauchen und in irgendeiner Weise miteinander

01:12:09.370 --> 01:12:10.190
zusammenhängen.

01:12:10.190 --> 01:12:10.970
Auf Wiedersehen!

01:12:13.550 --> 01:12:20.730
Dann möchte ich gerne wissen, wie wir bestimmen, ausgehend von einem

01:12:20.730 --> 01:12:23.910
bestimmten Anfangstag, wie lange braucht das ganze Ding?

01:12:24.230 --> 01:12:25.570
Minimal oder Maximal?

01:12:26.730 --> 01:12:32.270
Und Sie sehen also an diesem Beispiel, wenn Sie hier 8 Tage brauchen

01:12:32.270 --> 01:12:37.430
für die Aufgabe 1, 15 Tage für die Aufgabe 2, 10 Tage für die Aufgabe

01:12:37.430 --> 01:12:44.030
3, dann sind Sie an M1, M2, M4 zu unterschiedlichen Zeitpunkten.

01:12:45.270 --> 01:12:50.370
Und wenn das Ganze also alles endigt an der Stelle M8, rechnen Sie

01:12:50.370 --> 01:12:54.050
doch mal bitte aus, wie lange wir insgesamt brauchen.

01:13:01.850 --> 01:13:05.130
Und das Erste, was Sie feststellen, ist, das kann ich gar nicht.

01:13:07.170 --> 01:13:12.710
Denn, wenn ich nur einen Bearbeiter habe, dann muss der zum Beispiel

01:13:12.710 --> 01:13:16.030
T1, T2, T4 nacheinander bearbeiten.

01:13:22.310 --> 01:13:24.870
Und das heißt also dann, dass ich die sämtlichen Zeitdauern, die in

01:13:24.870 --> 01:13:26.710
diesem Diagramm stehen, zusammenzählen muss.

01:13:27.890 --> 01:13:32.410
Wenn ich jetzt zwei Bearbeiter habe, wie soll ich dann die Aufgaben

01:13:32.410 --> 01:13:35.010
verteilen auf die unterschiedlichen Bearbeiter, sodass ich

01:13:35.010 --> 01:13:36.410
kürzestmögliche Zeit bekomme?

01:13:38.800 --> 01:13:42.800
Und was wäre die optimale Anzahl von Bearbeitern, damit ich alle

01:13:42.800 --> 01:13:45.800
Aufgaben zusammengenommen in kürzester Zeit gelöst bekomme?

01:13:46.980 --> 01:13:50.840
Ich kann also ganz unterschiedliche Fragestellungen an einen solchen

01:13:50.840 --> 01:13:54.440
Netzplan anknüpfen, die alle von großer praktischer Relevanz sind.

01:13:57.690 --> 01:14:02.370
Was ich damit vorzeigen will, ist eigentlich nur, selbst wenn wir im

01:14:02.370 --> 01:14:07.470
Alltag üblicherweise nur Ecken markieren, die Markierung von Kanten

01:14:07.470 --> 01:14:12.750
hier mit Zeitdauer ist eine Aufgabenstellung, die in der Praxis von

01:14:12.750 --> 01:14:15.990
ungeheurer Bedeutung ist und die gleich auch noch zu sehr schwierigen

01:14:15.990 --> 01:14:17.070
Aufgabenstellungen führt.

01:14:19.630 --> 01:14:25.450
Also wenn Sie das Mautsystem auf den Autobahnen betrachten, dann

01:14:25.450 --> 01:14:28.830
können Sie auch solch einen Netzplan sehen und dann stellen Sie fest,

01:14:28.930 --> 01:14:30.790
dass die Leute sich offensichtlich berechnet haben.

01:14:37.050 --> 01:14:39.670
Andere Arten von Markierungen.

01:14:43.740 --> 01:14:48.640
Eine sehr häufig anzutreffende Form ist ein Graph, bei dem ich die

01:14:48.640 --> 01:14:56.200
sämtlichen Kanten in die Menge der natürlichen Zahlen abbilde, mit dem

01:14:56.200 --> 01:15:05.980
Ziel zu sagen, wenn du hier die Zahl 2 zugeordnet hast, dann bedeutet

01:15:05.980 --> 01:15:10.540
das in Wahrheit dasselbe, wie wenn ich von hier nach hier zwei Kanten

01:15:10.540 --> 01:15:11.400
gezeichnet hätte.

01:15:14.110 --> 01:15:18.030
Ich rede dann von einem Mehrfachgraph, das ist ein Graph, bei dem ich

01:15:18.030 --> 01:15:23.830
also mehrere Kanten zwischen zwei Ecken erlaube, was normalerweise

01:15:23.830 --> 01:15:26.250
nicht üblich ist, sondern verboten.

01:15:28.330 --> 01:15:32.430
Und das kann ich also wiedergeben durch einen Graphen mit

01:15:32.430 --> 01:15:33.270
Kantenmarkierung.

01:15:34.210 --> 01:15:40.550
Wenn ich zurückgehe auf mein Beispiel, was ich gerade hingemalt habe,

01:15:40.930 --> 01:15:46.930
mit dem Kantorowitschbaum, dann haben Sie entnommen, dass ich ganz

01:15:46.930 --> 01:15:49.510
offensichtlich A plus B gemeint habe.

01:15:51.390 --> 01:15:53.630
Und dass ich nicht gemeint habe B plus A.

01:15:55.510 --> 01:15:57.030
Woraus haben Sie das geschlossen?

01:16:04.640 --> 01:16:09.100
Das habe ich doch offensichtlich durch Hinschreiben und Lesen von

01:16:09.100 --> 01:16:10.500
links nach rechts herausgefunden.

01:16:11.640 --> 01:16:13.540
Aber ich habe nie laut darüber geredet.

01:16:15.440 --> 01:16:19.160
Und bei Bäumen schauen Sie jetzt die Definitionen an und da stellen

01:16:19.160 --> 01:16:21.900
Sie fest, von links und rechts ist da nicht die Rede.

01:16:24.620 --> 01:16:29.940
Das heißt, wenn ich da nur sage, das ist ein gerichteter Baum, dann

01:16:29.940 --> 01:16:33.680
ist zunächst einmal nicht auszuschließen, dass das B plus A ist.

01:16:34.840 --> 01:16:39.120
Erst dann, wenn ich jetzt den Begriff geordneter Baum einführe,

01:16:39.640 --> 01:16:47.040
nämlich eine Kantenmarkierung einführe, die für jede Kante sagt, das

01:16:47.040 --> 01:16:51.260
ist die erste, die zweite, die dritte, die von einem bestimmten Noten

01:16:51.260 --> 01:16:57.220
ausgeht, dann erst kann ich sagen, das ist der erste Operand und das

01:16:57.220 --> 01:16:58.180
ist der zweite Operand.

01:16:58.420 --> 01:17:03.900
Wenn ich das also hier unten als Kantorowitschbaum sehe, dann sehe

01:17:03.900 --> 01:17:07.080
ich, wenn ich hier hinschreibe, das ist der erste Operand, das ist

01:17:07.080 --> 01:17:12.820
hier der zweite, eins, zwei, eins, zwei, dann habe ich genau gesagt,

01:17:13.800 --> 01:17:14.840
wie das zu ordnen ist.

01:17:16.480 --> 01:17:22.260
Das wird bei solchen arithmetischen Ausdrücken implizit festgestellt.

01:17:23.440 --> 01:17:25.540
Es wird also immer von links nach rechts geordnet.

01:17:26.520 --> 01:17:29.360
Aber eigentlich muss man das ganz explizit dazu schreiben.

01:17:29.760 --> 01:17:34.280
Jeder Kantorowitschbaum oder sonstige Arten von Ableitungsbäumen, die

01:17:34.280 --> 01:17:38.060
wir malen, auch für Chomsky-Grammatiken, sind eigentlich geordnete

01:17:38.060 --> 01:17:42.800
Bäume, bei denen die Ordnungsrelation von links nach rechts geht.

01:17:42.800 --> 01:17:46.060
Sie sehen das auch an dem linken Beispiel.

01:17:49.880 --> 01:17:53.800
Schließlich gibt es dann die Ebenen- oder Plattengrafen.

01:17:54.780 --> 01:17:58.480
Auf Englisch heißt das Planargraph und es bürgert sich jetzt auch im

01:17:58.480 --> 01:18:00.500
Deutschen ein, dass das ein Planaragraph ist.

01:18:01.240 --> 01:18:07.560
Das ist ein Graph, den ich in der Ebene zeichnen kann, ohne dass es

01:18:07.560 --> 01:18:09.020
Überkreuzungen in der Kante gibt.

01:18:10.060 --> 01:18:14.100
Zum Beispiel solch eine Zeichnung, wie ich sie hier habe, die ist

01:18:14.100 --> 01:18:18.780
verboten, weil sich hier zwei Kanten kreuzen.

01:18:19.260 --> 01:18:22.380
Allerdings, wir haben das ja schon gesehen, ich kann diesen selben

01:18:22.380 --> 01:18:24.320
Graphen auch so malen, wie hier steht.

01:18:25.220 --> 01:18:26.720
Jetzt gibt es keine Überkreuzungen.

01:18:27.620 --> 01:18:32.680
Und da die Eigenschaft Planar eine abstrakte Eigenschaft ist, kommt es

01:18:32.680 --> 01:18:34.300
gar nicht darauf an, wie ich gezeichnet habe.

01:18:35.660 --> 01:18:39.340
Ich halte fest, dass dieser Graph genauso wie dieser Graph Planar

01:18:39.340 --> 01:18:42.300
sind, weil ich das ganze Ding so zeichnen kann.

01:18:44.040 --> 01:18:49.420
Wenn Sie aber mein Beispiel eines bipartiten Graphen mit drei Ecken

01:18:49.420 --> 01:18:53.080
oben und unten nehmen, der in der Hinsicht vollständig ist.

01:18:53.440 --> 01:18:55.040
Man nennt das den K3-3.

01:18:55.540 --> 01:18:59.740
Oben drei, unten drei Ecken und alles miteinander verbunden.

01:19:01.480 --> 01:19:03.400
Da können Sie sich anstrengen, wie Sie wollen.

01:19:05.520 --> 01:19:09.280
Den können Sie nicht zeichnen, ohne dass Sie irgendwelche Kreuzungen

01:19:09.280 --> 01:19:09.620
haben.

01:19:10.000 --> 01:19:14.780
Das heißt, das ist ein elementares Beispiel eines nicht planaren

01:19:14.780 --> 01:19:15.340
Graphen.

01:19:16.560 --> 01:19:23.080
Und ebenso ist der vollständige Graph K5 oder K6 oder irgendwelche

01:19:23.080 --> 01:19:27.880
solchen Dinge, wie wir sie früher hatten, der ist ebenfalls nicht

01:19:27.880 --> 01:19:28.400
planar.

01:19:35.220 --> 01:19:39.240
Planare Graphen sind in der Praxis sehr interessant und sehr wichtig.

01:19:39.860 --> 01:19:44.840
Beispiel, Sie haben irgendeine Platine, auf der Sie irgendwelche

01:19:44.840 --> 01:19:47.120
elektronischen Bauelemente montiert haben.

01:19:48.260 --> 01:19:52.600
Und jedes Bauelement ist eine Ecke eines Graphen.

01:19:52.980 --> 01:19:59.820
Und Kanten werden gezeichnet dann, wenn zwei dieser Elemente durch ein

01:19:59.820 --> 01:20:01.260
Draht miteinander verbunden werden.

01:20:02.120 --> 01:20:04.980
Zur Vermeidung von Kurzschlüssen möchten wir natürlich jetzt haben,

01:20:05.140 --> 01:20:07.100
dass diese Kanten sich nicht überschneiden.

01:20:08.600 --> 01:20:14.180
Sprich zu deutsch, wenn wir nur eine Zeichenebene haben, dann brauchen

01:20:14.180 --> 01:20:15.560
wir einen planaren Graphen.

01:20:15.640 --> 01:20:21.740
Sie müssen die Anordnung der Bauelemente so treffen, dass Sie einen

01:20:21.740 --> 01:20:22.740
planaren Graphen bekommen.

01:20:23.700 --> 01:20:28.980
Dann sehen Sie plötzlich, dass also die Frage, ist ein Graph planar,

01:20:29.580 --> 01:20:34.340
nicht nur eine Frage ist, die ich nachprüfe, sondern wo ich sogar

01:20:34.340 --> 01:20:35.420
konstruktiv vorgehe.

01:20:35.780 --> 01:20:40.580
Wie könnte ich erreichen, dass ein bestimmter Graph mit bestimmten

01:20:40.580 --> 01:20:43.460
vorgegebenen Bauelementen, bei denen ich aber noch nicht komplett

01:20:43.460 --> 01:20:46.740
gesagt habe, welche Verbindungen ich male, dass der planar wird.

01:20:46.740 --> 01:20:50.980
Sonst kann ich das ganze Ding nicht mit einer einschichtigen Platine

01:20:50.980 --> 01:20:52.120
belegen.

01:20:53.960 --> 01:20:58.520
Also wir haben viele technische Anwendungen, um kreuzungsfreie

01:20:58.520 --> 01:21:00.300
Leitungen zu bekommen und ähnliche Dinge.

01:21:00.820 --> 01:21:04.400
Und daher ist Planarität für die Praxis eine sehr wichtige Aufgabe.

01:21:05.400 --> 01:21:16.000
Es stellt sich heraus, dass der K5 und der K33 die grundlegenden

01:21:16.000 --> 01:21:23.540
Bösewichte sind, mit Hilfe derer ich überprüfen kann, ob irgendein

01:21:23.540 --> 01:21:25.960
Graph planar ist oder nicht planar.

01:21:27.020 --> 01:21:32.780
Wenn ein Graph nicht planar ist, dann muss ich irgendwelche Ecken

01:21:32.780 --> 01:21:39.860
aussondern können, die zusammen entweder einen K5 ergeben oder die

01:21:39.860 --> 01:21:41.720
zusammen einen K33 ergeben.

01:21:42.760 --> 01:21:45.980
Wenn ich sowas nicht identifizieren kann, dann ist der Graph planar.

01:21:46.860 --> 01:21:48.920
Das ist die intuitive Lösung des Problems.

01:21:49.500 --> 01:21:52.620
Natürlich werden wir dann noch Algorithmen kennenlernen, mit Hilfe

01:21:52.620 --> 01:21:56.020
derer wir mit dem Rechner feststellen können, ob die Eigenschaft

01:21:56.020 --> 01:21:57.020
gegeben ist oder nicht.

01:21:57.400 --> 01:22:00.680
Und das geht dann ein bisschen einfacher, als in einem Graph mit

01:22:00.680 --> 01:22:04.180
einigen hundert Ecken nachzuschauen, ob da ein K5 enthalten ist.

01:22:09.180 --> 01:22:11.060
Schließlich Repräsentation von Graphen.

01:22:11.380 --> 01:22:12.620
Jetzt fangen wir an zu rechnen.

01:22:13.440 --> 01:22:20.080
Wie könnten wir einen Graphen darstellen, sodass man damit rechnen

01:22:20.080 --> 01:22:20.260
kann?

01:22:20.320 --> 01:22:23.220
Dass man also beispielsweise die transitive Hülle berechnen kann.

01:22:23.220 --> 01:22:29.420
Dafür gibt es zwei Grundmethoden, wenn der Graph endlich ist.

01:22:30.220 --> 01:22:32.680
Die eine ist die Darstellung durch Adjacenzmatrix.

01:22:33.780 --> 01:22:41.280
Wir haben einen Graph mit N Ecken, nummeriert von 0 bis N-1

01:22:41.280 --> 01:22:41.960
beispielsweise.

01:22:46.600 --> 01:22:52.880
Und wir malen ein Kreuzchen rein, wenn die Ecke I verbunden ist mit

01:22:52.880 --> 01:22:54.400
der Ecke J.

01:22:54.720 --> 01:22:55.540
Seilen und Spalten.

01:22:59.330 --> 01:23:11.350
Das führt also zu dieser Definition einer Adjacenzmatrix.

01:23:11.350 --> 01:23:20.730
Und das würde also heißen, dass der Graph dargestellt wird, durch

01:23:20.730 --> 01:23:24.890
insgesamt N-Quadratelemente, sämtliche potenziellen Verbindungen sind

01:23:24.890 --> 01:23:26.450
mit 0 oder mit 1 belegt.

01:23:27.750 --> 01:23:30.910
Wenn der Graph vollständig ist, stehen überall Einsen drinnen.

01:23:31.830 --> 01:23:34.950
Die meisten Graphen... dürfen wir da auch mit lachen?

01:23:35.130 --> 01:23:37.970
Oder wenn Sie da drüben frühstücken wollen, dann gehen Sie doch bitte

01:23:37.970 --> 01:23:38.350
raus.

01:23:40.010 --> 01:23:41.470
Aufpassen tun Sie sowieso nicht.

01:23:41.890 --> 01:23:43.670
Also es ist völlig unklar, warum Sie hier sitzen.

01:23:46.150 --> 01:23:50.050
Das ist insbesondere eine Unverschämtheit, alle Umstehenden und

01:23:50.050 --> 01:23:51.430
Umsitzenden zu stören.

01:23:52.350 --> 01:23:54.750
Das geht nicht auf meine Kosten, das geht auf die Kosten Ihrer

01:23:54.750 --> 01:23:55.250
Kollegen.

01:24:01.260 --> 01:24:04.680
Also ich brauche N-Quadratelemente, um das alles darzustellen.

01:24:05.600 --> 01:24:09.160
Aber im ersten Anlauf zumindest habe ich immer nur eine Eins oder eine

01:24:09.160 --> 01:24:09.780
Null dastehen.

01:24:10.380 --> 01:24:12.880
Und das heißt, ich komme mit N-Quadrat-Bits aus.

01:24:13.480 --> 01:24:15.720
Ich brauche für jede Codierung genau ein Bit.

01:24:19.480 --> 01:24:21.940
Nummerweise, wenn ich nicht einen vollständigen oder fast

01:24:21.940 --> 01:24:25.240
vollständigen Graphen habe, stehen da drinnen fast nur Null.

01:24:26.460 --> 01:24:32.880
Und sowas nennt man dann eine dünn besetzte Matrix, wenn da fast nur

01:24:32.880 --> 01:24:33.780
Nullen drin stehen.

01:24:45.170 --> 01:24:47.930
Ja, und da stellt man sich natürlich die Frage, geht das nicht

01:24:47.930 --> 01:24:48.390
billiger?

01:24:48.390 --> 01:24:54.710
Und die nächste Idee wäre, wir schreiben nicht mehr überall Nullen und

01:24:54.710 --> 01:24:57.790
Einsen auf, sondern wir schreiben nur noch das Positive auf.

01:24:58.210 --> 01:25:01.730
Das heißt, für jede Ecke E schreiben wir die Menge der Nachbarn hin.

01:25:03.350 --> 01:25:07.150
Wir geben die Menge der Nachbarn als Liste an.

01:25:07.750 --> 01:25:09.390
Das nennt man dann eine Adjacenzliste.

01:25:18.100 --> 01:25:21.200
Und für unser Beispiel sehen Sie hier die Adjacenzmatrix.

01:25:22.660 --> 01:25:24.380
Und hier habe ich die Adjacenzliste hingeschrieben.

01:25:25.040 --> 01:25:28.640
Also A ist verknüpft mit B, C und D.

01:25:30.600 --> 01:25:31.400
Also mit allen.

01:25:31.980 --> 01:25:33.660
Aber C hat keine Nachbarn.

01:25:34.200 --> 01:25:35.620
Denn auch von C kommen sie nicht raus.

01:25:37.500 --> 01:25:39.980
Und das können Sie hier an den vielen Nullen sehen.

01:25:40.160 --> 01:25:42.700
Und hier sehen Sie es daran, dass ich eine Realität geschrieben habe.

01:25:44.520 --> 01:25:47.420
Also ich habe zwei verschiedene Darstellungen, mit beiden kann ich

01:25:47.420 --> 01:25:47.940
rechnen.

01:25:48.480 --> 01:25:52.360
Welche ich wähle, ich habe noch weitere Möglichkeiten hinterher, die

01:25:52.360 --> 01:25:54.060
Sie aber erst im zweiten Semester kennenlernen.

01:25:54.940 --> 01:25:58.800
Das ist jeweils eine Frage, was ist billiger?

01:25:59.620 --> 01:26:00.760
Das muss man nachrechnen.

01:26:01.340 --> 01:26:04.900
Also ich habe keine Religion, das eine ist besser als das andere.

01:26:04.900 --> 01:26:08.740
Sondern ich muss im Einzelfall nachrechnen, was besser ist.

01:26:10.220 --> 01:26:13.880
Bleiben wir aber zunächst bei den Adjacenzmatrixen.

01:26:14.260 --> 01:26:18.040
Da weiß ich zunächst, ich kann aus einer Adjacenzmatrix sofort

01:26:18.040 --> 01:26:22.360
ablesen, ob eine Relation reflexiv ist.

01:26:23.400 --> 01:26:27.120
Und an diesem Beispiel sehe ich also, die ist bestimmt nicht reflexiv.

01:26:28.520 --> 01:26:33.740
Denn reflexiv heißt, jedes Element ist mit sich selbst verbunden.

01:26:33.740 --> 01:26:34.820
Es gibt eine Schlinge.

01:26:35.580 --> 01:26:41.480
Und das würde heißen, dass ich in der Hauptdiagonal mit Index II

01:26:41.480 --> 01:26:43.740
einzelstehen haben müsste.

01:26:43.860 --> 01:26:47.820
Nur dann, wenn ich überall einzelstehen habe, ist die Relation

01:26:47.820 --> 01:26:48.680
reflexiv.

01:26:51.820 --> 01:26:55.040
Eine Relation ist symmetrisch, genau dann, wenn die Adjacenzmatrix

01:26:55.040 --> 01:26:55.900
symmetrisch ist.

01:26:58.420 --> 01:27:02.020
Jetzt erklärt sich also der Begriff symmetrische Relation ganz

01:27:02.020 --> 01:27:02.360
plötzlich.

01:27:03.560 --> 01:27:07.800
Und wenn ich jetzt zwei Relationen habe, Rho und Sigma, gegeben durch

01:27:07.800 --> 01:27:10.620
zwei verschiedene Adjacenzmatrixen A und B.

01:27:12.120 --> 01:27:16.360
Und ich frage, ist die Ecke I verknüpft mit der Ecke J durch die

01:27:16.360 --> 01:27:18.520
Verknüpfung der beiden Relationen Rho und Sigma.

01:27:19.120 --> 01:27:24.340
Dann muss es ja offenbar ein Zwischenelement K geben, sodass I Rho K

01:27:24.340 --> 01:27:25.780
gilt und K Sigma J.

01:27:27.640 --> 01:27:33.340
Und übersetzende Matrizen muss das also heißen, A I K muss 1 sein und

01:27:33.340 --> 01:27:34.620
B K J ist 1.

01:27:37.580 --> 01:27:43.500
Und das bedeutet, dass dann, wenn ich über sämtliche Möglichkeiten K

01:27:43.500 --> 01:27:50.860
zu wählen summiere, dann muss ich bei den Produktbildungen A I K mal B

01:27:50.860 --> 01:27:55.340
K J mindestens eine 1 gefunden haben, also die Summe über alle

01:27:55.340 --> 01:28:00.360
Möglichkeiten muss größer gleich 1 sein, dann gilt die Verknüpfung von

01:28:00.360 --> 01:28:00.940
I nach J.

01:28:02.360 --> 01:28:13.550
Ich finde sogar noch mehr, wenn ich zunächst einmal solch eine

01:28:13.550 --> 01:28:14.530
Relation habe,

01:28:18.730 --> 01:28:29.790
das wäre also Rho, und dann diese Beziehung, dann weiß ich also, es

01:28:29.790 --> 01:28:37.030
gibt zwei Wege von dieser Ecke zu dieser Ecke, wenn ich hier Identität

01:28:37.030 --> 01:28:37.330
habe.

01:28:39.230 --> 01:28:42.990
Und das ist gerade die Anzahl der Einsen, die ich in dieser Summe

01:28:42.990 --> 01:28:43.410
bekomme.

01:28:43.410 --> 01:28:45.950
Das heißt also, diese Summe ist sehr interessant.

01:28:48.570 --> 01:28:52.610
Wenn die N ist, dann weiß ich, es gibt N verschiedene Wege von dieser

01:28:52.610 --> 01:28:53.490
Ecke zu dieser Ecke.

01:28:56.640 --> 01:28:59.600
Nicht nur, dass ich herausfinden kann, gibt es überhaupt einen Weg,

01:29:00.360 --> 01:29:02.520
sondern ich kann außerdem noch feststellen, wie viele verschiedene

01:29:02.520 --> 01:29:03.220
Wege es gibt.

01:29:07.060 --> 01:29:12.700
Und insbesondere kann ich also sofort ablesen, ob eine Relation Rho

01:29:12.700 --> 01:29:13.660
-transitiv ist.

01:29:13.660 --> 01:29:17.520
Wenn sie transitiv ist, dann wissen wir, dass zweimalige Anwendung von

01:29:17.520 --> 01:29:24.200
Rho, Rho-Quadrat, nicht mehr geben kann, als was wir in Rho schon

01:29:24.200 --> 01:29:24.520
haben.

01:29:24.680 --> 01:29:26.260
Also Rho-Quadrate sind halt in Rho.

01:29:26.920 --> 01:29:27.780
Und was heißt das?

01:29:28.620 --> 01:29:38.260
Für beliebige Index-Triple IJK muss gelten, dass AIJ mal AJK kleiner

01:29:38.260 --> 01:29:39.580
gleich AIK ist.

01:29:39.580 --> 01:29:45.360
Null kann hier nur dann rauskommen, wenn mindestens eine dieser Dinge

01:29:45.360 --> 01:29:46.160
auch Null hat.

01:29:50.060 --> 01:29:54.940
Sonst könnte eins rauskommen und dann muss aber hier auch eins

01:29:54.940 --> 01:29:56.900
rauskommen, wenn das ganze Ding transitiv ist.

01:29:57.780 --> 01:30:08.040
Also ich kann an der Adjacenzmatrix sofort ablesen, was ich über

01:30:08.040 --> 01:30:09.500
Transitivität weiß.

01:30:09.500 --> 01:30:16.100
Und wenn Sie sich jetzt mal diese Summe hier anschauen, dann haben Sie

01:30:16.100 --> 01:30:18.320
diese Summe in der linearen Algebra auch schon gesehen.

01:30:21.700 --> 01:30:30.180
Das ist nämlich die Berechnung der Elemente CIJ für das

01:30:30.180 --> 01:30:31.800
Matrizenprodukt zweier Matrizen.

01:30:34.000 --> 01:30:40.960
Wenn ich also zwei Matrizen A und B habe und C berechne, dann sind die

01:30:40.960 --> 01:30:43.900
CIJ gerade diese Elemente.

01:30:43.900 --> 01:30:45.320
Wir sind gleich fertig.

01:30:48.080 --> 01:30:55.740
Und das heißt also, dass das Matrizenprodukt zweier Adjacenzmatrizen,

01:30:56.660 --> 01:31:03.880
das gibt mir klare Auskunft über die Frage, welche Wege der Länge 2

01:31:03.880 --> 01:31:09.380
gibt es, wenn ich beide Matrizen identisch wähle, also dieselbe

01:31:09.380 --> 01:31:10.440
Relation wähle.

01:31:10.440 --> 01:31:13.740
Und damit kann ich schon mal Transitivität feststellen, falls sie

01:31:13.740 --> 01:31:14.440
vorliegt.

01:31:15.740 --> 01:31:26.680
Und ich weiß noch mehr, wenn in einer Relation, wenn ich die L-Fach

01:31:26.680 --> 01:31:32.660
miteinander multipliziere, dann weiß ich, da kommt genau dann M

01:31:32.660 --> 01:31:38.120
heraus, wenn es insgesamt M verschiedene Wege der Länge L von I nach J

01:31:38.120 --> 01:31:38.420
gibt.

01:31:41.400 --> 01:31:44.860
Inklusive der Tatsache, wenn das Ding reflexiv ist, dann kann ich da

01:31:44.860 --> 01:31:46.980
irgendetwas reflektieren.

01:31:48.500 --> 01:31:52.200
Und insgesamt bekommen wir also, dass die Verknüpfung zweier

01:31:52.200 --> 01:31:56.320
Relationen der Multiplikation von Adjacenzmatrizen entspricht.

01:31:57.140 --> 01:31:58.020
Soviel für heute.

01:32:02.800 --> 01:32:07.360
Wie üblich, bevor Sie gehen, erheben Sie bitte Ihre Flieger auf.