WEBVTT

00:11.980 --> 00:17.020
So, einen wunderschönen guten Morgen und vorab noch alles Gute für das

00:17.020 --> 00:19.120
neue Jahr und viel Erfolg.

00:20.040 --> 00:24.120
Wir gehen jetzt langsam in den Endspurt über, noch ungefähr ein

00:24.120 --> 00:27.900
Drittel der Vorlesungszeit, ein bisschen weniger sogar übrig.

00:28.720 --> 00:35.280
An der Stelle machen wir jetzt weiter mit dem Begriff des Algorithmus.

00:35.400 --> 00:39.300
Da hatten wir noch ein Thema letztes Mal übrig und das war dieser ein

00:39.300 --> 00:42.440
bisschen seltsame Algorithmus zur Multiplikation nicht-negativer

00:42.440 --> 00:47.520
ganzer Zahlen, den wir als Beispiel verwenden wollen für eine

00:47.520 --> 00:48.560
Schleifeninvariante.

00:49.820 --> 00:54.760
Der basierte darauf auf den ganzzahligen Divisionen und dem Rest bei

00:54.760 --> 00:55.900
der ganzzahligen Division.

00:57.240 --> 01:02.440
Wichtig ist halt dieser Zusammenhang, dass sich jede natürliche Zahl

01:02.440 --> 01:05.400
xy...

01:05.880 --> 01:07.400
Da ist jetzt schon wieder der Fehler drin.

01:07.920 --> 01:09.260
Wer schreibt mir immer E-Mails?

01:10.540 --> 01:13.280
Danke, weil ganzzahlige Divisionen durch 0 geht immer noch nicht.

01:15.340 --> 01:20.040
xy-Element 0 gilt und das y muss aus einem n plus sein, wenn ich das

01:20.040 --> 01:20.660
richtig sehe.

01:21.860 --> 01:23.540
Durch 0 darf ich nicht dividieren.

01:24.260 --> 01:28.920
Also für jede natürliche Zahl x und jede positive natürliche Zahl y

01:28.920 --> 01:35.880
kann ich sowas hinschreiben wie x gleich y mal x div y plus halt den

01:35.880 --> 01:38.060
Rest, der dabei herausgekommen ist.

01:40.440 --> 01:41.340
Beispiele etc.

01:41.580 --> 01:42.500
kennen Sie alles von früher.

01:43.100 --> 01:46.740
Und dann gab es halt diesen Algorithmus, von dem behauptet wird, dass

01:46.740 --> 01:51.000
der zwei natürliche Zahlen a und b miteinander multipliziert.

01:53.760 --> 01:57.480
Da gibt es ein paar Variablen, die interessanten sind x, y und p.

01:57.640 --> 02:01.100
x ist am Anfang a, y ist am Anfang b und p ist am Anfang 0.

02:01.580 --> 02:03.940
Und dann gibt es noch eine Variable i, die hat eigentlich keine

02:03.940 --> 02:07.280
besondere Funktion, außer dass sie mitzählt, wie häufig wir die

02:07.280 --> 02:08.520
Weißschleife durchlaufen.

02:08.520 --> 02:14.480
Einfach nur den Interessen halber, aber hat auf die Funktionsweise

02:14.480 --> 02:17.520
dieses Algorithmus überhaupt keine Auswirkung.

02:21.340 --> 02:24.520
Wenn man jetzt wissen will, wie das Ganze funktioniert und vor allem,

02:24.620 --> 02:28.580
wo auch hinterher das Ergebnis steht, Spoiler, das Ergebnis soll

02:28.580 --> 02:33.000
hinterher in p stehen, kann man einfach mal so ein paar Beispielwerte

02:33.000 --> 02:33.620
aufschreiben.

02:33.620 --> 02:37.940
Man kann also mal a gleich 6 und b gleich 9 zum Beispiel nehmen und

02:37.940 --> 02:41.100
dann lässt man diese Schleife da ein paar mal durchlaufen.

02:41.280 --> 02:47.240
Man sieht halt, bevor man anfängt, ist halt p, i, 0, dann 6 und 9

02:47.240 --> 02:49.480
stehen halt für die Werte a und b in x und y.

02:50.100 --> 02:55.000
Und dann, nachdem ich die Schleife einmal durchlaufen habe, dann steht

02:55.000 --> 02:59.280
halt in p, i immer noch 0 und dann 3 und 18 in x, i und y, i.

02:59.280 --> 03:06.380
Dann beim zweiten Mal ist in p, i 18, in x noch 1 und in y 36 und dann

03:06.380 --> 03:11.820
nach dem dritten Schleifendurchlauf steht in p 54, in x, i 0 und in y

03:11.820 --> 03:12.560
42.

03:13.120 --> 03:19.220
Und 6 mal 9 sind eben gerade 54, also genau das Ergebnis, das bei

03:19.220 --> 03:19.460
herauskommt.

03:19.460 --> 03:25.400
Und die Idee ist natürlich jetzt nachzuweisen, dass dieser Algorithmus

03:25.400 --> 03:29.060
immer funktioniert und da haben wir halt kennengelernt die Hohrtüppel

03:29.060 --> 03:32.460
und insbesondere ganz zum Schluss die Schleifeninvariante.

03:33.260 --> 03:35.460
Und da man hier halt so eine Schleife hat, wird wohl die

03:35.460 --> 03:38.120
Schleifeninvariante das insbesondere Interessante sein.

03:39.440 --> 03:43.360
Wenn man jetzt das Ganze mit Hohrtüppeln nachweisen will und wir

03:43.360 --> 03:46.460
weisen das jetzt hier nach, aber wir schreiben nicht alle trivialen

03:46.460 --> 03:51.180
Hohrtüppel jetzt unbedingt hin, hat man ja gesagt, man geht von hinten

03:51.180 --> 03:53.040
nach vorne, von unten nach oben durch.

03:53.680 --> 03:57.240
Ich brauche also irgendwie eine Nachbedingung.

03:57.360 --> 04:01.500
Ich hätte gerne, dass p gleich a mal b gilt und ich brauche am Ende

04:01.500 --> 04:02.680
irgendeine Vorbedingung.

04:02.960 --> 04:06.720
Wenn ich eine allgemeingültige Vorbedingung nehme, kann ich die immer

04:06.720 --> 04:10.240
sicher hinschreiben, also sowas wie 0 gleich 0 als Vorbedingung kann

04:10.240 --> 04:11.520
ich immer problemlos hinschreiben.

04:11.520 --> 04:16.660
Und dann ist der größte Knackpunkt, was machen wir mit der Schleife?

04:16.760 --> 04:18.420
Was machen wir mit der Schleifeninvariante?

04:18.880 --> 04:22.300
Diese ganzen einzelnen einfachen Zuweisungen, die kann ich einfach,

04:22.380 --> 04:25.040
das hatten wir gesehen, von hinten nach vorne zurückrechnen und da

04:25.040 --> 04:27.560
immer Vor- und Nachbedingungen zwischen jeder Anweisung schreiben.

04:27.980 --> 04:29.960
Aber was machen wir mit der Schleifeninvariante?

04:30.060 --> 04:31.800
Da brauche ich so eine Schleifeninvariante.

04:31.800 --> 04:34.160
Ich brauche etwas, was vor der Schleife gilt.

04:34.880 --> 04:39.040
Was vor der Schleife gilt ist, wenn man einfach sich die Zuweisung

04:39.040 --> 04:42.740
anguckt, x mal y plus p gleich a mal b gilt immer, weil p halt 0 ist

04:42.740 --> 04:44.340
und x ist a und y gleich b.

04:44.420 --> 04:47.540
Das könnte man jetzt auch noch absichern durch so Hortwippel, aber das

04:47.540 --> 04:50.960
ist jetzt so trivial, dass wir uns an der Stelle schenken, sondern wir

04:50.960 --> 04:52.840
müssen uns jetzt halt überlegen, was brauchen wir noch für die

04:52.840 --> 04:53.620
Schleifenvariante.

04:56.480 --> 04:59.600
Da ist natürlich das eine, das einfache ist diese Abbruchbedingung,

04:59.740 --> 05:01.820
dieses x größer 0.

05:02.140 --> 05:06.520
Das heißt, am Anfang einer der Schleife, wenn ich reingehe, gilt immer

05:06.520 --> 05:07.420
x größer 0.

05:08.420 --> 05:10.580
Das wird da auf alle Fälle irgendwie stehen müssen.

05:11.660 --> 05:14.960
Und jetzt ist halt die Frage, schön wäre es ja, wenn dieses x mal y

05:14.960 --> 05:19.160
plus p gleich a mal b immer gelten würde.

05:21.560 --> 05:24.420
Sowohl am Anfang der Schleife, wenn ich es durchlaufen habe, als auch

05:24.420 --> 05:27.380
wenn ich die Sachen der Schleife abgearbeitet habe.

05:27.740 --> 05:30.340
Das Einzige, was ich halt am Ende der Schleife nicht mehr weiß, ob das

05:30.340 --> 05:33.000
x immer noch größer 0 ist oder nicht, sondern das weiß ich erst, wenn

05:33.000 --> 05:35.080
ich das nächste Mal wieder in die Schleife reingehe.

05:35.080 --> 05:38.300
Und ich hätte halt gerne, dass wenn die Schleife zu Ende durchlaufen

05:38.300 --> 05:42.240
wurde, halt entsprechend gilt, dass immer noch dieses x mal y plus p

05:42.240 --> 05:43.580
gleich a mal b ist.

05:44.320 --> 05:47.460
Und dass halt, wenn die Schleife zu Ende ist, dass x logischerweise

05:47.460 --> 05:50.260
nicht mehr größer 0 ist, weil wenn es größer 0 wäre, würde ich ja die

05:50.260 --> 05:51.080
Schleife durchlaufen.

05:51.080 --> 05:54.560
Und ich hätte jetzt immer noch gerne meine Abschlussbedingung, dass

05:54.560 --> 05:58.300
das p auch gleich a mal b sein muss.

05:59.640 --> 06:03.640
Dementsprechend beißt sich das auch nicht, das kann man sich

06:03.640 --> 06:09.400
überlegen, weil x mal y plus p gleich a mal b und x ist nicht mehr

06:09.400 --> 06:10.120
größer 0.

06:10.120 --> 06:13.360
x kann aber auch nicht kleiner 0 sein, sondern x muss gleich 0 sein.

06:13.500 --> 06:15.240
Das heißt, x mal y ist auf alle Fälle 0.

06:15.740 --> 06:20.600
Das heißt, dieses x mal y plus p gleich a mal und so weiter und so

06:20.600 --> 06:24.840
fort, wenn ich da einfach die Nachbedingung verschärfe, komme ich eben

06:24.840 --> 06:26.460
gerade bei dem p gleich a mal b.

06:26.820 --> 06:30.580
Das heißt also, diese Nachbedingung der Schleife passt genau zu dieser

06:30.580 --> 06:33.080
Nachbedingung, die ich insgesamt gerne haben möchte für den

06:33.080 --> 06:33.680
Algorithmus.

06:34.480 --> 06:38.120
Das heißt, da sind wir also mit so einer Schleifenvariante auf der

06:38.120 --> 06:38.820
sicheren Seite.

06:40.660 --> 06:45.640
Was wir jetzt halt noch nicht wissen ist, ob diese Schleifeninvariante

06:45.640 --> 06:46.360
denn immer gilt.

06:46.500 --> 06:51.340
Wenn wir jetzt halt von unten nach oben gehen, p gleich a mal b ist

06:51.340 --> 06:52.240
das, was wir gerne hätten.

06:52.360 --> 06:55.940
Das können wir auch schreiben als x mal y plus p gleich a mal b und

06:55.940 --> 06:57.760
nicht x größer 0.

06:59.320 --> 07:01.520
Beides logisch gleichbedeutend.

07:01.760 --> 07:04.800
Wenn ich jetzt in die Schleife reingehe, fällt erst mal unten dieses

07:04.800 --> 07:08.020
nicht x größer 0 fällt weg.

07:08.520 --> 07:11.260
Und jetzt muss ich halt mit den einfachen Hortwippeln mich von dieser

07:11.260 --> 07:15.460
letzten Bedingung innerhalb der Schleife Schritt für Schritt

07:15.460 --> 07:16.460
hochhangeln.

07:17.420 --> 07:24.420
Und dadurch, dafür löse ich jetzt einfach immer diese Zuweisung der

07:24.420 --> 07:26.000
Variablen rückwärts auf.

07:26.540 --> 07:30.560
Das heißt also, wenn ich also y durch 2 mal y ersetze und es soll halt

07:30.560 --> 07:34.080
x mal y plus p gleich a mal b rauskommen, dann heißt das also vor der

07:34.080 --> 07:38.540
Zuweisung musste halt stehen, dass x mal 2 y plus p gleich a mal b

07:38.540 --> 07:38.700
ist.

07:38.700 --> 07:42.420
Dann kann ich halt die Variable y durch 2 y ersetzen, um da

07:42.420 --> 07:43.600
rauszukommen, wo ich hin will.

07:44.060 --> 07:46.780
Und genauso mache ich jetzt halt wieder den Schritt zurück, dass wenn

07:46.780 --> 07:51.060
ich da x mit x div 2 ersetze und es soll halt am Ende x mal 2 y plus p

07:51.060 --> 07:56.300
gleich a mal b rauskommen, dann muss halt vorher oben x div 2 mal 2 y

07:56.300 --> 07:57.720
plus p gleich a mal b sein.

07:57.720 --> 08:00.800
Und genauso mache ich das mit der Zuweisung von dem p.

08:01.220 --> 08:04.100
Und die Zuweisung von dem i ist sowieso egal, weil das i in diesen

08:04.100 --> 08:06.400
ganzen Bedingungen nicht vorkommt.

08:06.480 --> 08:09.140
So das finde ich jetzt also, dass diese Anweisung innerhalb der

08:09.140 --> 08:13.840
Schleife zurückverfolgt habe, ich oben dann herausbekomme, dass also x

08:13.840 --> 08:20.980
div 2 mal 2 y plus p plus x mod 2 mal y gleich a mal b gelten soll.

08:20.980 --> 08:25.000
Und ich hätte halt gerne gehabt, dass x mal y plus p gleich a mal b

08:25.000 --> 08:26.300
und x größer 0 gilt.

08:26.860 --> 08:30.440
Das heißt, was ich gerne hätte, ist, dass dieses x mal y plus p gleich

08:30.440 --> 08:36.240
a mal b und x größer 0 eine Verallgemeinerung wäre, dieses anderen,

08:36.880 --> 08:39.380
dieses x div 2 und so weiter, das ich durch die Hohrtrippe

08:39.380 --> 08:44.480
nachgewiesen habe, weil ich ja dafür diese Regel habe der Erweiterung

08:44.480 --> 08:45.300
der Vorbedingungen.

08:46.160 --> 08:49.100
Da hilft mir jetzt ein bisschen hin und her rechnen.

08:49.780 --> 08:54.500
Ich kann einfach dieses x div 2 mal 2 y plus p plus x mod 2 mal y

08:54.500 --> 08:59.440
einfach umschreiben, indem ich da das y rausziehe.

08:59.440 --> 09:02.820
Bei dem p kann ich kein y rausziehen, das heißt ein plus p bleibt

09:02.820 --> 09:06.960
hinten stehen, aber bei dem Rest kann ich ein y rausziehen, sodass

09:06.960 --> 09:12.420
dann hinterher da stehen bleibt 2 mal x div 2 plus x mod 2 in großen

09:12.420 --> 09:18.980
Klammern mal y plus p und da hätte ich gerne, dass das x mal y plus p

09:18.980 --> 09:20.700
sein soll.

09:20.700 --> 09:27.240
Und das ist es auch, wenn wir uns an diese Rechenregel erinnern, dass

09:27.240 --> 09:36.100
ich halt so ein x auch unter anderem schreiben kann als 2 mal x div 2

09:36.100 --> 09:40.080
plus x mod 2, dass das eben gerade wieder x ist.

09:40.080 --> 09:43.720
Das hatten wir allgemein kennengelernt, dass ich jede Zahl darstellen

09:43.720 --> 09:49.820
kann x als y mal x div y plus x mod y und das y ist jetzt halt an der

09:49.820 --> 09:54.460
Stelle aus der Regel hier eine 2, das heißt also 2 x div 2 plus x mod

09:54.460 --> 09:58.120
2 ist eben gerade gemäß dieser Regel x, sodass da wirklich steht x mal

09:58.120 --> 09:59.820
y plus p.

09:59.820 --> 10:04.900
Das heißt, ich habe, Entschuldigung, das ist eine Verschärfung, ich

10:04.900 --> 10:10.940
habe sozusagen da oben stehen x mal y plus p gleich a mal b und jetzt

10:10.940 --> 10:15.180
verschärfe ich noch durch das und x größer 0 und das darf ich halt

10:15.180 --> 10:18.860
gemäß dieser Regel der Verschärfung der Vorbedingungen.

10:21.160 --> 10:27.980
Das heißt also, am Ende habe ich wirklich diese drei Dinge, die ich

10:27.980 --> 10:31.520
gerne hätte, durch die Hortrippel, durch das Rückverfolgen der

10:31.520 --> 10:34.440
Variablenzuweisung und das geschickte Hinschreiben der

10:34.440 --> 10:39.000
Schleifenbedingungen und dann der Anwendung dieser Regel HTA Schleife

10:39.000 --> 10:44.460
nachgewiesen, dass ich wirklich bei der Vorbedingung 0 gleich 0 und

10:44.460 --> 10:47.900
bei der Ausführung des Algorithmuses dann hinterher stehen habe, dass

10:47.900 --> 10:51.400
in der Variable p wirklich a mal b drin steht.

10:54.970 --> 10:55.110
Okay.

10:56.910 --> 10:59.010
Was sollen Sie aus diesem Kapitel mitnehmen?

10:59.810 --> 11:03.250
Zum einen diesen Algorithmusbegriff, den wir eingeführt haben, der

11:03.250 --> 11:05.710
zugemäßermaßen etwas informell ist.

11:06.490 --> 11:08.930
Nichtsdestotrotz wäre es trotzdem wichtig, dass Sie so die gewissen

11:08.930 --> 11:12.570
Eigenschaften, die wir von einem Algorithmus in diesem Rahmenwerk

11:12.570 --> 11:15.650
haben, kennen, sowas wie Determinismus, dass Sie auch wissen, was

11:15.650 --> 11:16.810
Determinismus ist.

11:16.890 --> 11:20.730
Endliche Eingabe, endliche Ausgabe, endliche Laufzeit, endliche Anzahl

11:20.730 --> 11:23.530
elementarer verständlicher Anweisungen und so weiter und so fort.

11:23.530 --> 11:26.790
Und im Idealfall, dass Sie auch so ein bisschen diskutieren können,

11:27.390 --> 11:31.790
ist das wirklich 100% sinnvoll, diese ganzen Bedingungen oder gibt es

11:31.790 --> 11:34.490
vielleicht in der Praxis Ausnahmen, wo man gegen ein oder andere

11:34.490 --> 11:38.090
dieser Bedingungen verstoßen möchte, dass das Ganze also wirklich nur

11:38.090 --> 11:41.650
ein einfacher Algorithmusbegriff ist und dass Sie hinter der Praxis

11:41.650 --> 11:44.970
eigentlich viel kompliziertere erkennen lernen sollen.

11:46.830 --> 11:51.270
Hortrippel sollten Sie verstanden haben, auch wenn man da sozusagen

11:51.270 --> 11:55.690
den Handschuh immer auf links zieht, weil man sich selten hinsetzen

11:55.690 --> 11:58.330
kann und sagen kann, ich habe hier einen Algorithmus und jetzt gehe

11:58.330 --> 12:00.830
ich von vorne nach hinten durch und schreibe die Hortrippel hin und

12:00.830 --> 12:04.710
dann ist bewiesen, meistens habe ich irgendwie einen Algorithmus und

12:04.710 --> 12:07.550
muss dann von hinten nach vorne die Hortrippel hinschreiben, damit ich

12:07.550 --> 12:09.630
halt den Beweis schön nachweisen kann.

12:10.150 --> 12:14.590
Und halt als die komplizierteste Geschichte bei der ganzen Sache ist

12:14.590 --> 12:17.370
immer, dass man dann die Schleifeninvarianten findet.

12:17.470 --> 12:20.950
Das ist das, wo man nicht nach Schema F vorgehen kann, sondern wo man

12:20.950 --> 12:25.110
halt, Schema F ist immer Vorbedingungen, Nachbedingungen, also

12:25.110 --> 12:27.750
Abbruchbedingungen der Schleife entsprechend reinzuschreiben.

12:27.750 --> 12:31.550
Das ist einfach, aber sozusagen das, was invariant ist während der

12:31.550 --> 12:33.990
Schleife, was sich also nie ändern soll, während ich durch die

12:33.990 --> 12:37.170
Schleife durchlaufe, das zu sehen ist manchmal ein bisschen schwierig

12:37.170 --> 12:40.930
und manchmal helfen halt so einfache Dinge wie, ich schreibe mir halt

12:40.930 --> 12:44.350
mal so ein paar Schleifendurchläufe hin, ein paar kleines Beispiel.

12:45.090 --> 12:49.590
Meistens hilft das dann ein bisschen beim Verständnis, was da in

12:49.590 --> 12:50.870
dieser Schleife wirklich passiert.

12:53.190 --> 12:56.190
Damit beantworten wir jetzt die Frage des Kommilitonen von vorhin.

12:56.310 --> 12:58.910
Wir schaffen es heute tatsächlich dann zum Kapitel Grafen.

13:01.550 --> 13:04.870
Was wir jetzt sozusagen machen für den Rest der Vorlesung, damit sie

13:04.870 --> 13:09.230
so ein bisschen ein Gefühl dafür bekommen, wir springen jetzt so ein

13:09.230 --> 13:10.110
bisschen hin und her.

13:10.210 --> 13:13.110
Wir haben jetzt Algorithmus und können beweisen, was ein Algorithmus

13:13.110 --> 13:13.670
korrekt ist.

13:13.670 --> 13:17.510
Jetzt schauen wir uns an, was sind Grafen, so im Sinne von Struktur

13:17.510 --> 13:19.250
und was sind so Eigenschaften von Grafen.

13:19.670 --> 13:22.590
Dann springen wir wieder zurück und schauen uns an, was haben wir denn

13:22.590 --> 13:29.910
für Algorithmen, die wir auf Grafen anwenden können und springen

13:29.910 --> 13:33.130
wieder zurück ein bisschen im Sinne von, wie können wir

13:33.130 --> 13:37.110
quantifizieren, was so die Laufzeit ist von Algorithmen, nicht nur von

13:37.110 --> 13:39.770
Grafenalgorithmen, sondern von Algorithmen im Allgemeinen.

13:40.410 --> 13:44.430
Dann springen wir wieder zurück zu etwas, was man als grafische

13:44.430 --> 13:45.790
Modelle auffassen könnte.

13:45.930 --> 13:50.190
Das sind dann sogenannte endliche Automaten, die letztendlich auch

13:50.190 --> 13:52.190
schön durch Grafen repräsentiert werden können.

13:53.150 --> 13:56.250
Und dann ganz zum Schluss kommen wir dann irgendwann hin zu einem sehr

13:56.250 --> 14:00.550
interessanten endlichen Automaten, der Turing-Maschine, mit der wir

14:00.550 --> 14:03.930
letztendlich, wenn wir so wollen, alles beschreiben können, was wir in

14:03.930 --> 14:05.310
der Informatik denn machen können.

14:06.190 --> 14:09.470
Und damit wir halt da hinkommen, fangen wir an mit dem einfachen

14:09.470 --> 14:10.470
Beispiel Grafen.

14:10.930 --> 14:15.350
So rein intuitiv, was denn Graf ist, haben Sie schon mehrmals in der

14:15.350 --> 14:16.710
Vorlesung kennengelernt.

14:16.810 --> 14:19.730
Sie haben zum Beispiel sowas wie gesehen wie Bäume und nichts anderes.

14:19.970 --> 14:22.670
Und ein Baum ist auch nichts anderes als eine besondere Art des

14:22.670 --> 14:23.590
Grafen.

14:24.630 --> 14:28.750
Anschaulich macht man das, man hat halt Kreise und die werden halt

14:28.750 --> 14:32.950
verbunden mit so Pfeilen häufig bei uns.

14:34.130 --> 14:38.090
Die Kreise, die nennt man jetzt in einem Graf die Knoten, auf Englisch

14:38.090 --> 14:43.130
Vertex, und die Pfeile, die nennen wir halt die Kanten, auf Englisch

14:43.130 --> 14:44.470
Edge.

14:48.010 --> 14:51.730
Und wenn Sie viel mit der Informatik zu tun haben hinterher, werden

14:51.730 --> 14:56.890
Sie an wahrscheinlich 90%, wenn nicht sogar 100% aller Stellen der

14:56.890 --> 14:59.870
Informatik irgendwann was mit Grafen zu tun haben.

14:59.990 --> 15:02.690
Grafen sind wichtig für Algorithmen, Grafen sind wichtig für

15:02.690 --> 15:07.030
Netzwerke, Grafen sind wichtig für Datenbanken, Grafen sind extrem

15:07.030 --> 15:10.030
wichtig in allem, was mit maschinellem Lernen und mit künstlicher

15:10.030 --> 15:11.190
Intelligenz zu tun hat.

15:13.650 --> 15:16.690
Also mir fällt es gerade schwer, einen Bereich zu finden der

15:16.690 --> 15:20.590
Informatik, wo man eigentlich nicht mit Grafen unter anderem auch

15:20.590 --> 15:22.270
arbeiten würde.

15:22.710 --> 15:25.890
Dementsprechend gibt es auch an der Fakultät mehrere Lehrstühle, die

15:25.890 --> 15:29.890
sich auch auf sehr grundlegender Ebene mit Grafen und

15:29.890 --> 15:34.330
Grafenalgorithmen beschäftigen und die aber auch so interessante Dinge

15:34.330 --> 15:36.510
damit machen wie Routenplanung.

15:36.510 --> 15:42.050
Also wenn Sie Ihr GPS-Navigationssystem anwerfen oder bei Google Maps

15:42.050 --> 15:45.330
nachschauen, wie Sie von A nach B kommen, dann sind das alles komplexe

15:45.330 --> 15:46.770
Grafenprobleme.

15:46.930 --> 15:50.990
Selbst wenn Sie sowas machen wie Sie suchen Webseiten, ist das

15:50.990 --> 15:53.550
letztendlich auch nichts anderes als ein Grafenproblem, weil die

15:53.550 --> 15:55.970
Webseiten sich ja gerade dadurch auszeichnen, dass sie miteinander

15:55.970 --> 15:58.370
verlinkt sind und dann haben Sie wieder einen Graf, weil dann haben

15:58.370 --> 16:02.130
Sie Webseiten halt als Knoten und Links als Kanten.

16:03.150 --> 16:06.830
Also mit anderen Worten, das ist etwas, das ist extrem wichtig und

16:06.830 --> 16:10.490
extrem hilfreich, unter anderem auch, weil wir uns so schön was unter

16:10.490 --> 16:12.350
solchen Grafen manchmal auch vorstellen können.

16:12.450 --> 16:13.990
Das hilft der Anschaulichkeit deutlich.

16:16.570 --> 16:23.470
Ein beliebtes Beispiel ist das sogenannte Königsberger Brückenproblem.

16:25.130 --> 16:29.590
Das da ist halt ein alter Stadtplan der damaligen Stadt Königsberg,

16:29.710 --> 16:35.210
heute das ganze unter dem Namen Kaliningrad als russische Enklave in

16:35.210 --> 16:37.410
dem, was früher mal Ostpreußen war.

16:38.190 --> 16:45.110
Und man sieht da durch Königsberg fließt so ein Fluss, da fließen

16:45.110 --> 16:46.150
eigentlich zwei Flüsse.

16:46.670 --> 16:49.270
Aber ich glaube, wir haben das ein bisschen farblich hervorgehoben.

16:50.370 --> 16:52.050
Da sieht man es so schön blau.

16:52.430 --> 16:54.610
Da geht es halt von rechts ein Fluss, von links ein Fluss.

16:54.610 --> 16:59.630
Dann fließen die einmal so ums Karree und dann sozusagen da ein Arm

16:59.630 --> 17:00.690
geht nach links raus.

17:01.530 --> 17:04.170
Das heißt, die Stadt wird dadurch so ein bisschen in Bereiche

17:04.170 --> 17:07.690
eingeteilt durch diese Flüsse, Kanäle und dann gibt es halt

17:07.690 --> 17:09.310
entsprechend Brücken über diese Flüsse.

17:09.310 --> 17:11.670
Insgesamt der Brücken sieben.

17:12.830 --> 17:18.490
Und die Frage, die man sich jetzt gestellt hatte, war, gibt es einen

17:18.490 --> 17:27.370
Spaziergang, so dass ich durch Königsberg spaziere und dabei jede

17:27.370 --> 17:30.470
Brücke genau einmal überquere.

17:30.470 --> 17:34.930
Also kann ich irgendwo da losgehen, dann marschiere ich durch die

17:34.930 --> 17:39.090
Stadt, hin und wieder überquere ich eine Brücke und am Ende meines

17:39.090 --> 17:42.570
Spaziergangs habe ich alle Brücken überquert und ich habe jede Brücke

17:42.570 --> 17:47.030
auch dabei nur genau ein einziges Mal überquert.

17:49.470 --> 17:52.990
Und eine der interessanten Fragestellungen ist, gibt es so einen

17:52.990 --> 17:55.190
Spaziergang, also existiert sowas überhaupt.

17:56.050 --> 17:59.090
Man hat sich halt hingesetzt und geguckt und halt rumprobiert und

17:59.090 --> 18:03.570
irgendwie hat man nie was gefunden, nur weil man halt nicht in der

18:03.570 --> 18:06.190
Lage ist, was zu finden, ist das leider noch kein Beweis dafür, dass

18:06.190 --> 18:07.170
das auch nicht existiert.

18:07.170 --> 18:10.050
Manchmal ist auch man einfach zu blind oder zu dumm, das zu finden.

18:10.550 --> 18:15.610
Und 1736 hat Euler halt postuliert, dass es eben keinen Spaziergang

18:15.610 --> 18:19.670
gibt, so dass man über jede Brücke genau einmal kommt, nur bis das

18:19.670 --> 18:23.630
Ganze auch bewiesen wurde, hat es eine ganze Weile gedauert und da hat

18:23.630 --> 18:27.050
es insbesondere dann auch der Informatik bedurft, damit man sowas

18:27.050 --> 18:29.310
wirklich schön formal auch beweisen kann.

18:31.430 --> 18:37.150
Wenn wir uns und da eine Sache, die man halt versucht und damit

18:37.150 --> 18:41.590
arbeitet, ist halt mit Graphen dieses Problem der Spaziergänge halt

18:41.590 --> 18:44.230
mit Hilfe von Graphen darzustellen.

18:44.490 --> 18:47.150
Am Ende des Kapitels sehen wir dann noch, dass das gar nicht so

18:47.150 --> 18:50.270
einfach ist, wie man jetzt an erster Stelle denken würde, daraus

18:50.270 --> 18:53.210
überhaupt erstmal eine formale Beschreibung im Sinne von Graphen zu

18:53.210 --> 18:53.450
machen.

18:54.250 --> 18:57.610
Und wenn wir uns also mit Graphen beschäftigen, müssen wir uns halt im

18:57.610 --> 19:02.010
Klaren darüber sein, was sind Graphen überhaupt und Graphen, die wir

19:02.010 --> 19:04.570
haben, unterteilen wir erstmal in zwei grobe Klassen.

19:05.130 --> 19:09.670
Die sogenannten gerichteten Graphen und die ungerichteten Graphen.

19:09.670 --> 19:13.570
Und dann kann man sowohl gerichtete Graphen als auch ungerichtete

19:13.570 --> 19:18.870
Graphen immer noch mit Knoten oder Kantenmarkierungen versehen, um

19:18.870 --> 19:22.850
dann noch hilfreichere, mächtigere Graphen zu bekommen.

19:23.570 --> 19:30.710
An dieser Stelle eine ganz große, große Warnung oder ein ganz großes

19:30.710 --> 19:31.390
Passen Sie auf.

19:31.490 --> 19:35.050
Ich sage Ihnen ja immer, nehmen Sie auch andere Literatur als nur die

19:35.050 --> 19:37.650
Vorlesung zur Hilfe.

19:38.470 --> 19:40.710
Und das ist auch in der Tat richtig und wichtig.

19:40.710 --> 19:46.770
Aber gerade insbesondere beim Thema Graphen gilt ganz wichtig, schauen

19:46.770 --> 19:48.830
Sie genau auf die Definitionen.

19:49.630 --> 19:53.350
Ich hatte da auch schon mit Herrn Worscht Diskussionen und da ging es

19:53.350 --> 19:57.510
dann darum und dann nachgeschaut und anders als bei uns in der

19:57.510 --> 19:59.710
Vorlesung, aber warum und wieso und weshalb.

19:59.710 --> 20:02.030
Und man muss da wirklich höllisch aufpassen.

20:02.150 --> 20:06.430
Unterschiedliche Lehrbücher definieren manche Begriffe unterschiedlich

20:06.430 --> 20:10.470
und es führt zu unterschiedlichen Eigenschaften, Verhalten und anderen

20:10.470 --> 20:12.170
Algorithmen gegebenenfalls.

20:12.450 --> 20:16.690
Oder wie es Herr Worscht gesagt, ausgedrückt hat, Zitat, Graphen

20:16.690 --> 20:20.070
schrecklich, zwei Bücher, drei Definitionen.

20:20.950 --> 20:24.230
Deswegen gucken Sie ruhig nach, aber wenn Sie nachgucken, passen Sie

20:24.230 --> 20:28.510
auf, dass das, was da definiert ist, auch kompatibel ist mit der Art

20:28.510 --> 20:30.790
und Weise, wie wir das Ganze hier definieren.

20:31.330 --> 20:37.310
Insbesondere große Freistricke, dann hinterher sowas wie Zyklen, Pfade

20:37.310 --> 20:39.550
und Zyklen in Pfaden, Zyklenfreiheit etc.

20:40.610 --> 20:42.890
Also, gerichtete Graphen.

20:43.350 --> 20:48.510
Ein gerichteter Graph kann man mathematisch schön definieren mit, wer

20:48.510 --> 20:53.070
hätte es gedacht, Mengen und Relationen und Kreuzprodukten und

20:53.070 --> 20:53.670
Abbildungen.

20:54.230 --> 20:57.130
Also, wie Sie schon gelernt haben, alles was wir in dieser Vorlesung

20:57.130 --> 21:01.530
machen, sind Mengen, Tupel, kathesisches Produkt, Operationen auf

21:01.530 --> 21:03.450
Mengen und Relationen und Abbildungen.

21:03.450 --> 21:06.410
Und nichts anderes ist ein gerichteter Graph.

21:06.470 --> 21:09.970
Ein gerichteter Graph ist ein Tupel, wir können es auch Paar nennen,

21:10.130 --> 21:15.250
G, bestehend aus einer Menge V, wie Englisch vertices und einer Menge

21:15.250 --> 21:16.490
E, wie Englisch edges.

21:17.170 --> 21:21.710
V ist die Menge der Knoten und sie hat eine Eigenschaft, sie ist

21:21.710 --> 21:23.430
endlich und sie ist nicht leer.

21:24.170 --> 21:27.810
An welche Menge erinnern Sie diese beiden Eigenschaften sofort?

21:29.290 --> 21:31.770
An die Menge eines Alphabetes.

21:32.130 --> 21:35.070
Da hat man nur noch als zusätzliche Eigenschaft, dass ein Alphabet

21:35.070 --> 21:36.470
halt sowas wie Symbole enthält.

21:36.590 --> 21:38.950
Hier enthält es halt etwas, das nennen wir Knoten.

21:38.950 --> 21:42.030
Und dann gibt es eine Menge von Kanten, das ist halt eine Teilmenge

21:42.030 --> 21:45.050
des kathesischen Produktes über die beiden Knoten.

21:45.770 --> 21:51.750
Und wenn V endlich und nicht leer ist, dann ist E auch endlich, aber E

21:51.750 --> 21:57.030
darf leer sein, weil die leere Menge immer Teilmenge jeder anderen

21:57.030 --> 22:00.090
Menge ist, insbesondere auch des kathesischen Produktes, einer nicht

22:00.090 --> 22:01.190
leeren Menge mit sich selber.

22:02.750 --> 22:08.290
Jetzt kann man hinschreiben, man hat Knoten, man kann die

22:08.290 --> 22:15.230
durchnummerieren, 1, 2, 3, 4, 5, A, B, C, D, E, Sternkreis, Spaten,

22:15.310 --> 22:15.730
was auch immer.

22:16.590 --> 22:20.570
Und dann haben wir die Menge E, der Edges, das sind also Tupel, deren

22:20.570 --> 22:23.410
Elemente wieder einzelne Knoten sind.

22:24.170 --> 22:27.430
Und könnte so einen Graph hinschreiben, wenn man da drauf guckt, auf

22:27.430 --> 22:29.650
die beiden Mengen sieht man natürlich erstmal überhaupt nichts,

22:29.750 --> 22:30.830
sondern das ist sehr unschön.

22:31.290 --> 22:33.670
Schöner ist, wenn man sich das Ganze halt grafisch hinschreibt.

22:34.230 --> 22:38.510
Also Kreise für Knoten und Pfeile für Kanten.

22:39.170 --> 22:42.430
Und das ist eben deshalb heißt der gerichtete Graph, gerichtete Graph,

22:42.550 --> 22:44.310
weil man hier Pfeile hinschreiben kann.

22:44.310 --> 22:48.010
Wenn man sich so eine Kante anschaut, als Tupel, hatten wir gesagt,

22:48.110 --> 22:50.630
bei dem Tupel kommt es insbesondere auf die Reihenfolge an.

22:50.730 --> 22:53.130
Beim Tupel gibt es ein erstes Element und ein zweites Element.

22:53.770 --> 22:55.490
Anders als das bei Mengen der Fall ist.

22:55.930 --> 22:59.330
Aber hier ist eine Kante eben ein Tupel und hat ein erstes Element und

22:59.330 --> 23:00.250
ein zweites Element.

23:00.410 --> 23:02.950
Das erste Element ist da, wo die Kante anfängt, der Knoten.

23:03.030 --> 23:05.750
Das zweite Element ist da, wo die Kante aufhört.

23:06.110 --> 23:10.290
Und der Pfeil zeigt eben immer in die Richtung, wo die Kante geht, das

23:10.290 --> 23:12.850
heißt dahin zu dem Knoten, wo die Kante dann aufhört.

23:15.170 --> 23:19.550
Wie ich jetzt das Ganze hinmale, ist mir am Ende letztendlich egal.

23:19.670 --> 23:25.070
Ob ich da explizit die Ziffern oder die Namen der Knoten reinschreibe

23:25.070 --> 23:29.370
oder ob ich die Namen der Knoten weglasse, ist letztendlich egal, weil

23:29.370 --> 23:32.910
so ein Knoten darf nur einmal vorkommen, insbesondere auch in so einer

23:32.910 --> 23:33.450
Zeichnung.

23:33.830 --> 23:37.930
Also ist das manchmal nicht so wichtig und lässt man die Sachen

23:37.930 --> 23:38.550
manchmal weg.

23:39.430 --> 23:43.270
Auch wie die geometrisch im Raum liegen, die Knoten, ist auch völlig

23:43.270 --> 23:44.250
egal.

23:44.770 --> 23:48.230
Das Einzige, was erhalten bleiben muss, ist sozusagen, welche Pfeile

23:48.230 --> 23:53.250
sind da, die immer vom selben Knoten zum anderen selben Knoten gehen

23:53.250 --> 23:56.970
und ob die jetzt spiegelverkehrt oder verzerrt oder irgendwas sind,

23:57.030 --> 24:00.350
ist völlig egal, solange die Struktur immer dieselbe ist, ist das

24:00.350 --> 24:03.510
immer wieder die Darstellung des einen und desselben Graphen.

24:05.710 --> 24:10.890
Bäume sind halt eine ganz besondere Form der gerichteten Graphen.

24:11.970 --> 24:15.870
Ein Baum ist nichts anderes als ein gerichteter Graph, bei dem die

24:15.870 --> 24:19.490
Menge der Knoten, und das ist jetzt das Ganze für einen vollständigen

24:19.490 --> 24:25.970
binären Baum, bei dem die Menge der Knoten halt basiert aus solchen

24:25.970 --> 24:27.530
Wörtern.

24:28.350 --> 24:30.830
Man kann diese Wörter dann als Bezeichnung haben.

24:30.910 --> 24:35.170
Die Wörter kommen aus diesem Alphabet 0, 1, Sternchen.

24:35.530 --> 24:40.390
Es gibt einen Knoten, der kriegt halt das Wort 1 verpasst und dann die

24:40.390 --> 24:43.850
in der Ebene drunter, die haben halt Wörter der Länge 2, alle

24:43.850 --> 24:45.350
Kombinationen aus 1 und 0.

24:45.350 --> 24:51.070
Noch eine Ebene weiter drunter sind dann Wörter der Länge 3, alle

24:51.070 --> 24:55.930
beliebigen Kombinationen aus 1 und 0 und so weiter und so fort.

24:56.510 --> 25:02.430
Und man sieht, dass man immer so eine, man kann sagen,

25:02.550 --> 25:03.690
Präfixverbindung hat.

25:03.690 --> 25:12.670
Das heißt, der Knoten 1, 0, der zeigt dann auf zwei weitere Knoten,

25:12.810 --> 25:16.270
die auch das Präfix 1, 0 haben und dann einmal die 0 und einmal die 1

25:16.270 --> 25:16.630
dahinter.

25:16.750 --> 25:20.550
Und der Knoten 1, 1, der zeigt auf zwei Knoten, die haben halt das

25:20.550 --> 25:24.050
Präfix 1, 1 und dahinter die 0 und dahinter wieder die 1.

25:24.190 --> 25:28.630
Und auf die Art und Weise wird halt dieser vollständige Baum komplett

25:28.630 --> 25:30.230
aufgebaut.

25:30.230 --> 25:33.650
Und mathematisch kann man das halt entsprechend hier mit der

25:33.650 --> 25:38.050
Konkatenation von Zeichen und Wörtern schön hinschreiben.

25:42.690 --> 25:46.430
Hier, wie gesagt, noch eine andere interessante Art von Graph.

25:46.570 --> 25:50.230
Da ist es so, dass diese Knoten, die wir haben, auch jetzt wieder

25:50.230 --> 25:55.210
Wörter sind über dem Alphabet 0, 1, der festen Länge n.

25:56.010 --> 26:02.270
Zum Beispiel halt ein Debyengraph vom Grad 3 hat dann halt Knoten, die

26:02.270 --> 26:07.670
haben die Beschriftung der festen Länge 3 und sind auch vollständig.

26:07.750 --> 26:11.870
Das heißt, alle Wörter der Länge 3 über dem Alphabet 0, 1 entsprechen

26:11.870 --> 26:15.010
dann entsprechend einem Knoten in diesem Debyengraph.

26:15.010 --> 26:20.850
Und die Kanten, die sind definiert über das, je nachdem ob man von

26:20.850 --> 26:23.310
vorne nach hinten oder nach hinten nach vorne geht, entweder über das

26:23.310 --> 26:24.770
Postfix oder das Präfix.

26:24.770 --> 26:29.710
Das heißt, wenn ich jetzt so einen Knoten habe, 0, 0, 1, was ich da

26:29.710 --> 26:36.550
mache ist, ich nehme hinten die letzten beiden Ziffern, das Präfix,

26:36.650 --> 26:41.890
das heißt das erste Zeichen wird abgespalten, bleibt 0, 1 übrig und

26:41.890 --> 26:46.830
dann konnektiere ich das zu allen Knoten, die halt 0, 1 als Präfix

26:46.830 --> 26:47.070
haben.

26:47.070 --> 26:52.330
Also 0, 1, 0 und 0, 1, 1 da oben rechts.

26:53.410 --> 26:56.470
Und so mache ich das für alle Knoten und bekomme auf diese Art und

26:56.470 --> 26:58.650
Weise so einen Debyengraph.

26:58.650 --> 27:03.690
Und an diesem Debyengraphen sehen wir dann eine besondere Art der

27:03.690 --> 27:08.130
Kante, zum Beispiel bei 0, 0 und bei 1, 1, 1.

27:08.250 --> 27:14.670
Wenn ich da das Präfix, also das Postfix nehme, 1, 1, dann verklünde

27:14.670 --> 27:17.450
ich das auch wieder mit 1, 1, 1, 1.

27:17.450 --> 27:19.330
Das heißt, ich mache den mit sich selber.

27:19.490 --> 27:23.010
Das heißt, ich habe auch so eine Kante, die aus dem Knoten 1, 1, 1

27:23.010 --> 27:24.370
raus geht und da wieder rein geht.

27:24.470 --> 27:25.390
Das ist zulässig.

27:25.790 --> 27:30.030
Das ist eine nach der Definition zulässige Kante und so eine Kante

27:30.030 --> 27:32.710
nennt man eben gerade eine Schlinge.

27:32.710 --> 27:36.410
Und wenn wir einen Graphen haben, in dem es keine solche Schlingen

27:36.410 --> 27:40.250
gibt, dann nennen wir den entsprechend schlingenfrei oder andersherum.

27:40.430 --> 27:44.890
So ein Debyengraph ist eben kein schlingenfreier Graph, weil er eben

27:44.890 --> 27:48.010
diese zwei Schlingen enthält.

27:49.770 --> 27:54.310
Interessant ist zum Beispiel, für sowas wie 1, 0, 0 gibt es

27:54.310 --> 28:00.430
entsprechend keine Schlinge, sondern es gibt nur für zwei Knoten eine

28:00.430 --> 28:02.990
Schlinge, dreimal die 0, dreimal die 1.

28:03.090 --> 28:05.730
Jetzt kann man sich überlegen, ob vielleicht im Debyengraphen

28:05.730 --> 28:08.910
beliebiger Ordnung n, das vielleicht irgendeine Eigenschaft gibt,

28:09.010 --> 28:10.970
welche Knoten halt Schlingen enthalten oder nicht.

28:11.070 --> 28:13.750
Ob das also jetzt nur hier so der Fall ist oder ob das vielleicht

28:13.750 --> 28:15.110
grundsätzlich gilt.

28:17.070 --> 28:20.450
Dann kennen wir den Begriff des Teilgraphen.

28:20.510 --> 28:25.410
Wenn wir also einen Graphen G' nehmen, der halt die Knotenmenge V' hat

28:25.410 --> 28:29.230
und die Knotenmenge E', dann ist das Ganze eben ein Teilgraph, dieses

28:29.230 --> 28:34.850
Graphen G, der aus V und E besteht, wenn halt V' eine Teilmenge der

28:34.850 --> 28:36.310
Knoten des Graphen G ist.

28:37.120 --> 28:43.510
Und wenn E' eine Teilmenge ist, der Menge, die ich erhalte, wenn ich

28:43.510 --> 28:49.810
alle Kanten nehme des ursprünglichen Graphen G' und die schneide mit

28:49.810 --> 28:54.710
dem kathesischen Produkt aus V' mit sich selber, sprich aus allen

28:54.710 --> 28:59.230
theoretisch denkbaren möglichen Kanten, die ein Graph mit der

28:59.230 --> 29:01.050
Knotenmenge V' haben könnte.

29:01.750 --> 29:07.130
Das heißt also insbesondere bei den Kanten E' des Teilgrafen vom G'

29:08.130 --> 29:12.890
sind nur solche Kanten zulässig, die auch wieder zu Knoten führen, die

29:12.890 --> 29:14.130
in dem Teilgraf liegen.

29:14.130 --> 29:17.690
Das heißt, Sie dürften keinen Teilgraf, wenn Sie den Graph wünschen

29:17.690 --> 29:22.010
schreiben, erhalten, bei dem es eine Kante gibt, die von einem Knoten

29:22.010 --> 29:24.290
weggeht und irgendwo ins Nirvana zeigt.

29:24.610 --> 29:30.530
Dann wäre das Ganze kein Teilgraf, sondern der Teilgraf darf nur

29:30.530 --> 29:34.790
Kanten enthalten, die auch innerhalb dieses Teilgrafen bleiben.

29:34.790 --> 29:39.250
Und das sind einfach so zwei mögliche Beispiele für so einen

29:39.250 --> 29:43.170
Teilgrafen, dieses De-Boyn-Graphen dritten Grades, den Sie da

29:43.170 --> 29:44.110
kennengelernt haben.

29:45.890 --> 29:52.070
Wenn wir jetzt anfangen, solche Knoten hintereinander zu schreiben, in

29:52.070 --> 29:56.170
Abhängigkeit davon, ob die jeweils mit Kanten miteinander vorhanden

29:56.170 --> 29:59.050
sind, dann kommen wir zu dem Begriff des Fads.

29:59.810 --> 30:04.850
Wir definieren uns dazu die Menge V+, oben mit so einem kleinen Plus

30:04.850 --> 30:08.770
drin, als die Menge der nicht leeren Listen von Elementen aus V.

30:09.350 --> 30:12.570
Jetzt müsste von Ihnen die berechtigte Frage kommen, was ist denn eine

30:12.570 --> 30:12.930
Liste?

30:12.930 --> 30:23.390
Eine Liste ist für uns letztendlich nichts anderes als ein N-Tupel mit

30:23.390 --> 30:27.770
beliebigem N größer gleich 1.

30:28.470 --> 30:34.530
Das heißt, so ein Fad ist dann so ein N-Tupel, im Fall ein N-Plus-1

30:34.530 --> 30:38.870
-Tupel, bestehend aus diesen Knoten V0 bis Vn, auch in dieser

30:38.870 --> 30:39.530
Reihenfolge.

30:39.630 --> 30:42.950
Dadurch, dass das ein N-Tupel ist, wird die Reihenfolge von V0, V1 und

30:42.950 --> 30:44.390
so weiter bis Vn erhalten.

30:45.190 --> 30:50.750
Und so eine Liste von V0, V1, Vn und so bis Vn ist eben dann ein Fad,

30:51.570 --> 30:58.010
wenn für jeden einzelnen Knoten innerhalb dieser Liste gilt, dass

30:58.010 --> 31:04.330
Knoten zu seinem Nachfolger, also Vi zu Vi-Plus-1 in diesem Graphen

31:04.330 --> 31:05.750
einer Kante entsprechen.

31:05.750 --> 31:10.490
Dadurch, dass also von Vi zu Vi-Plus-1 eine Kante in dem Graphen

31:10.490 --> 31:15.310
existiert, aus dem diese Knoten Vi und Vi-Plus-1 kommen.

31:16.110 --> 31:25.390
Wichtig ist, dieses 1, 2, 3, 4, 5 bis N, die die Position des Knotens

31:25.390 --> 31:30.010
in dieser Liste angibt, der hat rein gar nichts zu tun mit der

31:30.010 --> 31:32.450
Nummerierung der Knoten in der Menge der Knoten.

31:33.110 --> 31:35.590
Häufig haben Sie ja die Menge der Knoten, das sind auch so Zahlen 1,

31:35.610 --> 31:36.670
2, 3, 4 und so weiter.

31:37.210 --> 31:40.030
Stellen Sie sich besser vor, das ist a, b, c, d, e, f.

31:40.530 --> 31:43.690
Und diese Indizierung, dieses V0, das kann alles sein.

31:43.770 --> 31:46.670
Das kann a sein oder b oder c oder d oder e oder f, das ist völlig

31:46.670 --> 31:47.030
egal.

31:47.450 --> 31:52.430
Dieser Index 0 deutet nur an oder gibt nur an, in welcher Position in

31:52.430 --> 31:56.710
der Liste, die halt ein Fad sind, dieser Knoten stehen soll.

31:59.610 --> 32:03.730
Die Länge eines Fades wird definiert nicht über die Anzahl der Knoten,

32:03.830 --> 32:05.270
sondern über die Anzahl der Kanten.

32:06.190 --> 32:12.750
Das heißt, ein Fad V0, V1, der hätte eben gerade die Länge 1.

32:13.370 --> 32:17.350
Deswegen ist es auch ganz sinnvoll, da die Nummerierung bei 0 anfangen

32:17.350 --> 32:21.130
zu lassen, weil dann hat nämlich sowas wie V0, V1 eben gerade die

32:21.130 --> 32:21.650
Länge 1.

32:21.790 --> 32:27.130
Und V0, V1, V2 hat nämlich gerade eben die Länge 2, auch wenn da 3

32:27.130 --> 32:27.870
Knoten drin sind.

32:28.270 --> 32:31.350
Und was interessanterweise auch erlaubt ist, ist, dass man eben Fade

32:31.350 --> 32:32.610
hat, der Länge 0.

32:32.610 --> 32:34.790
Dann gibt es dann nur einen Knoten V0.

32:35.350 --> 32:39.970
Das ist also ein 1-Tupel, sozusagen.

32:40.990 --> 32:43.110
Einen 1-Tupel kennen wir eigentlich nicht, deswegen ist es halt eine

32:43.110 --> 32:43.350
Liste.

32:46.410 --> 32:52.130
Wenn der erste und der letzte Knoten gleich sind, wenn also V0 gleich

32:52.130 --> 32:57.050
Vn gilt, dann nennen wir diesen Fad geschlossen.

32:58.730 --> 33:04.790
Und wenn jetzt dieses n größer gleich 1 ist, dann heißt das Ganze ein

33:04.790 --> 33:05.390
Zyklus.

33:05.970 --> 33:08.070
Und jetzt muss man sich gerade überlegen, was hat das für eine

33:08.070 --> 33:08.650
Bedeutung?

33:09.930 --> 33:16.570
Naja, ein Fad der Länge 0 ist ein Fad, also V0 ist ein Fad und das n

33:16.570 --> 33:19.470
ist gleich 0, das heißt V0 ist gleich V0.

33:19.850 --> 33:22.590
Das heißt, der Fad der Länge 0 ist logischerweise also auch

33:22.590 --> 33:23.050
geschlossen.

33:25.510 --> 33:33.210
Im Prinzip ist, wenn ich die Menge der Knoten eines gerichteten

33:33.210 --> 33:37.190
Graphen hernehme, ist jeder einzelne Knoten für sich somit auch ein

33:37.190 --> 33:41.350
Fad der Länge 0 und somit auch ein geschlossener Fad, aber er ist kein

33:41.350 --> 33:41.990
Zyklus.

33:42.750 --> 33:45.710
Weil um einen Zyklus zu erhalten, brauche ich mindestens eine Kante.

33:48.010 --> 34:00.670
Dann nennt man so einen Fad wiederholungsfrei, wenn keine Kante, die

34:00.670 --> 34:03.090
ich durchlaufe, mehrfach vorkommt.

34:03.090 --> 34:11.250
Knoten darf mehrfach vorkommen, aber es darf sozusagen keine Kante

34:11.250 --> 34:14.750
mehrfach in dieser Liste des Fades vorkommen.

34:15.110 --> 34:19.330
Plus die Knoten selber müssen auch in einer paar Weise verschieden

34:19.330 --> 34:23.970
sein, das heißt es darf auch kein Knoten mehrmals vorkommen.

34:24.130 --> 34:28.370
Einzige Ausnahme V0 und Vn, die dürfen gleich sein.

34:28.370 --> 34:31.710
Und wenn ich das habe, dann habe ich eben einen wiederholungsfreien

34:31.710 --> 34:32.890
Zyklus.

34:33.470 --> 34:36.110
Und einen wiederholungsfreien Zyklus nenne ich entsprechend einen

34:36.110 --> 34:37.170
einfachen Zyklus.

34:37.170 --> 34:40.990
Und wenn ich jetzt einen Graph hernehme und jeder Teilgraph des

34:40.990 --> 34:51.330
Graphen kein Teilgraph ein Zyklus ist, dann nenne ich diesen ganzen

34:51.330 --> 34:53.150
Graphen a-zyklisch.

34:58.810 --> 35:01.410
Also mal ein paar einfache Beispiele für Faden.

35:03.350 --> 35:07.130
1-0-0 ist der Fad der Länge 0, genauso hätte ich jeden anderen

35:07.130 --> 35:10.150
bliebigen Knoten rausnehmen können und einen Fad der Länge 0 bekommen.

35:10.990 --> 35:15.390
Wenn ich von 1-0-0 nach 0-0-1 gehe, erhalte ich entsprechend einen Fad

35:15.390 --> 35:16.110
der Länge 1.

35:16.630 --> 35:20.990
Und wenn ich dann noch weiter gehe und zum Beispiel den linken Weg

35:20.990 --> 35:28.430
nehme, von 1-0-0 nach 0-0-0 und von 0-0-0 nach 0-0-1, dann habe ich

35:28.430 --> 35:30.350
einen Fad der Länge 2.

35:33.420 --> 35:36.200
Bei normalen Faden kann ich auch bestimmte Kanten mehrmals

35:36.200 --> 35:36.680
durchlaufen.

35:36.900 --> 35:40.580
Also hier zum Beispiel mache ich 1-1-0, dann gehe ich nach 1-0-1, dann

35:40.580 --> 35:47.220
gehe ich nach 0-1-1, von 0-1-1 gehe ich zu 1-1-1, der hat eine

35:47.220 --> 35:49.760
Schlinge und durch die Schlinge gehe ich jetzt zweimal durch.

35:49.760 --> 35:56.340
Das heißt am Ende des Fades steht dreimal der Knoten 1-1-1 und zwar

35:56.340 --> 36:00.420
die letzten beiden Male gehe ich halt zweimal durch diese Schlinge

36:00.420 --> 36:02.660
durch, dann habe ich einen Fad der Länge 5.

36:04.240 --> 36:06.100
Der ist halt nicht mehr wiederholungsfrei.

36:08.640 --> 36:11.240
Und wenn ich einen einfachen Zyklus habe, brauche ich also was

36:11.240 --> 36:15.160
wiederholungsfreies und ich muss da ankommen, wo ich vorher aufgehört

36:15.160 --> 36:18.280
habe, dann hat man so einen einfachen Zyklus der Länge 3, in dem ich

36:18.280 --> 36:22.940
bei 0-1-1 losgehe, da 1-1-0 ankomme, dann zu 1-0-1 gehe und dann

36:22.940 --> 36:25.820
wieder bei 0-1-1 Ende und aufhöre.

36:29.800 --> 36:33.060
Genauso kann ich mir, wie ich Metall graf, kann ich mir einen Teilfad

36:33.060 --> 36:39.100
definieren, wenn ich einen Fad P habe, der von V0 bis Vn geht, dann

36:39.100 --> 36:44.380
kann ich einen Teilfad dadurch bekommen, dass ich endlich viele Knoten

36:44.380 --> 36:49.200
streiche und zwar entweder am Anfang oder am Ende, also ein Präfix

36:49.200 --> 36:53.740
oder ein Postfix wegschneide und es muss mindestens ein Knoten übrig

36:53.740 --> 36:54.100
bleiben.

36:54.640 --> 36:57.400
Weil wenn kein Knoten mehr übrig bleibt, dann habe ich auch keinen Fad

36:57.400 --> 36:57.700
mehr.

36:59.300 --> 37:02.120
Fade negativer Länge gibt es nicht und das wäre ja die logische

37:02.120 --> 37:03.800
Konsequenz zum Beispiel daraus.

37:07.370 --> 37:11.190
Wenn ich jetzt einen gerichteten Graphen habe, dann kann ich auch

37:11.190 --> 37:13.970
etwas aussagen über seinen Zusammenhang und man nennt einen

37:13.970 --> 37:19.350
gerichteten Graphen streng zusammenhängend, wenn ich zwischen jeden

37:19.350 --> 37:24.470
beiden Knoten, die ich bekomme, einen Fad finde, der von diesem einen

37:24.470 --> 37:26.150
Knoten zu dem anderen Knoten führt.

37:26.150 --> 37:31.430
Also wenn ich für jedes Tuple xy aus diesem V-Quadrat entsprechend

37:31.430 --> 37:34.530
einen Fad finde, der von x nach y geht.

37:35.250 --> 37:38.170
Und das Schöne ist bei zum Beispiel so einem Debyein-Graphen, der ist

37:38.170 --> 37:45.990
streng zusammenhängend, hier kann ich von jedem Knoten immer zu jedem

37:45.990 --> 37:47.770
anderen Knoten einen Fad finden.

37:47.770 --> 37:52.490
Und insbesondere kann ich zum Beispiel in diesem Debyein-Graphen einen

37:52.490 --> 37:56.790
Zyklus finden, einen einfachen Zyklus, also wiederholungsfrei, auf dem

37:56.790 --> 37:57.670
alle Knoten liegen.

37:58.230 --> 38:01.570
Und wenn ich sozusagen so einen Zyklus habe, dann ist das natürlich

38:01.570 --> 38:04.610
ein schöner Nachweis darüber, dass jeder Knoten von jedem anderen

38:04.610 --> 38:05.730
Knoten aus erreichbar ist.

38:05.730 --> 38:09.450
Weil ich muss ja, wenn ich mir irgendeinen Knoten raussuche und mich

38:09.450 --> 38:11.990
jetzt frage, kann ich von dem Knoten aus einen anderen Knoten

38:11.990 --> 38:15.690
erreichen, dann gehe ich einfach den Zyklus so lange lang, bis ich bei

38:15.690 --> 38:17.170
dem anderen Knoten angekommen bin.

38:19.110 --> 38:22.010
Das heißt, wenn ich das sozusagen nachweise, dann kann ich leicht

38:22.010 --> 38:25.190
nachweisen, dass dieser Debyein-Graph streng zusammenhängend ist.

38:25.510 --> 38:27.930
Wenn ich sowas nicht habe, dann kann der Graph nach wie vor streng

38:27.930 --> 38:31.190
zusammenhängend sein, nur kann es halt eventuell schwieriger werden,

38:31.710 --> 38:34.910
da nachzuweisen, dass er streng zusammenhängt ist.

38:34.910 --> 38:38.370
Das wäre so dieser einfache Zyklus, auf dem alle Knoten liegen.

38:38.550 --> 38:42.950
Da kann ich bei jedem beliebigen Knoten, der jetzt da ist, loslaufen

38:42.950 --> 38:46.450
und einfach den roten Pfeilen folgen und komme dann über alle anderen

38:46.450 --> 38:49.010
Knoten wieder bei dem ursprünglichen Startknoten an.

38:51.890 --> 38:54.410
Dann, wie gesagt, gibt es gerichtete Bäume.

38:54.530 --> 38:59.310
Gerichtete Bäume als besondere Art des gerichteten Graphen.

38:59.530 --> 39:01.930
Hier bei den gerichteten Bäumen sprechen wir insbesondere über

39:01.930 --> 39:03.730
gerichtete, vollständige, binäre Bäume.

39:04.830 --> 39:10.230
Und man kann da auch einen besonderen Knoten identifizieren und diesen

39:10.230 --> 39:12.350
besonderen Knoten, den nennen wir die Wurzel.

39:13.150 --> 39:20.150
Es gibt also einen Knoten R, der ist die Wurzel und diese Wurzel hat

39:20.150 --> 39:25.390
die Eigenschaft, dass zu jedem Knoten X genau ein Pfad von der Wurzel

39:25.390 --> 39:25.990
aus existiert.

39:27.830 --> 39:32.890
Und das Schöne ist, dass wenn ich einen gerichteten Baum habe, diese

39:32.890 --> 39:37.330
Wurzel immer eindeutig bestimmt ist, nämlich gerade immer der Knoten

39:37.330 --> 39:39.310
mit der Beschriftung 1.

39:43.830 --> 39:46.830
Also, ein kleiner Satz, ein Lämmer, ein Hilfsatz.

39:46.950 --> 39:50.290
Die Wurzel eines gerichten Baumes ist eindeutig.

39:50.350 --> 39:51.950
Und das kann man relativ leicht beweisen.

39:52.650 --> 39:56.810
Also angenommen, Beweis durch Gegenbeweis angenommen, es gibt zwei

39:56.810 --> 40:00.670
verschiedene Wurzeln eines gerichten Baumes.

40:00.670 --> 40:08.770
Wenn es so wäre, dann gebe es ein Pfad von R nach R', weil R ist eine

40:08.770 --> 40:09.110
Wurzel.

40:09.550 --> 40:12.710
Und gemäß Definition einer Wurzel muss es immer einen, genau einen

40:12.710 --> 40:16.090
eindeutigen Pfad von der Wurzel zu jedem anderen Knoten geben, also

40:16.090 --> 40:19.990
muss es einen Pfad geben von R nach R'.

40:19.990 --> 40:24.710
Und genauso, weil R' Wurzel ist, müsste es einen Pfad von R' nach R

40:24.710 --> 40:27.450
geben, weil R' ja auch eine Wurzel ist.

40:28.090 --> 40:31.590
Und jetzt könnte ich diese beiden Pfade einfach hintereinander hängen.

40:32.990 --> 40:40.490
Ich könnte von R nach R' gehen und ich könnte von R' nach R gehen.

40:41.390 --> 40:44.430
Und dieser Pfad hätte eine Länge, die ist größer als 0.

40:44.650 --> 40:44.870
Warum?

40:45.150 --> 40:48.770
Weil wir sagen, R' und R sind verschieden, das sind zwei

40:48.770 --> 40:49.410
unterschiedliche.

40:49.410 --> 40:52.890
Das heißt, ich hätte einen Pfad, der geht von R nach R', und R' ist

40:52.890 --> 40:55.050
was anderes als R, und dann wieder von R' nach R.

40:55.430 --> 41:00.410
Das ist also ein Pfad der Länge 2, mindestens, eher sogar noch mehr.

41:02.090 --> 41:05.510
Und dieser Pfad bringt mich von R nach R.

41:07.070 --> 41:10.530
Gleichzeitig gibt es aber auch den Pfad der Länge 0, der nur R ist,

41:10.790 --> 41:12.230
der mich von R nach R bringt.

41:12.890 --> 41:16.130
Das darf aber nicht sein, weil wir hatten gesagt, R soll eine Wurzel

41:16.130 --> 41:16.410
sein.

41:16.530 --> 41:20.010
Und wenn R eine Wurzel ist, dann gibt es genau einen einzigen Pfad,

41:20.110 --> 41:23.670
der von R nach R geht, nämlich nur der Pfad R selber und nichts alles

41:23.670 --> 41:23.990
andere.

41:23.990 --> 41:27.230
Weil wenn es einen anderen Pfad gibt, dann ist er per Definition eher

41:27.230 --> 41:28.110
keine Wurzel mehr.

41:29.710 --> 41:32.370
Also Pfad von R nach R wäre nicht eindeutig.

41:32.450 --> 41:35.930
Ich könnte mindestens zwei Pfade konstruieren und dann wäre

41:35.930 --> 41:39.890
entsprechend R auch keine Wurzel mehr, damit Widerspruch und damit

41:39.890 --> 41:43.830
bewiesen, dass halt die Wurzel eines gerichteten Baumes eindeutig

41:43.830 --> 41:44.450
bestimmt ist.

41:45.930 --> 41:48.930
Und wie gesagt, nach der Definition, wie wir hier diese vollständigen

41:48.930 --> 41:53.290
binären Bäume definiert haben, ist es gerade eben immer der Eins.

41:54.710 --> 41:56.450
Beweis, leichte Aufgabe für zu Hause.

41:58.730 --> 42:04.570
Dann definieren wir so etwas wie die Gerade von Knoten.

42:04.930 --> 42:08.930
Wir haben so etwas wie den Eingangsgrad eines Knoten Y, den macht man

42:08.930 --> 42:10.750
mit DO-Y.

42:11.570 --> 42:19.190
Das ist eben die Anzahl aller Knoten, von denen es aus eine Kante

42:19.190 --> 42:23.050
gibt, die in X anfangen und in Y enden.

42:24.050 --> 42:27.490
Oder anders ausgedrückt, wenn ich grafisch denke, gucke ich mir an,

42:27.550 --> 42:30.370
wie viele Pfeile gehen denn in diesen Knoten rein.

42:30.450 --> 42:31.490
Das ist sein Eingangsgrad.

42:31.930 --> 42:37.390
Und genauso ist der Ausgangsgrad, die Anzahl der Knoten, die es gibt,

42:38.430 --> 42:45.190
die durch eine Kante direkt von dem Knoten, von dem ich den

42:45.190 --> 42:48.290
Ausgangsgrad mir anschaue, erreicht werden.

42:48.290 --> 42:53.010
Oder grafisch gesprochen, wie viele Pfeile gehen aus diesem Knoten

42:53.010 --> 42:53.450
heraus.

42:54.010 --> 42:54.710
Das ist der Ausgangsgrad.

42:54.810 --> 42:57.550
Und dann der Grad eines Knotens ist dann eben gerade die Summe aus

42:57.550 --> 42:59.070
Eingangsgrad und Ausgangsgrad.

42:59.210 --> 43:04.050
Wie viele Pfeile gehen rein und wie viele Pfeile gehen aus dem Knoten

43:04.050 --> 43:04.390
heraus.

43:07.450 --> 43:11.210
Dann unterscheidet man bei Bäumen noch zwischen Blättern und

43:11.210 --> 43:13.110
sogenannten inneren Knoten.

43:13.190 --> 43:16.210
Blätter erkennt man immer leicht daran, dass sie einen Ausgangsgrad

43:16.210 --> 43:17.110
von 0 haben.

43:17.890 --> 43:21.450
Und innere Knoten sind dann alle anderen Knoten, also Knoten, die

43:21.450 --> 43:23.710
einen Ausgangsgrad größer 0 haben.

43:23.710 --> 43:26.950
Und wenn Sie sich das grafisch vorstellen, solange wir von

43:26.950 --> 43:30.990
vollständigen binären Bäumen reden, dann sind die Blätter immer

43:30.990 --> 43:36.270
diejenigen, die ganz unten auf der letzten Ebene liegen.

43:38.770 --> 43:45.190
Dann können wir auch uns anschauen, den Begriff der Isomorphie für

43:45.190 --> 43:46.130
Grafen.

43:47.090 --> 43:51.370
Der ist anschaulich relativ leicht dadurch zu erklären, dass man

43:51.370 --> 43:56.990
einfach guckt, wie kann ich den Grafen und insbesondere dann also nur

43:56.990 --> 44:01.290
die Knoten umbenennen, sodass die Struktur, also die Art und Weise,

44:01.390 --> 44:04.650
wie die Knoten miteinander letztendlich ins Verhältnis stehen, gegeben

44:04.650 --> 44:08.710
durch die Kanten, dass diese Struktur erhalten bleibt, dass die gleich

44:08.710 --> 44:09.930
bleibt, dass die sich nicht ändert.

44:12.190 --> 44:17.350
Man sagt dann halt, dass ein Graf G1 isomorph ist zu einem Grafen G2,

44:17.950 --> 44:22.150
wenn ich so eine Bijektion finde zwischen den Knoten des ersten Grafen

44:22.150 --> 44:24.250
und des Knoten des zweiten Grafen.

44:24.250 --> 44:25.330
Was heißt das Bijektion?

44:25.410 --> 44:30.490
Das ist also eine Abbildung, die injektiv und subjektiv sein soll.

44:31.150 --> 44:36.530
Und diese Bijektion, die muss die Eigenschaft haben, dass für alle

44:36.530 --> 44:47.830
Knoten aus dem ersten Grafen und für alle Knoten aus dem ersten Grafen

44:47.830 --> 44:51.090
und für alle Knoten aus dem zweiten Grafen, wenn ich daraus diese

44:51.090 --> 44:57.250
Tupel -Bilde XY und das sind Kanten, wenn es also für alle Kanten dann

44:57.250 --> 45:00.470
entsprechend so ist, dass wenn ich jetzt den Anfangs- und den

45:00.470 --> 45:05.990
Endknoten abbilde, dass das, was dabei herauskommt, das Tupel dann

45:05.990 --> 45:09.050
auch wieder eine Kante ist in dem zweiten Grafen.

45:10.030 --> 45:12.630
Und wenn ich so eine Funktion habe, die nennt man dann entsprechend

45:12.630 --> 45:14.490
einen Graf-Isomorphismus.

45:14.910 --> 45:17.530
Das kann man sich relativ leicht vorstellen, das ist wie schon gesagt,

45:17.610 --> 45:20.310
wenn ich hier was habe, das ist irgendwie durchnummeriert und dann

45:20.310 --> 45:22.170
bilde ich das halt auf ABCD.

45:23.970 --> 45:28.210
Wie die Kanten die Knoten miteinander verbinden, bleibt gleich.

45:28.670 --> 45:33.110
Lediglich die Namen der Knoten ändern sich so, dass die auch Knoten,

45:33.170 --> 45:36.190
die vorher unterschiedlich waren, auch nach der Umbenennung nach wie

45:36.190 --> 45:39.470
vor unterschiedlich sind und dass auch immer noch dann die Knoten

45:39.470 --> 45:41.970
entsprechend miteinander verbunden sind.

45:50.420 --> 45:54.320
Relativ leicht sieht man, dass wenn G1 Isomorph zu G2 ist, dann ist

45:54.320 --> 45:55.980
auch G2 Isomorph zu G1.

45:56.440 --> 46:00.960
Das Schöne ist ja, diese Abbildung F ist eine Bijektion mit dieser

46:00.960 --> 46:03.760
besonderen Eigenschaft und dadurch, dass es eine Bijektion ist, ist

46:03.760 --> 46:05.220
sie insbesondere auch invertierbar.

46:05.220 --> 46:11.360
Und das Inverse dieser Bijektion F liefert halt entsprechend dann den

46:11.360 --> 46:15.120
Isomorphismus von G2 zu G1.

46:18.980 --> 46:22.180
Und dementsprechend ist auch jeder Graf-Isomorph zu sich selber, indem

46:22.180 --> 46:24.000
ich einfach die Identitätsabbildung nehme.

46:24.600 --> 46:27.620
Jeder Knoten wird auf sich selber abgebildet, ist dann ein Graf

46:27.620 --> 46:31.300
-Isomorphismus für den Grafen zu sich selber.

46:33.580 --> 46:37.400
Man kann auch da mit der Hintereinanderausführung der Abbildungen

46:37.400 --> 46:38.140
schön arbeiten.

46:38.260 --> 46:43.160
Wenn ich also einen Grafen G1 habe, der Isomorph zu G2 ist und wenn G2

46:43.160 --> 46:48.240
auch Isomorph zu G3 ist, gibt es also eine Abbildung F für G1 zu G2,

46:48.380 --> 46:54.440
eine Abbildung G für G2 zu G3, dann ist auch G1 Isomorph zu G3, wenn

46:54.440 --> 46:57.700
es die Hintereinanderausführung tut, tut das Gewünschte.

46:57.700 --> 47:00.940
Das ist sozusagen die Transitivität.

47:03.020 --> 47:06.840
Und das ist dann entsprechend die Verbindung zum Begriff der

47:06.840 --> 47:07.680
Relationen.

47:08.480 --> 47:14.320
Man hat so einen Grafen und so ein Graf ist gleichzeitig auch eine

47:14.320 --> 47:19.080
Relation über die Art und Weise, wie er die Knoten miteinander

47:19.080 --> 47:19.580
verbindet.

47:19.580 --> 47:23.560
Wenn man nämlich jetzt die Kanten hernimmt, dann ist das ja eine

47:23.560 --> 47:27.300
Teilmenge des kathesischen Produktes, der Menge der Knoten mit sich

47:27.300 --> 47:27.640
selber.

47:27.920 --> 47:31.960
Das heißt also, E selber ist auch eine Relation, eine binäre Relation.

47:32.900 --> 47:38.100
Und was ist jetzt, wenn ich die E als Relation nehme, E² hernehme,

47:38.160 --> 47:42.580
also als Relation dann E hintereinander mit sich selber ausführe?

47:43.220 --> 47:51.620
Na gut, E, hintereinander ausgeführt E, das sind alle Tuplen XZ aus

47:51.620 --> 47:54.880
dem kathesischen Produkt der Knoten mit sich selber, so dass es

47:54.880 --> 47:58.300
irgendwie einen Knoten Y gibt, so dass ich erst eine Kante habe, die

47:58.300 --> 48:03.060
von X nach Y geht und dann habe ich eine Kante, die von Y nach Z geht.

48:03.680 --> 48:09.020
Das heißt, ich habe also einen Pfad der Länge 2, der X und Z

48:09.020 --> 48:10.880
miteinander verbindet.

48:17.940 --> 48:22.000
Das heißt, also so ein Knotenpaar ist genau dann in der Relation, wenn

48:22.000 --> 48:29.820
es also einen Pfad der Länge 2 gibt, der von X nach Z führt, über

48:29.820 --> 48:30.860
diesen Knoten Y.

48:39.540 --> 48:44.640
Diese Relation nennt man auch, wenn man sie ins Extreme treibt, die

48:44.640 --> 48:46.000
Erreichbarkeitsrelation.

48:46.180 --> 48:49.740
Wenn ich mich jetzt hier nur mit Pfaden der Länge 2 beschäftige, dann

48:49.740 --> 48:53.160
nennt man das die Zweierreichbarkeitsrelation.

48:54.460 --> 48:58.820
Also XY ist aus dieser Zweierreichbarkeitsrelation, wenn es halt einen

48:58.820 --> 49:02.080
Pfad der Länge 2 von X nach Y gibt, dann kann man sich auch

49:02.080 --> 49:05.680
entsprechend definieren die Einserreichbarkeitsrelation, die Menge der

49:05.680 --> 49:06.060
Kanten.

49:06.060 --> 49:13.100
Da sind alle Tuple XY drin, es existiert ein Pfad der Länge 1 von X

49:13.100 --> 49:18.380
nach Y und noch einfacher dann die Nullerreichbarkeitsrelation, da

49:18.380 --> 49:23.520
sind also alle Tuple XY drin, sodass es einen Pfad der Länge 0 von X

49:23.520 --> 49:24.420
nach Y gibt.

49:24.420 --> 49:30.060
In armen Worten nichts anderes als die Menge der Knoten.

49:31.260 --> 49:33.060
Tuteln, Knoten mit sich selber.

49:33.920 --> 49:38.900
Das ist jetzt also von 2 runtergerechnet und genauso kann man das

49:38.900 --> 49:44.760
Ganze auch hochrechnen für immer größere Ends, Zweierreichbarkeit,

49:44.860 --> 49:47.700
Dreierreichbarkeit, Viererreichbarkeit und so weiter und so fort, bis

49:47.700 --> 49:49.720
man zur allgemeinen Erreichbarkeit kommt.

49:53.960 --> 49:58.180
Allgemein für beliebiges I aus N0 kann man erstmal sagen, ein

49:58.180 --> 50:02.220
Knotenpaar XY ist genau in dieser Relation E hoch I, der I

50:02.220 --> 50:06.480
-Erreichbarkeitsrelation, wenn es halt einen Pfad der Länge I von X

50:06.480 --> 50:08.840
nach Y gibt in diesem Graphen G.

50:12.400 --> 50:16.740
Jetzt kann man sich an der Stelle schon mal im Hinterkopf folgende

50:16.740 --> 50:17.620
Überlegung machen.

50:18.500 --> 50:21.800
Man kann jetzt dieses I immer größer und größer werden machen lassen,

50:21.900 --> 50:25.920
man kann einen Pfade beliebiger Länge ja hernehmen und jetzt kann man

50:25.920 --> 50:29.800
ein bisschen im Hinterkopf behalten, wie war das nochmal, die Menge

50:29.800 --> 50:34.080
der Knoten war endlich, dementsprechend war die Menge der Kanten

50:34.080 --> 50:34.480
endlich.

50:35.200 --> 50:40.220
Das heißt, wenn ich mir jetzt Pfade immer größerer Länge anschaue, ich

50:40.220 --> 50:44.220
aber nur eine endliche Menge Knoten habe, dann werden irgendwann

50:44.220 --> 50:46.300
Knoten häufiger vorkommen.

50:46.860 --> 50:50.040
Und irgendwann muss ich dann auch, wenn die Pfade immer länger werden,

50:50.160 --> 50:54.080
gegebenenfalls auch in einen Zyklus reinlaufen, weil ich habe dann

50:54.080 --> 50:59.000
irgendwie sieben Knoten, die es nur gibt und man fährt ja jetzt 15

50:59.000 --> 51:03.580
Kanten lang und auf dem liegen zum Aufpassen 16 Knoten und es gibt nur

51:03.580 --> 51:05.260
sieben Knoten, da muss irgendwas doppelt vorkommen.

51:05.260 --> 51:07.900
Das heißt, ich habe irgendwo da innen drin so Zyklen.

51:08.040 --> 51:10.820
Ich habe keinen wiederholungsfreien Pfad mehr.

51:11.400 --> 51:16.140
Und wenn ich mich jetzt um Erreichbarkeit bemühe, dann ist ja diese

51:16.140 --> 51:20.640
Wiederholungsfreiheit irgendwann wichtig, wenn ich mich sozusagen

51:20.640 --> 51:24.660
darum frage, was ist so der kürzeste Pfad, den ich finden kann, um von

51:24.660 --> 51:27.120
einem Knoten zum anderen zu kommen und dann kann ich mir leicht

51:27.120 --> 51:31.300
überlegen, dass das irgendwann, wenn ich dieses I hochgehen lasse,

51:31.760 --> 51:34.960
dass das ab einer bestimmten Zahl von I keinen Sinn mehr macht, weil

51:34.960 --> 51:38.820
ich werde nichts Neues mehr dazubekommen, weil ich mich nur noch in so

51:38.820 --> 51:39.600
Zyklen bewege.

51:39.680 --> 51:42.180
Ich werde also keinen neuen Knoten mehr erreichen, sondern ich werde

51:42.180 --> 51:45.140
irgendwo an irgendeiner Stelle irgendwo nur im Kreis laufen.

51:45.760 --> 51:48.040
Das kann man sich schon mal so ein bisschen im Hinterkopf behalten.

51:52.400 --> 51:55.780
Noch ein weiteres Korollar, das dabei abfällt, ist, wenn ich jetzt so

51:55.780 --> 52:00.120
einen Graph habe und jetzt habe ich einen Knotenpaar XY, dann ist das

52:00.120 --> 52:03.680
genau dann in dieser Relation E-Stern, das heißt also, wenn ich das I

52:03.680 --> 52:06.660
beliebig groß gemacht habe, wir nennen das die

52:06.660 --> 52:12.300
Erreichbarkeitsrelation, das heißt XY ist von X aus genau dann

52:12.300 --> 52:16.660
erreichbar, ist also genau dann in dieser Relation E-Stern, wenn ein

52:16.660 --> 52:20.020
Pfad eventuell in der Länge 0 von X nach Y in G existiert.

52:20.760 --> 52:24.780
Das heißt, das heißt nichts anderes als dieses E-Stern, das I also

52:24.780 --> 52:31.420
gegen unendlich gehen lassen, dass das eben gerade diese

52:31.420 --> 52:35.960
Erreichbarkeitsrelation ist, dass es eben genau angibt, ob ein Knoten

52:35.960 --> 52:39.660
Y von einem Knoten X aus erreichbar ist.

52:41.840 --> 52:46.000
Und dann kann man, weil ja der strenge Zusammenhang eben gerade was

52:46.000 --> 52:50.120
mit der Erreichbarkeit zu tun hat, daraus dann auch ableiten, dass ein

52:50.120 --> 52:54.880
Graph, gerichteter Graph, genau dann streng zusammenhängend ist, wenn

52:54.880 --> 53:00.700
diese Erreichbarkeitsrelation E-Sternchen gerade das kathesische

53:00.700 --> 53:02.500
Produkt der Knoten mit sich selber ist.

53:02.500 --> 53:06.800
Weil das war gerade die Definition eines streng zusammenhängenden

53:06.800 --> 53:11.220
Graphens, dass jeder Knoten von jedem anderen Knoten aus erreichbar

53:11.220 --> 53:11.760
sein muss.

53:16.140 --> 53:19.520
Also soviel zu gerichteten Graphen.

53:20.960 --> 53:23.800
Allgemein werden irgendwelche Beziehungen ausgedrückt.

53:23.960 --> 53:27.300
Ich habe irgendwas, das kann ich als Knoten repräsentieren.

53:27.380 --> 53:29.520
Ich habe irgendwas, das kann ich als Kanten repräsentieren.

53:29.520 --> 53:32.100
Dann kann ich anfangen, Pfade zu definieren.

53:32.220 --> 53:34.920
Ich habe so spezielle Kanten, die nämlich schlinken und wenn ich dann

53:34.920 --> 53:38.460
halt so Pfade habe, habe ich spezielle Pfade, die heißen

53:38.460 --> 53:41.100
wiederholungsfrei und dann gibt es Pfade, die nämlich zyklen.

53:41.540 --> 53:43.400
Ich kann sowas wie Teilgraphen bilden.

53:43.940 --> 53:46.540
Sowas wie ein De Bruijn Graph scheint irgendwie ein ganz interessanter

53:46.540 --> 53:48.620
Graph zu sein, mit dem man schöne Eigenschaften sieht.

53:49.020 --> 53:52.120
Ganz wichtig, was Sie schon häufig gesehen haben, sind Bäume und Bäume

53:52.120 --> 53:57.440
sind wiederum nichts anderes als ein Spezialfall von gerichteten

53:57.440 --> 53:57.980
Graphen.

53:57.980 --> 54:03.800
Und ein gerichteter Graph definiert mir immer eine Relation, diese

54:03.800 --> 54:06.740
sogenannte Erreichbarkeitsrelation E-Stern.

54:08.240 --> 54:12.980
Analog zu gerichteten Graphen gibt es entsprechend auch ungerichtete

54:12.980 --> 54:13.620
Graphen.

54:13.620 --> 54:19.860
Man versucht jetzt, diese Begriffe, die man bei gerichteten Graphen

54:19.860 --> 54:23.680
hat, auf ungerichtete Graphen zu übertragen und kommt da an ein paar

54:23.680 --> 54:26.340
Stellen natürlich an Grenzen.

54:27.740 --> 54:30.440
Also was ist erst mal ein ungerichteter Graph?

54:30.840 --> 54:33.580
Wenn man graphisch spricht, würde man sagen, bei einem ungerichteten

54:33.580 --> 54:38.960
Graphen werden die Pfeilspitzen an den Kanten weggeworfen.

54:39.200 --> 54:42.360
Eine Kante hat keine Pfeilspitzen mehr, eine Kante hat keinen Anfang

54:42.360 --> 54:43.300
und kein Ende mehr.

54:43.300 --> 54:46.960
Die Menge der Knoten bleibt gleich, wie vorher auch, aber bei der

54:46.960 --> 54:48.500
Menge der Kanten ändert sich was.

54:49.160 --> 54:54.280
Statt der Tupel, die man jetzt hat, also bei den Kanten von dem

54:54.280 --> 54:56.960
gerichteten Graph hat man eine Menge von Tupeln, Anfangsknoten,

54:57.000 --> 55:00.580
Endknoten, aus diesem Tupel werden jetzt Mengen.

55:00.580 --> 55:02.980
Mengen von zwei Knoten X und Y.

55:03.320 --> 55:06.320
Und wenn Sie sich erinnern, wir hatten ja gesagt, Mengen haben keine

55:06.320 --> 55:07.440
Reihenfolge.

55:07.500 --> 55:09.880
Die Elemente in einer Menge kennen keine Reihenfolge.

55:10.000 --> 55:10.960
Anders als bei Tupeln.

55:11.460 --> 55:13.860
Das heißt, dadurch, dass ich also aus dem Tupel eine Menge mache,

55:13.960 --> 55:18.260
werfe ich eben gerade die Pfeilspitze weg, werfe weg, was ist der

55:18.260 --> 55:19.860
Anfangs - und was ist der Endknoten.

55:22.490 --> 55:27.370
Wenn zwei Knoten irgendwie mit einer Kante ohne Pfeil verbunden sind,

55:27.550 --> 55:29.970
dann gibt es ja keinen Anfangs- und keinen Endknoten mehr.

55:30.830 --> 55:33.170
Die sind beide gleichberechtigt, man nennt sie dann nur noch die

55:33.170 --> 55:34.770
Adjacentenknoten.

55:35.430 --> 55:37.370
Und es gibt auch nach wie vor Schlingen.

55:38.610 --> 55:42.330
Das war vorher Kante mit identischem Start- und Zielknoten.

55:44.730 --> 55:48.150
Jetzt gibt es keinen Start- und Zielknoten mehr, sondern jetzt ist

55:48.150 --> 55:52.410
eine Schlinge dann, wenn ein Knoten Adjacent zu sich selber ist.

55:52.970 --> 55:58.010
Das heißt, wenn es also eine Kante gibt, sei X der Knoten, die Kante

55:58.010 --> 56:02.390
besteht dann halt aus der Menge X, X und da halt mehrfach vorkommen in

56:02.390 --> 56:06.310
der Menge egal ist, ist das das gleiche wie die Menge nur aus X.

56:07.350 --> 56:10.350
Und wenn ich einen Graph habe, der keine Schlingen hat, dann nenne ich

56:10.350 --> 56:11.990
den wie immer Schlingenfrei.

56:13.590 --> 56:17.070
Also einfaches Beispiel, das gleiche Beispiel wie vorhin bei den

56:17.070 --> 56:21.210
gerichteten Graphen, nur dass jetzt halt die Pfeilspitzen weggefallen

56:21.210 --> 56:25.150
sind und entsprechend aus der Menge der Kanten eine Menge von Mengen

56:25.150 --> 56:27.110
geworden ist und nicht mehr eine Menge von Tupeln.

56:28.270 --> 56:30.990
Ich habe nach wie vor sowas wie eine Schlinge, ist nach wie vor

56:30.990 --> 56:31.330
möglich.

56:32.690 --> 56:39.190
Ich kann auch nach wie vor Teilgraphen bilden, also U' ist der

56:39.190 --> 56:43.450
Teilgraph eines ungerichteten Graphen, wenn wieder die Menge der

56:43.450 --> 56:47.090
Knoten, eine Teilmenge der Knoten ist des ursprünglichen Graphen und

56:47.090 --> 56:53.290
die Menge der Kanten wieder aus diesem Schnitt kommt, aus den

56:53.290 --> 56:56.850
ursprünglichen Kanten und allen möglichen Kanten, die ich in dem

56:56.850 --> 56:58.590
Teilgraphen bilden kann.

56:58.590 --> 57:03.350
Das heißt auch nach wie vor, die Endpunkte der Kante in dem

57:03.350 --> 57:06.250
Teilgraphen müssen auch wieder in dem Teilgraphen drin bleiben.

57:06.410 --> 57:09.590
Also ich darf nicht irgendwie Striche haben, die da zwar irgendwo an

57:09.590 --> 57:13.350
einem Knoten angedockt sind, aber dann auf der anderen Seite nicht

57:13.350 --> 57:16.030
mehr an einem Knoten angedockt sind.

57:16.030 --> 57:19.430
Und Teilgraphen sind dementsprechend halt auch Graphen, das ist gerade

57:19.430 --> 57:21.070
wieder die Definition eines Graphen.

57:22.770 --> 57:28.050
Jetzt gibt es keine Pfade mehr, sondern statt der Pfade haben wir

57:28.050 --> 57:29.810
jetzt etwas, das nennen wir einen Weg.

57:30.550 --> 57:36.370
Und ein Weg ist wieder eine Liste von so Knoten, von 0 bis vn.

57:37.950 --> 57:41.210
So, dass wenn ich jetzt in der Liste, in der es die Reihenfolge gibt,

57:41.350 --> 57:43.730
also in einem Weg, gibt es eine Reihenfolge, in der die Knoten

57:43.730 --> 57:50.010
abgelaufen werden, wenn diese Kante vi zu vi plus 1 eine Kante ist in

57:50.010 --> 57:54.130
dem Graphen, wenn also vi zu vi plus 1 in dem Graphen mit einer Kante

57:54.130 --> 57:57.950
verbunden sind, wenn also vi adjacent ist zu vi plus 1.

57:58.610 --> 58:01.730
Und auch die Länge eines Weges wird wieder definiert über die Anzahl

58:01.730 --> 58:04.010
der Kanten, die ich habe.

58:05.030 --> 58:08.710
Auch mit einem Weg kann man eine Erreichbarkeit definieren, also ein

58:08.710 --> 58:14.530
Knoten Y ist von einem Knoten X aus erreichbar, wenn es einen Weg

58:14.530 --> 58:19.410
gibt, der mit X anfängt und mit Y aufhört.

58:20.510 --> 58:25.390
Ein Weg, genauso wie ein Pfad, ist wiederholungsfrei, wenn halt diese

58:25.390 --> 58:30.410
Knoten paarweise verschieden sind.

58:31.250 --> 58:34.650
Nur der Anfangs- und der Endknoten, die dürfen gleich sein.

58:35.050 --> 58:41.790
Und ansonsten müssen die Knoten ansonsten immer paarweise

58:41.790 --> 58:42.670
unterschiedlich sein.

58:45.480 --> 58:48.200
Wenn man einen geschlossenen Weg hat, dann nennt man das nicht mal

58:48.200 --> 58:50.740
einen Zyklus, sondern nennt man das Ganze einen Kreis.

58:51.540 --> 58:55.800
Wenn also der Anfangs- und der Endknoten in dieser Liste, der da ein

58:55.800 --> 58:58.720
Weg ist, gleich sind, dann nennen wir das einen Kreis.

58:58.840 --> 59:01.720
Wenn der Kreis wiederholungsfrei ist, also wiederholungsfreier Pfad

59:01.720 --> 59:05.580
ist, dann ist es ein einfacher Kreis, aber wir fordern, dass er

59:05.580 --> 59:08.860
mindestens drei verschiedene Knoten enthalten ist.

59:15.230 --> 59:19.810
Jetzt kann man sich noch überlegen, bei dem gerichteten Graphen hatten

59:19.810 --> 59:22.110
wir ja so eine Relation definiert durch die Kanten.

59:24.310 --> 59:26.810
Bei ungerichteten Graphen ist das jetzt nicht mehr so einfach.

59:26.990 --> 59:30.750
Bei gerichteten Graphen war das einfach, weil die Menge der Kanten war

59:30.750 --> 59:34.750
schon per Definition eine binäre Relation, weil es war ein

59:34.750 --> 59:35.670
kathesisches Produkt.

59:36.390 --> 59:38.450
Teilmenge des kathesischen Produktes der Knoten.

59:38.790 --> 59:40.610
Das ist jetzt beim ungerichteten Graphen nicht mehr der Fall.

59:41.030 --> 59:44.110
Da habe ich jetzt nicht mehr Teilmenge eines kathesischen Produktes,

59:44.190 --> 59:47.170
weil ich habe keine Tupel mehr, sondern ich habe nur noch Abhängen mit

59:47.170 --> 59:51.610
einem oder zwei Knoten drin.

59:52.930 --> 59:55.990
Wenn ich mir also jetzt die Relation anschauen will, die durch so

59:55.990 --> 59:59.530
einen ungerichteten Graphen definiert wird, dann muss ich irgendwie

59:59.530 --> 01:00:01.890
wieder den Schritt machen hin zu gerichteten Graphen.

01:00:02.530 --> 01:00:12.090
Und wir nennen halt E, wir erhalten jetzt so eine Kantenrelation, so

01:00:12.090 --> 01:00:21.450
eine binäre Relation, indem wir einen gerichteten Graph definieren,

01:00:21.590 --> 01:00:23.530
der zu diesem ungerichteten Graph gehört.

01:00:23.530 --> 01:00:28.010
Also angenommen, wir haben so einen ungerichteten Graphen VE, dann

01:00:28.010 --> 01:00:32.550
definieren wir uns dazu den gerichteten Graphen GU, der besteht wieder

01:00:32.550 --> 01:00:36.270
aus dem selben Knoten V, und aus neun gerichteten Kanten.

01:00:36.890 --> 01:00:41.590
Und diese gerichteten Kanten erhalte ich halt, wenn ich für jede Kante

01:00:41.590 --> 01:00:46.030
XY aus E mir das Tupel XY hernehme.

01:00:46.030 --> 01:00:51.030
Und da eben diese Reihenfolge XY in der Kante egal war, gibt es

01:00:51.030 --> 01:00:54.130
sozusagen dann gegebenenfalls zwei Kanten.

01:00:54.850 --> 01:00:58.850
Einmal von dem Knoten in die eine Richtung und in die andere Richtung.

01:00:59.290 --> 01:01:03.230
Wenn also vorher zwei Knoten XY miteinander adjazent waren, dann

01:01:03.230 --> 01:01:07.130
erhalte ich im zugehörigen gerichteten Graphen zwei Kanten, nämlich

01:01:07.130 --> 01:01:12.670
die Kante von X nach Y und wieder die Kante von Y nach X zurück.

01:01:12.670 --> 01:01:17.350
Das nenne ich jetzt den zu U gehörenden gerichteten Graphen und über

01:01:17.350 --> 01:01:22.950
diesen zugehörigen gerichteten Graphen komme ich dann wieder zu einer

01:01:22.950 --> 01:01:23.590
Relation.

01:01:25.930 --> 01:01:30.890
Angenommen, ich habe jetzt so einen ungerichteten Graphen U, dann

01:01:30.890 --> 01:01:38.090
nenne ich den zusammenhängend, wenn der zugehörige gerichtete Graph,

01:01:38.150 --> 01:01:41.590
den ich daraus konstruieren kann, streng zusammenhängend ist.

01:01:45.870 --> 01:01:46.830
Also angenommen,

01:01:50.870 --> 01:01:53.770
ich kann jetzt also auch, also ich kann von einem ungerichteten Graph

01:01:53.770 --> 01:01:57.110
zu einem zugehörigen gerichteten Graphen kommen, genauso kann ich

01:01:57.110 --> 01:02:01.170
umgekehrt von einem ungerichteten Graphen wieder zurückkommen, von

01:02:01.170 --> 01:02:04.370
einem gerichteten Graphen wieder gehen zu einem ungerichteten Graphen

01:02:04.370 --> 01:02:09.150
und das mache ich einfach, indem ich diese Richtungsinformationen, die

01:02:09.150 --> 01:02:13.090
in den Kanten des gerichteten Graphens drin stecken, wegwerfe, indem

01:02:13.090 --> 01:02:18.430
ich also aus diesem tuplen XY Mengen XY mache und je nachdem verliere

01:02:18.430 --> 01:02:22.650
ich halt dadurch bestimmte Kanten, dadurch, dass jetzt die Reihenfolge

01:02:22.650 --> 01:02:27.130
nicht mehr egal ist und die Menge XY das gleiche ist wie die Menge YX.

01:02:28.770 --> 01:02:33.530
Also man entfernt die Pfeilspitzen und gegebenenfalls muss man halt

01:02:33.530 --> 01:02:37.130
dann redundante Kanten entsprechend auch entfernen.

01:02:37.130 --> 01:02:44.590
Es gibt auch so etwas wie einen ungerichteten Baum, das ist der

01:02:44.590 --> 01:02:49.470
ungerichtete Graph U, der zu dem gerichteten Baum G gehört.

01:02:49.630 --> 01:02:52.470
Also wenn ich einen gerichteten Baum G habe, kann ich zu einem

01:02:52.470 --> 01:02:56.350
ungerichteten Baum U kommen, indem ich einfach den zugehörigen

01:02:56.350 --> 01:03:00.450
ungerichteten Graphen zu diesem gerichteten Baum G finde.

01:03:04.730 --> 01:03:10.770
Das wären zum Beispiel so Beispiele, die ich bekommen kann.

01:03:11.450 --> 01:03:15.510
Das sind alles ungerichtete Graphen, die ich erhalten kann, indem ich

01:03:15.510 --> 01:03:18.890
einen gerichteten Graph nehme, der ein Baum ist und daraus dann den

01:03:18.890 --> 01:03:20.730
zugehörigen ungerichteten Graphen habe.

01:03:20.730 --> 01:03:23.730
Und was man jetzt aufpassen muss, ist bei der Wurzel.

01:03:24.210 --> 01:03:26.750
Bei dem gerichteten Graphen konnten wir zeigen, dass die Wurzel

01:03:26.750 --> 01:03:30.670
eindeutig bestimmt ist, bei dem ungerichteten Graphen geht das nicht

01:03:30.670 --> 01:03:30.950
mehr.

01:03:31.690 --> 01:03:35.510
Dadurch, dass ich keine Richtungsinformationen habe, kann ich also

01:03:35.510 --> 01:03:43.150
Pfade, die ich vorher hatte, jetzt sowohl vorwärts als auch rückwärts

01:03:43.150 --> 01:03:46.950
durchlaufen in meinem zugehörigen ungerichteten Graphen.

01:03:46.950 --> 01:03:50.370
Das heißt, ich kann nicht mehr erkennen, was jetzt die Wurzel ist und

01:03:50.370 --> 01:03:54.410
der Trick ist halt, dass man bei einem ungerichteten Baum explizit

01:03:54.410 --> 01:03:58.290
definieren muss, welche der Knoten in dem ungerichteten Baum denn

01:03:58.290 --> 01:04:00.150
jetzt bitteschön meine Wurzel sein soll.

01:04:00.450 --> 01:04:03.170
Das kann ich jetzt also nicht mehr aus der Struktur ablesen, sondern

01:04:03.170 --> 01:04:07.550
das muss ich als Mensch von außen bei diesem ungerichteten Graph dann

01:04:07.550 --> 01:04:09.110
per Hand definieren.

01:04:11.770 --> 01:04:14.690
Knotengrad in ungerichteten Graphen ist ganz blöd.

01:04:17.610 --> 01:04:22.190
Da gibt es viele unterschiedliche Definitionen in der Literatur, da

01:04:22.190 --> 01:04:23.350
muss man ein bisschen aufpassen.

01:04:23.350 --> 01:04:27.090
Was wir hier in der Vorlesung machen ist, dass wir sagen, dass der

01:04:27.090 --> 01:04:32.210
Grad eines Knotens in einem ungerichteten Graphen, das ist eben

01:04:32.210 --> 01:04:39.650
erstmal die Anzahl der Kanten, die an ihn angedockt sind, die keine

01:04:39.650 --> 01:04:40.450
Schlingen sind.

01:04:41.550 --> 01:04:45.610
Und falls ich eine Schlinge habe, dann wird zwei dazu gezählt.

01:04:46.650 --> 01:04:51.150
Das heißt, wenn ich die Schlinge habe, die dockt zweimal an diesem

01:04:51.150 --> 01:04:55.370
Knoten an, da wo sie losgeht und da wo sie reingeht und ich zähle

01:04:55.370 --> 01:05:01.450
beides mit, wenn ich den Grad des Knotens ermitteln will.

01:05:01.450 --> 01:05:04.730
Das heißt also, wenn ich es mir grafisch hinmale, ich zähle, wie

01:05:04.730 --> 01:05:08.890
häufig dockt da so ein Strich an diesem Knoten, dessen Grad ich haben

01:05:08.890 --> 01:05:10.630
möchte, entsprechend an.

01:05:13.070 --> 01:05:15.270
Soviel zum Thema ungerichteten Graphen.

01:05:16.050 --> 01:05:19.410
Beim nächsten Mal werden wir uns dann nochmal anschauen diese

01:05:19.410 --> 01:05:25.410
Relationen, die durch Graphen induziert werden.

01:05:25.410 --> 01:05:29.750
Und die haben dann noch eine interessante Eigenschaft, die uns dann

01:05:29.750 --> 01:05:33.030
dazu bringt, dass wir nochmal die kompletten Eigenschaften einer

01:05:33.030 --> 01:05:36.730
bestimmten Relation und einer besonderen Art von Relation sehen

01:05:36.730 --> 01:05:39.110
werden, nämlich die der Äquivalenzrelation.

01:05:39.790 --> 01:05:42.410
Aber das machen wir dann nächsten Mittwoch.

01:05:43.210 --> 01:05:44.150
Schönes Wochenende.