WEBVTT

00:09.060 --> 00:10.000
Ja, guten Tag.

00:12.020 --> 00:17.240
Wir waren beim letzten Mal fast fertig geworden mit kürzesten Wegen.

00:19.280 --> 00:22.940
Wir hatten uns dann zuletzt verschiedenste Varianten des kürzesten

00:22.940 --> 00:24.500
Wege -Problems angeschaut.

00:24.960 --> 00:27.900
Also wir hatten ja angefangen mit einer zu allen.

00:28.700 --> 00:31.120
Dann haben wir gesagt, wir können auch von überall nach überall

00:31.120 --> 00:31.580
suchen.

00:34.180 --> 00:37.040
Ich hatte dann auch schon angefangen, zusammenzufassen.

00:39.440 --> 00:41.280
Vielleicht auch nochmal zur Erinnerung.

00:41.600 --> 00:44.920
Also wir haben uns ja die meiste Zeit mit beliebigen gerichteten

00:44.920 --> 00:48.980
Graphen befasst, aber nicht negative Kantengewichte angenommen.

00:50.860 --> 00:54.400
Und da war dann halt Dijkstra's Algorithmus ein sehr gutes Verfahren.

00:58.000 --> 01:02.220
Wir haben dann letztes Mal gesehen, dass man bei a-zyklischen Graphen

01:02.220 --> 01:05.400
sogar in linearer Zeit fertig wird und dort sogar negative

01:05.400 --> 01:07.140
Kantengewichte akzeptieren kann.

01:07.140 --> 01:12.220
Während man im allgemeinen Fall bei Anwesenheit negativer

01:12.220 --> 01:17.560
Kantengewichte deutlich komplexere Algorithmen braucht, also die sind

01:17.560 --> 01:21.620
auch sehr einfach, aber haben im Worst-Case eine viel höhere Laufzeit.

01:22.380 --> 01:27.940
Wellman-Ford-Algorithmus braucht n mal m Laufzeit, verglichen mit m

01:27.940 --> 01:30.760
plus n log n von Dijkstra's Algorithmus.

01:32.460 --> 01:35.640
Beim Dijkstra waren halt Prioritätslisten ganz wichtig.

01:36.520 --> 01:40.480
So, jetzt wollte ich Ihnen noch ein bisschen Blick über den Tellerrand

01:40.480 --> 01:40.800
geben.

01:42.120 --> 01:44.540
Diejenigen, die schon mal in die Folien geguckt haben, da kommt jetzt

01:44.540 --> 01:47.860
ganz viel über Beschleunigungstechniken, das werden wir jetzt so in

01:47.860 --> 01:50.580
der Vorlesung nicht machen, aber nächste Woche in der Übung werden wir

01:50.580 --> 01:56.160
Ihnen da noch eine konkrete Technik aus unserer Arbeit in der

01:56.160 --> 02:00.360
Arbeitsgruppe vorstellen und hier möchte ich jetzt erstmal so ein ganz

02:00.360 --> 02:03.200
bisschen nochmal Überblick geben, was gibt es denn noch.

02:03.780 --> 02:10.480
Ich habe ja gesagt, Prioritätslisten sind ganz wichtig, wenn man

02:10.480 --> 02:14.020
rausfinden will, wie schnell genau ist denn jetzt Dijkstra's

02:14.020 --> 02:14.640
Algorithmus.

02:14.780 --> 02:23.180
Also wir hatten ja mit Binary Heaps m plus n mal log n rausgekriegt,

02:23.460 --> 02:26.940
mit Fibonacci Heaps, die wir in Algorithmen 2 machen, das ist dann m

02:26.940 --> 02:34.800
plus n log n und das Beste im Moment Bekannte ist m plus n log log n,

02:36.560 --> 02:40.280
ist dann allerdings nicht mehr vergleichsbasierte Prioritätslisten,

02:40.620 --> 02:49.600
sondern man nutzt dann halt die Bit-Repräsentation der Zahlen aus,

02:49.720 --> 02:52.180
macht dann Annahmen darüber, wie groß die sind und sowas.

02:55.060 --> 02:58.240
Jetzt gibt es noch eine ganze Menge Verallgemeinerungen von kürzesten

02:58.240 --> 03:02.020
Wege -Problemen, eine Sache ist zum Beispiel, was ist, wenn man

03:02.020 --> 03:03.520
mehrere Zielfunktionen hat.

03:03.760 --> 03:08.180
Wenn Sie zum Beispiel Routenplanung machen, Sie wollen von Karlsruhe

03:08.180 --> 03:12.520
nach München fahren, Sie wollen schon eine schnelle Route haben, aber

03:12.520 --> 03:14.480
vielleicht wollen Sie auch eine haben, die wenig kostet.

03:15.420 --> 03:18.800
Aber meistens ist es dann so, wenn Sie zum Beispiel in Frankreich noch

03:18.800 --> 03:21.740
schlimmer Mautstrecken vermeiden wollen, müssen Sie dann langsamere

03:21.740 --> 03:22.260
Routen nehmen.

03:22.780 --> 03:27.020
Das heißt, da gibt es dann einen Tradeoff zwischen mehreren

03:27.020 --> 03:31.380
Zielfunktionen, vielleicht auch noch Schönheit der Route und was nicht

03:31.380 --> 03:34.720
alles, und das ist dann ein schwieriges kombinatorisches

03:34.720 --> 03:35.680
Optimierungsproblem.

03:35.940 --> 03:39.500
Also mit einer Zielfunktion ist das schon viel einfacher, sondern es

03:39.500 --> 03:41.840
ist tatsächlich auch ein Thema, wo wir uns auch in der Arbeitsgruppe

03:41.840 --> 03:43.180
beschäftigen.

03:46.800 --> 03:50.040
Dann, was ist, wenn Sie nicht ein Ziel haben, sondern mehrere?

03:51.000 --> 03:53.380
Dann können Sie sagen, ja, kein Problem, dann muss ich halt mehrere

03:53.380 --> 03:56.940
kürzeste Wege Probleme lösen, aber so einfach ist das nicht, Sie

03:56.940 --> 03:59.700
müssen dann ja noch zusätzlich entscheiden, in welcher Reihenfolge

03:59.700 --> 04:03.660
besuchen Sie die Ziele, Sie werden ja nicht jedes Mal wieder

04:03.660 --> 04:10.780
zurückfahren wollen nach Hause, sondern da geht es dann eher darum,

04:10.840 --> 04:13.580
wie kann ich die richtige Reihenfolge bestimmen, und da gibt es halt,

04:14.040 --> 04:17.920
wenn ich N Ziele habe, N fakultätmögliche Reihenfolgen, das heißt, das

04:17.920 --> 04:22.220
ist eine kombinatorische Explosion, die einem da droht, wie geht man

04:22.220 --> 04:22.760
damit um?

04:24.000 --> 04:27.540
Mit dem Thema werden wir uns dann im letzten Kapitel über Optimierung

04:27.540 --> 04:29.760
noch mal auseinandersetzen.

04:32.020 --> 04:35.200
Und was man manchmal auch haben will, ist nicht einen Weg finden,

04:35.280 --> 04:36.040
sondern mehrere.

04:36.800 --> 04:40.900
Die Theoretiker sagen dann klassisch, ja, ich möchte disjunkte Wege

04:40.900 --> 04:46.020
haben, das ist auch ein relativ schwieriges Problem, in der Praxis ist

04:46.020 --> 04:49.320
es dann oft so, es gibt vielleicht keine disjunkten Wege, oder die

04:49.320 --> 04:54.120
sind dann völlig unpraktikabel, aber man möchte trotzdem so etwas wie

04:54.120 --> 04:57.320
Alternativrouten haben, und dann will man überhaupt mal modellieren,

04:57.380 --> 04:58.360
was sind denn gute Alternativen.

04:59.620 --> 05:03.160
Wir sollten halt sicherlich nicht zu viel mit der kürzesten Route

05:03.160 --> 05:07.220
zusammen übereinstimmen, weil dann kann ich es mir auch gleich

05:07.220 --> 05:11.760
schenken, und meistens will man die ja haben, um irgendwie Robustheit

05:11.760 --> 05:12.260
zu haben.

05:12.260 --> 05:15.940
Aber falls dann die Durchsage kommt, hier ist Stau an der und der

05:15.940 --> 05:18.160
Stelle, dann nimmt man halt die Alternativroute oder so.

05:19.500 --> 05:22.860
Und wenn man dann nur kleine Varianten hat, bringt es das nicht.

05:22.980 --> 05:26.040
Aber andererseits sollten die auch nicht zu lang sein, nicht zu

05:26.040 --> 05:30.480
kompliziert aussehen, da kann man sich alle möglichen Dinge überlegen.

05:31.680 --> 05:34.280
Da gibt es auch Arbeiten zu, bei uns in der Arbeitsgruppe zum

05:34.280 --> 05:34.580
Beispiel.

05:34.580 --> 05:43.930
So, dann eine Variante, die eigentlich besonders wichtig ist, die wir

05:43.930 --> 05:49.170
uns bisher noch nicht angeguckt haben, ist, was ist denn, wenn ich nur

05:49.170 --> 05:51.690
einen Startknoten und einen Zielknoten habe?

05:52.590 --> 05:56.050
Kann ich das nicht schneller als das allgemeine One-to-all-Problem?

05:57.730 --> 06:01.250
Naja, da gibt es eine ganze Menge Tricks, und der einfachste, den habe

06:01.250 --> 06:04.410
ich Trick Null genannt, weil der fast offensichtlich ist.

06:04.410 --> 06:08.090
Wenn Sie jetzt mit Dijkstra's Algorithmus suchen, habe ich ja gesagt,

06:08.670 --> 06:12.330
suchen Sie ja im Prinzip so eine Scheibe ab in dem Graphen.

06:13.570 --> 06:18.150
Sie ziehen immer weitere Kreise, man entfernt die Knoten ja in der

06:18.150 --> 06:21.410
Reihenfolge ihrer kürzeste Wegeentfernung aus der Prioritätsliste.

06:23.770 --> 06:29.190
Naja, und wenn Sie dann das T aus der Prioritätsliste entfernen, den

06:29.190 --> 06:32.250
Zielknoten, dann ist klar, dass Sie fertig sind.

06:33.790 --> 06:37.930
Weil Sie haben ja nicht negative Kantengewichte und dann wird es

06:37.930 --> 06:42.850
sicherlich keinen Pfad geben, der irgendwie erst noch weiter rausfährt

06:42.850 --> 06:45.550
und dann wieder zurück, weil das kann ja nur noch länger werden.

06:48.290 --> 06:51.390
Also das kann einiges sparen, vor allem in der Praxis, stellen Sie

06:51.390 --> 06:57.250
sich vor, Sie haben ein Netzwerk für ganz Europa und bauen ein

06:57.250 --> 06:58.070
Navigationssystem.

06:58.070 --> 07:02.870
Naja, die meisten Anfragen werden wahrscheinlich eher einigermaßen

07:02.870 --> 07:06.430
lokal sein, wer fährt schon regelmäßig nach Portugal mit dem Auto?

07:08.170 --> 07:09.590
Das heißt, da gewinnen Sie einiges.

07:10.330 --> 07:14.350
Als Theoretiker würde ich sagen, selbst im Average Case, wenn ich

07:14.350 --> 07:17.750
einen zufälligen Knoten wähle, muss ich immer noch die Hälfte der

07:17.750 --> 07:20.610
Knoten besuchen, bis ich den gefunden habe, im Mittel.

07:21.230 --> 07:24.290
Das heißt, in dem Fall spart es nicht so viel.

07:26.850 --> 07:30.870
Das ist aber dann ein gutes Beispiel dafür, dass das Verhalten im

07:30.870 --> 07:33.110
Mittel nicht immer das Verhalten in der Realität ist.

07:34.110 --> 07:37.350
Also hier haben wir schon mal ein bisschen was gewonnen, wenn der

07:37.350 --> 07:39.090
Zielknoten nah am Startknoten ist.

07:39.330 --> 07:41.650
Und in einigen Anwendungen ist das offenbar der Fall.

07:43.110 --> 07:45.630
Und dann gibt es ja noch eine ganze Menge andere Techniken, die

07:45.630 --> 07:48.050
untersucht wurden, zum Teil auch, wie gesagt, bei uns in der

07:48.050 --> 07:51.610
Arbeitsgruppe oder bei meiner Kollegin Dorothea Wagner.

07:53.510 --> 07:58.030
Eine Sache, die ich machen kann, ist vom Start vorwärts suchen und vom

07:58.030 --> 07:58.870
Ziel rückwärts.

07:59.830 --> 08:01.470
Das ist ja völlig symmetrisch.

08:01.630 --> 08:05.890
Also wenn ich eine Rückwärtssuche vom Ziel mache, gucke ich mir halt

08:05.890 --> 08:11.430
die umgedrehten Kanten an, aber finde dann eben den kürzesten Wegebaum

08:11.430 --> 08:14.610
von allen Knoten, die ich erreicht habe, zu dem Ziel.

08:15.310 --> 08:20.290
Man kann sich dann überlegen, wenn das tatsächlich so eine Ausbreitung

08:20.290 --> 08:25.030
in der zweidimensionalen Ebene ist, dass diese beiden Suchen

08:25.030 --> 08:30.890
zusammentreffen, wenn der Radius sowas ist wie die Hälfte des

08:30.890 --> 08:31.610
Abstands.

08:32.290 --> 08:38.570
Und dann sagt Ihnen Schulmathematik, dass die Summe der Flächen dieser

08:38.570 --> 08:46.710
beiden Suchen nur halb so groß ist wie eine Fläche von einem Kreis mit

08:46.710 --> 08:47.810
dem doppelten Radius.

08:48.450 --> 08:51.210
Weil die Fläche ja quadratisch mit dem Radius steigt.

08:52.290 --> 08:55.790
Und das ist tatsächlich auch, was man so ungefähr beobachtet, wenn man

08:55.790 --> 09:00.910
das implementiert für Straßennetzwerke.

09:01.010 --> 09:03.550
Bei anderen Netzwerken ist die Beschleunigung oft sogar noch viel

09:03.550 --> 09:03.990
größer.

09:05.150 --> 09:06.950
Es gibt aber auch Fälle, wo das wenig bringt.

09:09.150 --> 09:12.570
Aber immerhin, das ist ein Faktor 2 und das kriegt man fast umsonst,

09:13.210 --> 09:15.190
außer wenn man ins Kleingedruckte guckt.

09:15.570 --> 09:18.790
Da steht dann nämlich, man muss dann den Graphen eigentlich zweimal

09:18.790 --> 09:20.950
abspeichern, einmal in Vorwärts- und einmal in Rückwärtsreihenfolge.

09:22.430 --> 09:24.830
Das ist ja manchmal teuer.

09:26.410 --> 09:28.850
Trotzdem, Rückwärtssuche ist eine wichtige Technik, weil die mit

09:28.850 --> 09:32.210
anderen Beschleunigungstechniken manchmal zusammenwirken kann.

09:33.590 --> 09:37.270
Dann gibt es eine Idee, zielgerichtete Suchen zu machen, das werden

09:37.270 --> 09:40.510
wir in Algorithmen 2 uns noch etwas näher anschauen, weil es da auch

09:40.510 --> 09:46.210
interessante mathematische Methoden gibt, die auch in anderen Graphen

09:46.210 --> 09:49.270
-Algorithmen auftreten, mit Knotenpotentialen und sowas.

09:50.130 --> 09:57.490
Also man manipuliert die Suche so, dass man eben nicht so einen Kreis

09:57.490 --> 10:01.550
hier immer weiter abwachsen lässt, sondern lässt den in Richtung des

10:01.550 --> 10:03.470
Ziels wachsen, den Suchraum.

10:03.590 --> 10:07.010
Und da gibt es halt Techniken, wie man das erreichen kann, und dann

10:07.010 --> 10:08.990
ist halt die Hoffnung, dass das deutlich kleiner ist.

10:10.230 --> 10:12.690
Bei Straßennetzwerken ist das jetzt so, das funktioniert auch ganz

10:12.690 --> 10:16.710
gut, also mit den einfachen Techniken bringt das sogar einen Faktor 3

10:16.710 --> 10:17.370
oder sowas.

10:18.950 --> 10:21.730
Die schlechte Nachricht ist dann, wenn Sie das mit bidirektional

10:21.730 --> 10:27.230
kombinieren, dann wird es schwierig, die naive Art, das zu machen, zu

10:27.230 --> 10:31.250
inkorrekten Ergebnissen, was tatsächlich auch bedeutet, dass einige

10:31.250 --> 10:34.170
Navigationssysteme, die immer noch auf dem Markt sind, Ihnen keine

10:34.170 --> 10:39.210
optimalen Routen liefern, weil die das aus verschiedenen Gründen nicht

10:39.210 --> 10:41.290
perfekt machen, war da eine Frage?

10:44.190 --> 10:47.190
Das heißt, die beiden Sachen gehen nicht so gut zusammen, man muss

10:47.190 --> 10:50.850
hier aufpassen, wenn man zielgerichtete bidirektionale Suche macht,

10:50.890 --> 10:51.810
das geht aber auch.

10:53.330 --> 10:56.630
Vor allem gibt es einige sehr starke Methoden für zielgerichtete

10:56.630 --> 10:58.590
Suche, bei denen das dann insgesamt Sinn macht.

10:59.590 --> 11:04.170
Was wir gemacht haben, ist ein bisschen anders und zumindest bei

11:04.170 --> 11:09.210
Straßennetzwerken noch effektiver, wir machen auch bidirektionale

11:09.210 --> 11:14.370
Suche, und dieses Bild soll jetzt sowas sagen wie, den kompletten

11:14.370 --> 11:17.430
Graphen suchen wir eigentlich nur in der Umgebung von Start und Ziel

11:17.430 --> 11:21.430
ab, und je weiter wir wegkommen von Start und Ziel, desto stärker

11:21.430 --> 11:23.430
dünnen wir die Suche aus.

11:24.670 --> 11:27.490
Und das ist in Straßennetzwerken auch sehr intuitiv.

11:27.950 --> 11:31.870
Wenn Sie von hier nach München fahren, werden Sie sich nicht sämtliche

11:31.870 --> 11:36.190
Wohnstraßen in Stuttgart anschauen, auch nicht die in Ulm, obwohl Sie

11:36.190 --> 11:39.350
da ganz in der Nähe dran vorbeifahren, und so eine zielgerichtete

11:39.350 --> 11:40.750
Suche das durchaus tun würde.

11:40.750 --> 11:47.710
Aber Sie wissen irgendwie intuitiv, diese Wohnstraße da in Neu-Ulm, so

11:47.710 --> 11:52.830
und so, die ist garantiert nicht relevant für eine Langstreckenroute.

11:55.760 --> 11:59.080
Das Problem dabei ist auch, das haben die Praktiker auch lange

11:59.080 --> 12:03.140
gemacht, also das ist in einigen heutigen Navigationssystemen auch

12:03.140 --> 12:08.840
immer noch drin, da übersehen Sie ab und zu einen Schleichweg, wenn

12:08.840 --> 12:12.940
Sie das machen, und Sie müssen dann sehr intensiv an den Daten

12:12.940 --> 12:17.120
arbeiten, die manuell so aufbereiten, dass Sie die richtigen Straßen

12:17.120 --> 12:18.760
als Fernstraße deklarieren.

12:21.020 --> 12:25.940
Also was dann in der Praxis oft passiert ist, dass man am Anfang dann

12:25.940 --> 12:29.460
bestimmte Autobahnzubringer oder sowas vergisst und dann ganz

12:29.460 --> 12:31.120
merkwürdige Ergebnisse kriegt.

12:35.980 --> 12:40.600
Und eine andere Technik, das ist jetzt erstmal sehr allgemein, ist,

12:40.720 --> 12:45.500
dass man einfach Teilabschnitte von Routen vorberechnet und in

12:45.500 --> 12:47.200
irgendwelchen Datenstrukturen ablegt.

12:47.880 --> 12:50.060
Im Extremfall Tabellen macht.

12:51.060 --> 12:57.320
Das extreme Ergebnis wäre zu sagen, ich mache einfach eine

12:57.320 --> 13:02.460
Abstandstabelle von allen Knoten zu allen Knoten, und dann brauchen

13:02.460 --> 13:04.500
Sie überhaupt nicht mehr wirklich suchen, da müssen Sie nur noch

13:04.500 --> 13:07.800
nachschlagen, das braucht allerdings quadratischen Platz.

13:08.780 --> 13:13.880
Und was wir uns dann allerdings angeschaut haben, ist das sogenannte

13:13.880 --> 13:17.900
Transit -Node-Routing, sagen wir das folgende, wir machen so eine

13:17.900 --> 13:21.900
Abstandstabelle nicht für alle Knoten, sondern nur für eine sorgfältig

13:21.900 --> 13:27.000
ausgewählte Menge von wichtigen Knoten, Autobahnauffahrten, Brücken

13:27.000 --> 13:33.240
und sowas, und wir machen dann eine relativ komplizierte

13:33.240 --> 13:39.720
Vorberechnung, das heißt, die ist gar nicht so super kompliziert, aber

13:39.720 --> 13:44.480
man muss da schon ein bisschen aufpassen, wo wir uns für jeden Knoten

13:44.480 --> 13:49.180
nur merken, welche wichtigen Knoten in der Nähe werden eigentlich

13:49.180 --> 13:49.940
benötigt.

13:49.940 --> 13:58.760
Das heißt, wenn ich eine Fernstrecke fahre, beobachtet man, fährt man

13:58.760 --> 14:04.340
für jeden Knoten immer wieder über die gleichen Eingänge ins

14:04.340 --> 14:06.300
Fernstraßennetzwerk, sage ich mal.

14:07.020 --> 14:11.220
Also wenn Sie zum Beispiel von Ihrer Studentenbude mit dem Auto

14:11.220 --> 14:17.160
irgendwo hinfahren, egal ob das dann Richtung Norden, Süden, Osten,

14:17.260 --> 14:20.560
Westen ist, Sie fahren eigentlich immer über die gleichen drei oder

14:20.560 --> 14:22.400
vier Autobahnauffahrten, nehme ich an.

14:23.140 --> 14:26.460
Dann merken Sie sich einfach, wie weit es zu diesen Autobahnauffahrten

14:26.460 --> 14:32.720
ist, das Gleiche machen Sie auch am Ziel, und dann müssen Sie nur noch

14:32.720 --> 14:36.360
die Abstände zwischen diesen Auffahrten, die relevant sind, in der

14:36.360 --> 14:41.720
Tabelle nachschlagen, und dazu addieren Sie dann die Strecke dahin und

14:41.720 --> 14:44.820
da weg, und dann nehmen Sie von diesen Alternativen die beste.

14:45.280 --> 14:47.520
Und das ist zum Beispiel ein sehr schnelles Verfahren.

14:48.680 --> 14:51.960
Da müssen Sie nur noch aufpassen, es könnte ja auch sein, dass Sie

14:51.960 --> 14:55.700
jetzt eine Start-Ziel-Anfrage haben, wo Start und Ziel so nah

14:55.700 --> 14:58.140
beieinander sind, dass Sie gar nicht erst ins Fernstraßennetz

14:58.140 --> 15:01.660
reingehen, und Sie müssen da aufpassen, dass Sie den Fall auch korrekt

15:01.660 --> 15:02.140
bearbeiten.

15:03.280 --> 15:08.120
Und es gibt noch eine ganze Reihe anderer Techniken, die aber sehr oft

15:08.120 --> 15:10.960
eine Zusammensetzung dieser Basisideen sind.

15:13.700 --> 15:17.780
Mehr dazu erfahren Sie in der Spezialvorlesung Routenplanung, die

15:17.780 --> 15:21.800
macht meistens ein Mitarbeiter von meiner Kollegin Frau Wagner.

15:24.860 --> 15:28.560
Und das Wichtige bei diesen fortgeschrittenen Techniken ist eigentlich

15:28.560 --> 15:30.840
immer, dass man Vorberechnungen macht.

15:31.080 --> 15:37.240
Also man hat ein Straßennetzwerk, das sich selten ändert, und da lohnt

15:37.240 --> 15:42.020
es dann, einen gewissen Aufwand in Vorberechnungen zu stecken, das

15:42.020 --> 15:45.840
sind ein paar Minuten bis ein paar Stunden, je nach Verfahren, und

15:45.840 --> 15:49.700
dann hat man eben in vielen Anwendungen Millionen von Start-Ziel

15:49.700 --> 15:53.280
-Anfragen, über die man dann diese Vorberechnungen amortisieren kann.

15:54.520 --> 15:57.360
Und das ist jetzt auch wieder ein Beispiel für ein

15:57.360 --> 16:02.440
Algorithmenentwurfsmuster, das ganz allgemein nützlich ist, also sehr

16:02.440 --> 16:05.540
oft lohnt es sich, Vorberechnungen durchzuführen, damit man dann

16:05.540 --> 16:08.220
spätere Operationen beschleunigen kann.

16:14.590 --> 16:18.490
Das hier will ich jetzt im Detail nicht machen, wie gesagt, dazu

16:18.490 --> 16:24.390
werden wir aktualisierte Folien in der Übung zeigen.

16:29.480 --> 16:33.240
Und stattdessen fange ich jetzt an mit dem Kapitel über minimale

16:33.240 --> 16:33.800
Spannbäume.

16:36.600 --> 16:39.960
Wieder so eine Motivation, die nichts mit Computern zu tun hat.

16:40.560 --> 16:42.580
Stellen Sie sich vor, Sie haben eine Inselgruppe,

16:46.840 --> 16:54.280
wir sind hier in der Zeit vor der Erfindung von Flugzeugen, ja, das

16:54.280 --> 16:58.480
ist jetzt vielleicht eine Region eines Landes oder ein selbstständiger

16:58.480 --> 17:02.280
Staat, die wollen natürlich Verkehr innerhalb dieser Inselgruppe

17:02.280 --> 17:08.400
ermöglichen, ist aber ein sehr armes Land, die sagen, wir haben nur

17:08.400 --> 17:11.120
ganz wenig Geld, das müssen wir irgendwo beim internationalen

17:11.120 --> 17:14.560
Währungsfonds ausleihen und die wollen ganz viel Zinsen und so weiter.

17:14.560 --> 17:21.060
Und wir haben uns jetzt halt schon angeguckt, naja, wir können jetzt

17:21.060 --> 17:24.620
im Prinzip natürlich zwischen jedem Paar von Inseln eine Fährlinie

17:24.620 --> 17:31.860
anlegen, aber das kostet unterschiedlich viel im Betrieb und wenn es

17:31.860 --> 17:34.260
eine längere Strecke ist, muss man vielleicht auch eine größere Fähre

17:34.260 --> 17:37.360
kaufen oder mehr Fähren, damit man da oft genug fahren kann.

17:37.360 --> 17:41.540
Also nehmen wir mal an, wir haben uns für jedes Paar von Inseln

17:41.540 --> 17:45.860
angeguckt, was ist das Minimum an Kosten, was ich brauche, um da eine

17:45.860 --> 17:47.420
Fährverbindung zu etablieren.

17:48.720 --> 17:51.620
Also hier sind zwei nah beieinander liegende, die kann ich mit Kosten

17:51.620 --> 17:54.500
2 verbinden, die mit Kosten 7 und so weiter.

17:57.040 --> 17:59.780
Und dann ist die Frage, welche Fährverbindungen sollte ich jetzt

17:59.780 --> 18:02.850
tatsächlich einrichten, sodass die Gesamtkosten minimiert werden.

18:05.410 --> 18:12.130
Das ist eine sehr einfache Variante eines Netzwerkentwurfproblems, und

18:12.130 --> 18:16.250
da gibt es eine ganze Reihe anderer Varianten davon, zum Beispiel, wie

18:16.250 --> 18:20.390
verkable ich Häuser mit Telefonleitungen und so weiter.

18:22.730 --> 18:27.830
Ja, dieses Bild hat meine Sekretärin gemalt, die Umrisse von den

18:27.830 --> 18:29.850
Inseln, die gibt es wirklich.

18:29.970 --> 18:31.630
Weiß jemand, welche Inseln das sind?

18:33.110 --> 18:34.230
Erkennt jemand eine wieder?

18:35.890 --> 18:38.690
Ich bin selber nicht mehr ganz sicher, aber ich glaube, das sind vier

18:38.690 --> 18:39.390
von den Kanareninseln.

18:41.030 --> 18:44.790
Also insbesondere die da, das ist Teneriffa oder La Palma, ich weiß

18:44.790 --> 18:45.350
nicht mehr genau.

18:45.350 --> 18:49.250
Die anderen müssten dann auch irgendwie in dieses Schema passen.

18:49.330 --> 18:51.950
Vielleicht ist das da La Gomera, also die sind not to scale.

18:52.970 --> 18:55.470
Die haben wir alle auf ungefähr die gleiche Größe gebracht, um das

18:55.470 --> 18:56.370
Bild schön zu machen.

18:59.290 --> 19:00.710
Wie lösen wir so ein Problem?

19:01.290 --> 19:02.870
Als erstes formalisieren.

19:05.810 --> 19:09.030
Also es geht um minimale Spannbäume, wir haben einen ungerichteten

19:09.030 --> 19:12.350
Graphen, nehmen wir zunächst mal an, der ist auch zusammenhängend.

19:13.450 --> 19:18.490
In Knoten, im Kanten, wir haben positive Kantengewichte.

19:20.050 --> 19:23.290
Hier ist es übrigens so, wir könnten auch negative und Null zulassen,

19:23.430 --> 19:27.570
aber das würde jetzt wieder einige Spezialfalluntersuchungen

19:27.570 --> 19:29.590
erfordern, die lassen wir jetzt mal weg.

19:30.250 --> 19:32.630
Ist aber auch ein schönes Thema für Übungsaufgaben.

19:32.750 --> 19:37.730
Wie lösen Sie das Problem, wenn diese Restriktion wegfällt?

19:38.770 --> 19:43.270
Da kann man einfach Reduktionen angeben, wie man das dann

19:43.270 --> 19:45.650
transformiert in ein Problem mit dieser Normalform.

19:47.970 --> 19:50.590
Die Aufgabenstellung ist, wir wollen einen Baum suchen.

19:53.270 --> 19:55.330
Das ist ja auch ein Graph V,T.

19:55.550 --> 19:56.890
T ist eine Teilmenge von E.

19:58.850 --> 20:04.390
Und das Gesamtgewicht der Kanten in T soll minimiert werden.

20:05.270 --> 20:05.670
Ja.

20:07.070 --> 20:09.270
Und das ist auch wieder eine schöne Übungsaufgabe.

20:09.370 --> 20:11.350
Das ist äquivalent zu der Aufgabenstellung.

20:12.370 --> 20:17.970
Finden eine Teilmenge von Kanten mit minimalem Gesamtgewicht, sodass

20:17.970 --> 20:21.270
es von jedem Knoten zu jedem Knoten einen Pfad gibt.

20:21.910 --> 20:23.910
Es ist halt immer ein Baum, der optimal ist.

20:24.030 --> 20:27.030
Weil stellen Sie sich vor, Sie haben mehr als einen Baum, dann gibt es

20:27.030 --> 20:31.350
immer eine Kante, die Sie weglassen können, und da die alle positives

20:31.350 --> 20:34.730
Gewicht haben, kriegen Sie damit eine billigere Verbindung.

20:39.010 --> 20:40.570
Fragen zu der Problemstellung?

20:43.900 --> 20:46.580
Sagt mal, habt ihr zufällig eine Fernsteuerung dabei?

20:46.740 --> 20:47.600
Ich hatte meine vergessen.

20:51.220 --> 20:51.380
Ja.

20:51.980 --> 20:58.440
So, jetzt mal gleich zu dem Fall, wenn der nicht zusammenhängt, der

20:58.440 --> 21:01.980
Graph ist, dann spricht man auch von minimalen spannenden Wäldern oder

21:01.980 --> 21:03.680
Forests, MSF.

21:05.600 --> 21:10.520
Und dann ist klar, dann möchte man für jede Zusammenhangskomponente

21:10.520 --> 21:12.560
des Graphen einen minimalen Spannbaum suchen.

21:15.140 --> 21:20.280
Und man kann die minimalen Spannbaum-Algorithmen leicht

21:20.280 --> 21:24.380
verallgemeinern, dass sie minimale spannende Wälder erzeugen.

21:25.420 --> 21:26.240
Anwendungen.

21:26.460 --> 21:32.380
Das Netzwerkentwurfsproblem habe ich schon genannt, mit diesem relativ

21:32.380 --> 21:34.160
plastischen Beispiel der Fährlinien.

21:35.320 --> 21:38.540
Erstaunlicherweise ist das in der Praxis relativ selten, dass das

21:38.540 --> 21:40.540
genau ein minimales Spannbaumproblem ist.

21:41.060 --> 21:44.260
Meistens hat man in der Praxis zusätzliche Bedingungen oder andere

21:44.260 --> 21:47.540
Möglichkeiten, die daraus ein komplizierteres Problem machen.

21:49.620 --> 21:53.020
Tatsächlich verwendet werden minimale Spannbäume für die folgenden

21:53.020 --> 21:53.620
zwei Sachen.

21:54.100 --> 21:58.940
Das eine ist eine spannende mathematische Eigenschaft, nennt man eine

21:58.940 --> 22:04.660
Variante des kürzesten Wege-Problems, das Bottleneck-Shortest-Path

22:04.660 --> 22:07.160
-Problem oder Engpass-Kürzeste-Wege-Problem.

22:08.560 --> 22:16.380
Wir haben eine Anfrage, ST, suchen einen Pfad, und da geht es jetzt

22:16.380 --> 22:21.980
nicht um die Summe der Kantengewichte, sondern um das maximale

22:21.980 --> 22:22.760
Kantengewicht.

22:27.420 --> 22:30.640
Und übrigens ist es hier auch so, das kann man dann sogar umdrehen,

22:30.640 --> 22:32.840
und das ist vielleicht die plastischere Anwendung.

22:33.300 --> 22:36.280
Man kann hier das auch leicht transformieren in ein Problem, wo man

22:36.280 --> 22:41.100
für gegebenen ST sucht man einen Pfad, wo das minimale Kantengewicht

22:41.100 --> 22:42.080
maximiert wird.

22:42.840 --> 22:45.120
Und da wäre jetzt zum Beispiel eine Anwendung, stellen Sie sich vor,

22:45.180 --> 22:49.780
Sie haben ein Kommunikationsnetzwerk mit Punkt-zu-Punkt-Verbindungen

22:49.780 --> 22:53.380
zwischen den Knoten, und Sie wollen jetzt zwischen S und T irgendwie

22:53.380 --> 22:54.780
ein Video übertragen.

22:55.660 --> 22:58.280
Mit einer möglichst guten Bildqualität.

22:59.340 --> 23:03.260
Dann ist aber die Bandbreite, die Sie erreichen, zumindest wenn Sie

23:03.260 --> 23:08.440
die Daten auf einem Pfad übertragen wollen, halt beschränkt durch die

23:08.440 --> 23:13.100
Leitung mit der geringsten Übertragungsbandbreite.

23:14.720 --> 23:18.640
Sie merken das bewusst oder unbewusst, wenn Sie im Internet browsen,

23:19.520 --> 23:27.240
immer wieder oft hakelt dann eine Filmübertragung, weil halt irgendwo

23:27.240 --> 23:28.140
das langsam ist.

23:28.220 --> 23:33.440
Sei das beim Anschluss ans WLAN, bei Ihrem Zugang zum Netzwerk,

23:34.720 --> 23:37.980
irgendwo zwischendurch, durch Überlastung des Servers und so weiter.

23:38.080 --> 23:40.580
Wenn einer langsam ist, reicht, dass das alles langsam ist.

23:40.660 --> 23:42.680
Das ist diese Flaschenhals-Eigenschaft.

23:45.220 --> 23:49.720
Und das Überraschende ist, man kann relativ leicht zeigen, wieder eine

23:49.720 --> 23:52.680
schöne Übungsaufgabe, oder vielleicht steht es auch im Buch, ich weiß

23:52.680 --> 23:58.700
nicht genau, wenn ich mir gar nicht den ganzen Graphen angucke,

23:58.800 --> 24:03.020
sondern nur einen Pfad im minimalen Spannbaum suche, der hat ja die

24:03.020 --> 24:07.400
Eigenschaft, es gibt genau einen Pfad zwischen zwei beliebigen Punkten

24:07.400 --> 24:10.960
in diesem minimalen Spannbaum, und der hat gerade diese Bottleneck

24:10.960 --> 24:11.380
-Eigenschaft.

24:11.500 --> 24:14.540
Das ist der optimale Pfad für dieses Optimierungsproblem.

24:15.320 --> 24:19.260
Das ist super, weil wir werden sehen, man kann minimale Spannbäume

24:19.260 --> 24:22.060
sehr schnell berechnen, und das ist dann auch wieder eine

24:22.060 --> 24:25.760
Vorberechnung sogar, und danach kann man die Pfade noch schneller

24:25.760 --> 24:26.300
berechnen.

24:26.400 --> 24:30.200
Man kann dann im Endeffekt in Zeitlinearen der Anzahl Kanten

24:30.200 --> 24:31.660
wahrscheinlich so einen Pfad suchen.

24:32.620 --> 24:34.420
Oder auf jeden Fall in linearer Zeit.

24:37.040 --> 24:40.560
Also das ist eine wichtige Anwendung, und was fast noch wichtiger ist,

24:41.520 --> 24:42.760
ist Clustering.

24:44.800 --> 24:48.120
Also grob, was man da macht, man bestimmt so einen minimalen Spannbaum

24:48.120 --> 24:50.960
und lässt dann einzelne Kanten weg.

24:51.720 --> 24:55.400
Und sagt dann, okay, die verbleibenden Zusammenhangskomponenten, also

24:55.400 --> 24:59.860
dann bleibt ja ein Wald über, und die einzelnen Bäume in dem Wald, die

24:59.860 --> 25:02.560
sind irgendwie stärker miteinander verbunden als der Rest.

25:04.120 --> 25:09.120
Und das ist eine Formulierung eines Clustering-Problems, die man in

25:09.120 --> 25:10.660
sehr vielen Anwendungen verwendet.

25:11.560 --> 25:13.660
Vor allem ist das sowas wie dieses...

25:17.360 --> 25:18.160
wie nennt man das?

25:20.780 --> 25:24.780
Wenn ein Betrunkener irgendwie seinen Schlüssel verloren hat, dann

25:24.780 --> 25:28.700
sucht er halt unter der Straßenlaterne, weil er sagt ja, außerhalb

25:28.700 --> 25:30.760
kann ich den ja sowieso nicht finden, da sehe ich nichts.

25:31.420 --> 25:32.900
Und das ist hier tatsächlich auch so.

25:33.240 --> 25:36.660
Clustering-Probleme sind im Allgemeinen sehr schwierig zu lösen.

25:37.400 --> 25:40.700
Also optimale Lösungen kennt man meistens nur Laufzeiten, die

25:40.700 --> 25:42.780
exponentiell in der Eingabegröße sind.

25:43.660 --> 25:49.720
Aber wenn man die Zielfunktion so verbiegt, dass man daraus ein

25:49.720 --> 25:52.660
minimales Spannbaum-Problem machen kann, dann kann man das schnell

25:52.660 --> 25:53.060
lösen.

25:53.760 --> 25:54.900
Ja, und dann macht man das halt.

25:55.280 --> 25:58.480
Und versucht dann noch irgendwie zu reparieren, falls die Zielfunktion

25:58.480 --> 26:01.440
in Wirklichkeit eine andere ist, um dann trotzdem vernünftige

26:01.440 --> 26:02.420
Ergebnisse zu kriegen.

26:04.740 --> 26:08.960
Also was man dann macht, ist, man lässt dann einfach schwere Kanten

26:08.960 --> 26:10.740
weg und guckt dann, was dann passiert.

26:10.820 --> 26:12.880
Machen wir mal ein ganz einfaches Beispiel hier.

26:14.500 --> 26:20.180
Also hier ist jetzt ein Graph mit vier Kanten, der minimale Spannbaum

26:20.180 --> 26:22.140
ist dieser Pfad hier im Endeffekt.

26:23.760 --> 26:26.380
Der hat ja nicht sehr viele Kanten, da lässt man halt die schwerste

26:26.380 --> 26:27.760
weg, und dann ist das hier das Ding.

26:28.260 --> 26:31.660
Und wenn man dann die zweitschwerste weglässt, zerfällt der halt in

26:31.660 --> 26:33.000
diese beiden Komponenten.

26:33.960 --> 26:38.040
Und das ist eine sinnvolle Lösung, weil eins und zwei sind ja

26:38.040 --> 26:43.320
tatsächlich näher beieinander als die anderen da, die haben ja immer

26:43.320 --> 26:44.500
Mindestabstand sieben.

26:45.600 --> 26:48.580
Und das hat auch was mit diesem Bottleneck-Problem hier zu tun.

26:48.720 --> 26:51.760
Also die Leistungsgarantie, die man durch diese Cluster dann kriegt,

26:51.980 --> 26:56.180
ist, wenn ich alle Kanten bis zu einem bestimmten Gewicht x weglasse,

26:56.180 --> 27:00.200
dann ist der Abstand zwischen den Clustern mindestens x.

27:02.910 --> 27:06.400
Und das ist für einige Anwendungen tatsächlich das, was man haben

27:06.400 --> 27:06.600
will.

27:09.660 --> 27:12.960
Also wir haben uns das zum Beispiel mal angeschaut, minimale

27:12.960 --> 27:15.140
Spannbäume zur Segmentierung von Bildern.

27:17.360 --> 27:22.020
Da muss man dann noch etwas komplexere Regeln entwerfen, welche Kanten

27:22.020 --> 27:25.320
man weglässt, aber kommt dann eigentlich zu sehr guten Lösungen.

27:26.440 --> 27:29.700
Und das ist halt auch eine wichtige Anwendung heutzutage, wenn man

27:29.700 --> 27:33.940
immer mehr Bildverarbeitung macht, immer größere Datenmengen, und man

27:33.940 --> 27:36.220
braucht dafür verlässliche, effiziente Algorithmen.

27:36.760 --> 27:40.720
Und da sind minimale Spannbäume tatsächlich eine der

27:40.720 --> 27:42.060
vielversprechenden Ansätze.

27:43.820 --> 27:48.960
Und dann ist es so, es gibt viele schwierigere Probleme, wo man aus

27:48.960 --> 27:51.780
minimalen Spannbäumen Näherungsprobleme dafür macht.

27:51.780 --> 27:55.300
Zum Beispiel hatte ich eben erwähnt, das Handlungsreisende-Problem,

27:55.380 --> 27:59.200
das war das Problem, ich habe N Orte und will die alle besuchen und

27:59.200 --> 28:00.560
weiß nicht, in welcher Reihenfolge.

28:01.380 --> 28:04.860
Und da kann man zeigen, wenn man einen minimalen Spannbaum berechnet

28:05.640 --> 28:10.420
für diese N Städte, dann kann man daraus eine Tour ableiten, die

28:10.420 --> 28:12.720
höchstens zweimal länger ist als die optimale.

28:13.780 --> 28:16.740
Und das ist nicht besonders toll, also wenn Sie jetzt einem

28:16.740 --> 28:19.700
Handlungsreisenden sagen, du musst doppelt so weit fahren wie die

28:19.700 --> 28:23.600
beste Lösung, dann tippt er sich an den Kopf, das kann ich besser,

28:24.040 --> 28:24.680
sagt er dann.

28:25.440 --> 28:30.580
Aber es gibt dann tatsächlich noch Verfahren, wie man das dann in

28:30.580 --> 28:33.320
Richtung immer besserer Lösungen schieben kann und trotzdem

28:33.320 --> 28:38.060
zwischendurch immer wieder minimale Spannbäume berechnen muss, sodass

28:38.060 --> 28:40.100
das also tatsächlich eine spannende Anwendung ist.

28:41.100 --> 28:46.760
Genauso ein anderes Netzwerkentwurfsproblem, das Steinerbaum-Problem,

28:49.060 --> 28:55.000
das in der Praxis tatsächlich relativ häufig auftaucht, funktioniert

28:55.000 --> 28:59.200
jetzt so, also ich sag das auch nur grob, das ist jetzt nicht

28:59.200 --> 29:03.180
Prüfungsstoff oder sowas, also das war jetzt dieses

29:03.180 --> 29:06.960
Telefonleitungsproblem, Sie haben irgendwie N Häuser und wollen die

29:06.960 --> 29:11.900
mit Telefonleitungen verkabeln, hat jemand eine Idee, warum man da

29:11.900 --> 29:14.420
eigentlich keinen minimalen Spannbaum berechnen will?

29:19.650 --> 29:20.630
Keiner eine Idee?

29:24.990 --> 29:29.970
Mal gucken, ob ich das hier zum Laufen kriege.

29:37.620 --> 29:41.380
Wie war denn, weißt du noch, welches Dings das war?

29:48.200 --> 29:48.720
Ja,

29:53.110 --> 29:56.490
nee, lass mal, das hat jetzt, das ist vielleicht nicht so, also der

29:56.490 --> 29:59.190
Trick ist, das kann ich auch so zeigen, stellen Sie sich vor, Sie

29:59.190 --> 30:04.950
haben in der Ebene, genau, wir machen das hier mit Stühlen, Sie haben,

30:05.070 --> 30:12.570
ein Knoten ist der da, ein Haus ist da, eins ist da, nee, jetzt machen

30:12.570 --> 30:20.350
wir das anders, so, also ein Haus ist das da, eins ist das da und eins

30:20.350 --> 30:23.150
ist das hier, wie würden Sie die verkabeln?

30:24.050 --> 30:29.410
Naja, indem Sie hier einen Knoten machen und dann drei Leitungen

30:29.410 --> 30:36.030
ziehen, das ist kürzer als so und so, können Sie nachrechnen an einem

30:36.030 --> 30:37.110
Stück Papier, wenn Sie wollen.

30:37.770 --> 30:41.610
Also allgemeiner, man kann sogenannte Steinerpunkte verwenden, die

30:41.610 --> 30:49.130
nicht Teil des Eingabegrafen sind, und über die dann Verbindungen

30:49.130 --> 30:50.890
herstellen und kriegt damit bessere Lösungen.

30:50.890 --> 30:54.670
Und der Trick ist jetzt, man kann aber mit Hilfe von minimalen

30:54.670 --> 30:58.050
Spannbäumen wieder Nährungslösungen für das Steinerbaum-Problem

30:58.050 --> 30:59.150
berechnen.

31:00.330 --> 31:04.210
Also da steht mehr drüber bei uns im Buch, in der Folge sind

31:04.210 --> 31:07.010
Grundlagen theoretischer Informatik, werden Sie da auch was mehr

31:07.010 --> 31:08.890
drüber lernen und in Algorithmen 2.

31:09.950 --> 31:11.390
Fragen zu den Anwendungen?

31:15.790 --> 31:21.490
So, das war jetzt die motivierende Einleitung, ich hoffe motivieren,

31:22.470 --> 31:26.690
jetzt geht es wieder zurück zur Mathematik, wie gehe ich da dran,

31:26.790 --> 31:27.890
dieses Problem zu lösen?

31:27.990 --> 31:31.850
Und da ist beim minimalen Spannbaum-Problem tatsächlich so, dass es da

31:31.850 --> 31:35.570
sehr schöne mathematische Eigenschaften gibt, die man ausnutzen kann,

31:37.090 --> 31:41.830
und die sind ganz einfach und klar, und daraus konstruiert man dann

31:41.830 --> 31:45.010
verschiedene Algorithmen, da müssen noch irgendwelche Datenstrukturen

31:45.010 --> 31:48.490
reingebaut werden, und dann kriegt man einen ganzen Zoo von

31:48.490 --> 31:51.550
Algorithmen, die die ein oder anderen Vor- oder Nachteile haben.

31:51.630 --> 31:54.610
Also ein sehr schönes Beispiel für, wie Mathematik und

31:54.610 --> 31:56.510
Algorithmenentwurf da zusammenarbeiten.

31:57.410 --> 32:02.870
Die wichtigste Eigenschaft ist vielleicht die Schnitteigenschaft, ich

32:02.870 --> 32:06.530
schneide den Graphen an irgendeiner Stelle durch, also mathematisch

32:06.530 --> 32:14.150
bedeutet das, ich wähle eine Teilmenge S von Knoten, und trenne diese

32:14.150 --> 32:19.850
Knoten von allen anderen Knoten, ich habe also den Graphen einfach in

32:19.850 --> 32:23.410
zwei Teilmengen von Knoten geteilt, und schaue mir jetzt alle Kanten

32:23.410 --> 32:28.770
an, die zwischen diesen beiden Mengen verlaufen, das nennt man den

32:28.770 --> 32:29.070
Schnitt.

32:30.850 --> 32:33.130
Anders ausgedrückt, das sind auch die Kanten, die man zerschneiden

32:33.130 --> 32:35.950
muss, wenn man den Graphen da wirklich auseinanderreißen will.

32:36.810 --> 32:39.990
Also hier ist jetzt zum Beispiel mal der Schnitt, der zwei vom Rest

32:39.990 --> 32:44.950
trennt, und die Behauptung ist jetzt, wenn man von den zerschnittenen

32:44.950 --> 32:49.350
Kanten die leichteste nimmt, also die mit dem kleinsten Gewicht, dann

32:49.350 --> 32:51.530
kann man die für einen minimalen Spannbaum verwenden.

32:56.130 --> 32:59.950
Also hier wäre das, dieser Schnitt geht hier drüber, der zerschneidet

32:59.950 --> 33:06.370
die Kanten mit Gewicht 5 und 7, das heißt die Kante mit Gewicht 5 kann

33:06.370 --> 33:06.810
ich nehmen.

33:07.250 --> 33:11.330
In dem Fall ist es so, die mit 7 ist auch drin, aber das lässt sich so

33:11.330 --> 33:12.590
lokal nicht sehen.

33:12.590 --> 33:15.670
Da gibt es einen anderen Schnitt, der das bezeugt, das ist nämlich der

33:15.670 --> 33:21.290
da, der 1, 2 von 3, 4 trennt, und da ist die 7 tatsächlich das

33:21.290 --> 33:21.750
leichteste.

33:25.750 --> 33:27.970
Genau, also können wir jetzt auch mal weitermachen.

33:28.910 --> 33:32.870
Diese 2 wird zum Beispiel bezeugt durch diesen Schnitt, aber auch

33:32.870 --> 33:34.850
durch diesen, also da gibt es viele Möglichkeiten.

33:35.090 --> 33:39.370
Es gibt eine exponentielle Zahl von Schnitten, es wäre sicherlich kein

33:39.370 --> 33:43.410
so guter Algorithmus, alle Schnitte zu betrachten und dann die Dinger

33:43.410 --> 33:46.810
da zusammenzunehmen, dann würde es sehr lange dauern.

33:49.450 --> 33:52.010
So, aber beweisen wir erstmal diese Eigenschaft.

33:53.810 --> 33:58.010
Was ich da mache, ist das folgende, ich schaue mir irgendeinen

33:58.010 --> 34:00.070
minimalen Spannbaum T' mal an.

34:05.130 --> 34:09.590
Also ich habe jetzt so eine Menge S festgelegt und den Schnitt, der

34:09.590 --> 34:13.170
dadurch bestimmt wird, den halte ich fest und betrachte irgendeinen

34:13.170 --> 34:14.270
minimalen Spannbaum.

34:14.890 --> 34:19.670
Dann gibt es zwei Fälle, und ich betrachte natürlich diese Kante E,

34:19.810 --> 34:22.050
die die leichteste zerschnittene Kante ist.

34:22.590 --> 34:26.550
Und jetzt gibt es zwei Fälle, entweder E ist sowieso in dem T' drin,

34:26.650 --> 34:27.450
dann bin ich fertig.

34:28.030 --> 34:29.470
Das ist ja genau die Behauptung.

34:30.310 --> 34:36.150
Aber könnte natürlich sein, dass E da nicht drin ist.

34:36.270 --> 34:37.110
Was passiert denn dann?

34:37.850 --> 34:38.930
Jetzt gucke ich mir das mal an.

34:38.930 --> 34:41.770
Also hier ist S, da ist V ohne S.

34:44.530 --> 34:47.190
E ist in dem Schnitt, das heißt, es verbindet diese beiden Dinger.

34:48.570 --> 34:52.930
Und ich interessiere mich jetzt für den Fall, dass in dem T' leider

34:52.930 --> 34:59.230
nicht das E drin ist, sondern eine andere Kante, diese blaue da zum

34:59.230 --> 34:59.570
Beispiel.

35:00.190 --> 35:01.990
Naja, es muss so eine Kante geben.

35:02.690 --> 35:06.430
Weil wenn es überhaupt keine Kante in T' gibt, die durch den Schnitt

35:06.430 --> 35:10.990
geht, dann wäre das überhaupt kein Spannbaum, geschweige denn,

35:11.090 --> 35:11.570
minimaler.

35:11.870 --> 35:15.610
Also es muss so eine Kante geben, vielleicht sogar mehrere.

35:15.790 --> 35:20.470
Ich nehme mir irgendeine und mache jetzt einfach so eine

35:20.470 --> 35:21.390
Austauschoperation.

35:21.630 --> 35:26.650
Ich schmeiße die aus T' raus, dann zerfällt dieser Baum in zwei

35:26.650 --> 35:27.030
Stücke.

35:27.550 --> 35:32.090
Aber was natürlich passiert ist, ich habe hier weiterhin zwei

35:32.090 --> 35:35.770
zusammenhängende Teilbäume, die S und V ohne S verbinden.

35:36.410 --> 35:36.870
Aufspannen.

35:38.250 --> 35:41.850
Und wenn ich jetzt das E da reinschmeiße, also ich habe jetzt

35:41.850 --> 35:44.830
praktisch die blaue durch die rote Kante ersetzt, kriege ich wieder

35:44.830 --> 35:45.690
einen spannenden Baum.

35:46.390 --> 35:49.250
Und außerdem war das hier ja die leichteste Kante, also wird das

35:49.250 --> 35:55.350
Gesamtgewicht von dem Baum leichter oder es bleibt vielleicht gleich,

35:55.450 --> 35:56.650
wenn die gleiches Gewicht haben.

35:57.790 --> 35:59.510
Es folgt jetzt schon was stärkeres.

35:59.670 --> 36:02.930
Also wenn es überhaupt einen anderen minimalen Spannbaum gibt, dann

36:02.930 --> 36:07.010
nur einen, bei dem hier eine Schnittkante mit dem gleichen Gewicht

36:07.010 --> 36:07.210
ist.

36:07.270 --> 36:09.750
Weil sonst hätte ich einen Widerspruch herbeigeführt.

36:09.810 --> 36:12.430
Wir hätten dann einen echt leichteren Spannbaum gebaut.

36:14.210 --> 36:18.910
Und das ist jetzt ein sehr typisches Argument, den man in der

36:18.910 --> 36:22.650
kombinatorischen Optimierung und sowas verwendet, in der diskreten

36:22.650 --> 36:24.890
Mathematik allgemein, so Austauschargumente.

36:25.830 --> 36:29.290
Wir haben irgendwie eine Lösung, verändern da was und können irgendwie

36:29.290 --> 36:32.390
was darüber zeigen, was sich dann an der Gesamtlösung verändert.

36:33.390 --> 36:36.130
Und dann kann man diese Austauschoperationen vielleicht auch

36:36.130 --> 36:38.710
wiederholen und kommt damit zu irgendwelchen Normalformen und so

36:38.710 --> 36:38.950
weiter.

36:39.110 --> 36:43.070
Also ein ganz wichtiger Typ von mathematischem Argument.

36:44.370 --> 36:48.010
Fragen zur Schnitteigenschaft und ihrem Beweis.

36:55.620 --> 36:59.200
Eine komplementäre Eigenschaft ist die Kreiseigenschaft, die sagt uns

36:59.200 --> 37:02.300
nämlich etwas über Kanten, die wir weglassen können.

37:02.300 --> 37:08.040
Wir betrachten einen beliebigen Kreis in dem Graphen und die schwerste

37:08.040 --> 37:08.880
Kante da drauf.

37:09.160 --> 37:13.360
Also in diesem Graphen gibt es diesen Kreis, die Kante hier mit

37:13.360 --> 37:16.540
Gewicht 9 ist die schwerste Kante und wenn ich die einfach weglasse,

37:18.520 --> 37:20.980
zerstöre ich für eine MST-Berechnung nichts.

37:21.260 --> 37:24.700
Also diese Kante benötige ich nicht für einen minimalen Spannbaum.

37:26.000 --> 37:27.020
Kann ich sie auch weglassen.

37:29.240 --> 37:29.800
Beweis.

37:32.360 --> 37:34.200
Und wieder ein Austauschargument.

37:35.340 --> 37:39.700
Also nehmen wir mal an, wir haben hier einen minimalen Spannbaum T',

37:40.280 --> 37:44.480
der diese Kante E', also die schwerste, auf diesem Kreis hier benutzt.

37:46.060 --> 37:47.940
Dann mache ich wieder so einen Austausch.

37:49.240 --> 37:52.420
Ich nehme die einfach raus aus dem minimalen Spannbaum und nehme

37:52.420 --> 37:54.380
irgendeine andere Kante auf dem Kreis.

37:54.380 --> 37:58.200
Dann habe ich wieder einen Spannbaum und der kann nicht schwerer

37:58.200 --> 37:58.860
geworden sein.

38:00.020 --> 38:00.700
Und das war es schon.

38:01.920 --> 38:02.680
Fragen dazu?

38:06.480 --> 38:10.360
Also wir haben jetzt zwei grafentheoretische Eigenschaften, mit denen

38:10.360 --> 38:13.900
wir arbeiten können, mit denen wir konkret Kanten identifizieren, die

38:13.900 --> 38:18.700
wir in den minimalen Spannbaum reintun können und Kanten auch

38:18.700 --> 38:19.700
rausschmeißen können.

38:20.160 --> 38:23.840
Wir werden jetzt auf der Basis Algorithmen entwerfen, die dann

38:23.840 --> 38:27.060
tatsächlich auch einen kompletten minimalen Spannbaum bauen.

38:28.360 --> 38:31.480
Und der erste, den ich Ihnen vorstellen möchte, ist der Jarnik-Priem

38:31.480 --> 38:32.260
-Algorithmus.

38:32.920 --> 38:37.680
Der hat deshalb so einen komplizierten Doppelnamen, weil der von Herrn

38:37.680 --> 38:42.140
Jarnik im Jahr 1930 erfunden wurde, aber leider nur auf Tschechisch

38:42.140 --> 38:46.660
veröffentlicht, sodass der Herr Priem 1957 dann gedacht hätte, er

38:46.660 --> 38:49.080
hätte was Tolles entdeckt, das veröffentlicht.

38:49.680 --> 38:53.460
Man hat dann, glaube ich, auch zehn Jahre lang irgendwie das entweder

38:53.460 --> 38:56.440
ignoriert, dass es das schon gab, oder völlig übersehen und deshalb

38:56.440 --> 39:00.260
heißt er in allen Lehrbüchern der Priem'sche Algorithmus, aber das

39:00.260 --> 39:03.860
entspricht eigentlich nicht den Geflogenheiten der Wissenschaft, man

39:03.860 --> 39:06.660
benennt Algorithmen nach ihren Erfindern und nicht nach den

39:06.660 --> 39:07.380
Zweiterfindern.

39:09.500 --> 39:12.180
Deshalb sollte man ihn den Jarnik-Algorithmus nennen, nur dann würde

39:12.180 --> 39:14.680
keiner mehr wissen, wovon ich rede, und deshalb nenne ich ihn den

39:14.680 --> 39:15.880
Jarnik -Priem-Algorithmus.

39:16.020 --> 39:17.720
Und so machen das auch andere Kollegen.

39:20.560 --> 39:23.940
Also die Idee ist, wir lassen einen Baum langsam wachsen.

39:25.480 --> 39:29.560
Wir starten mit einem einzelnen Knoten, welcher ist eigentlich egal,

39:30.580 --> 39:38.840
S, den wählen wir aus, und wir reden ja hier immer über diese Cut

39:38.840 --> 39:39.340
-Eigenschaft.

39:39.980 --> 39:42.680
Also dieser Algorithmus beruht ausschließlich auf dieser Schnitt

39:42.680 --> 39:46.800
-Eigenschaft, die ja definiert wird durch so eine Knotenmenge Groß-S,

39:46.800 --> 39:50.600
und am Anfang ist das einfach die ein-elementige Menge Klein-S.

39:51.360 --> 39:54.360
Und der Baum ist am Anfang leer, enthält keine Kanten.

39:55.160 --> 40:01.940
So, und jetzt habe ich einfach eine Schleife, n-1 mal, suchen wir eine

40:01.940 --> 40:05.000
Kante, die die Schnitt-Eigenschaft für Groß-S erfüllt.

40:05.280 --> 40:08.200
Also am Anfang ist das die leichteste inzidente Kante von S.

40:09.860 --> 40:12.800
Was ich dann immer mache, ist, ich tue dann...

40:15.960 --> 40:22.320
und hier nehme ich jetzt noch an der OBDA, U ist in S und V ist nicht

40:22.320 --> 40:22.540
drin.

40:24.020 --> 40:29.160
Und dann tue ich den Knoten, der nicht drin ist, zu S dazu, kriege ich

40:29.160 --> 40:34.280
einen neuen Schnitt, und die Kante merke ich mir auch.

40:36.160 --> 40:40.520
Gucken wir uns mal ein Beispiel an, dieser Graph hier, wir fangen mit

40:40.520 --> 40:44.620
A an, der Schnitt, der durch A definiert ist, schneidet hier die

40:44.620 --> 40:46.840
Kanten mit Gewicht 7, 9 und 6.

40:47.460 --> 40:48.960
Aha, 6 ist die leichteste.

40:49.600 --> 40:50.980
Mit der erreiche ich C.

40:51.960 --> 40:54.420
Jetzt wird das reingenommen, dann habe ich jetzt meinen Schnitt halt

40:54.420 --> 40:58.800
definiert durch A und C, geht hier durch, dadurch schneidet die Kanten

40:58.800 --> 41:01.140
mit Gewicht 7, 9, 3 und 4.

41:01.340 --> 41:03.000
Aha, 3 ist die leichteste.

41:03.660 --> 41:04.840
Dann nehme ich die rein.

41:05.920 --> 41:09.260
Dann ist mein Schnitt jetzt definiert durch die Knoten A, B, C.

41:09.920 --> 41:14.360
Das heißt, der geht jetzt hier durch und der durchschneidet die Kanten

41:14.360 --> 41:18.540
mit Gewicht 2, 9 und 4.

41:19.560 --> 41:22.640
Da ist diese 2 das leichteste, und dann ist das hier der minimale

41:22.640 --> 41:23.160
Spannbaum.

41:24.080 --> 41:27.000
Man kann sich überlegen, dass man eigentlich in jedem Schritt, wenn

41:27.000 --> 41:31.200
das ein zusammenhängender Graph ist, auch einen neuen Knoten finden

41:31.200 --> 41:36.740
muss, weil es halt immer außerhalb von S irgendwelche Knoten gibt, die

41:36.740 --> 41:37.760
noch verbunden sind.

41:38.760 --> 41:42.820
Und von den Kanten, die die Dinge erreichen, muss halt eine die

41:42.820 --> 41:43.660
leichteste sein.

41:43.740 --> 41:46.920
Das heißt, man findet immer was, die Schnitteigenschaft sagt einem,

41:47.600 --> 41:50.400
das ist auch tatsächlich eine Kante eines minimalen Spannbaums, also

41:50.400 --> 41:51.940
hat man hier einen korrekten Algorithmus.

41:53.620 --> 41:58.440
Wir müssen uns jetzt eigentlich nur noch überlegen, wie wir das hier

41:58.440 --> 41:59.660
effizient implementieren.

42:04.240 --> 42:07.700
Und jetzt haben Sie hier gleich einen relativ komplizierten Pseudokod,

42:10.020 --> 42:13.060
der ist aber gar nicht so schlimm, weil das ist eigentlich Dijkstra's

42:13.060 --> 42:13.660
Algorithmus.

42:15.000 --> 42:17.840
Tatsächlich ist es so, dass nicht nur Herr Prien diesen Algorithmus

42:17.840 --> 42:19.840
wiederentdeckt hat, sondern Herr Dijkstra auch.

42:20.700 --> 42:27.020
In dem Papier von 1959, in dem er den kürzesten Wege-Algorithmus

42:27.020 --> 42:32.740
entdeckt hat, beschreibt er außerdem noch den Janik-Priem-Algorithmus.

42:32.900 --> 42:35.420
Und er wusste auch nicht, dass Herr Janik und Herr Priem das auch

42:35.420 --> 42:36.480
schon vor ihm gemacht hatten.

42:37.220 --> 42:42.060
Ist der gleiche Algorithmus, nur an den roten Stellen ändere ich ein

42:42.060 --> 42:43.800
bisschen was, und das erkläre ich jetzt.

42:46.240 --> 42:49.260
Und ja gut, Rückgabe ist ein bisschen was anderes, eine Menge von

42:49.260 --> 42:55.640
Kanten hier, statt diesem Distanz-Array und dem Parent-Array, aber

42:55.640 --> 42:57.160
ansonsten ist es das Gleiche.

42:58.780 --> 43:02.060
Der erste Unterschied beim kürzesten Wege-Problem ist der

43:02.060 --> 43:03.580
Startknotenteil der Eingabe.

43:03.860 --> 43:05.620
Hier kann ich den irgendwie beliebig wählen.

43:05.740 --> 43:08.120
Das ist der erste Knoten, der mir vor die Flinte kommt zum Beispiel.

43:08.880 --> 43:13.260
Distanz-Array wird oft unendlich initialisiert, das ist wie beim

43:13.260 --> 43:14.380
kürzesten Wege-Problem.

43:16.320 --> 43:19.480
Parent definiert mir später meinen minimalen Spannbaum.

43:23.360 --> 43:27.020
Und ich mache es aber wie beim Dijkstra-Algorithmus, Parent S gleich

43:27.020 --> 43:29.000
S, Distanz von S gleich 0.

43:29.840 --> 43:35.640
Und übrigens wird es hier so sein, dieser Wert Distanz 0 wird für uns

43:35.640 --> 43:40.700
kodieren, die Tatsache, dass der Knoten in dieser Menge S drin ist.

43:40.840 --> 43:43.820
Also wir haben hier gar keine explizite Repräsentation von S, sondern

43:43.820 --> 43:48.380
wir haben einfach, das ist die Menge der Knoten, deren Distanzwert 0

43:48.380 --> 43:48.760
ist.

43:49.660 --> 43:50.540
Eine Vereinbarung.

43:51.860 --> 43:56.100
Und in der Priority-Queue steht das S halt auch drin, und die

43:56.100 --> 43:58.960
Priorität ist wieder dieser Distanzwert.

44:01.520 --> 44:05.540
Also syntaktisch ist das hier genau das Gleiche wie beim Dijkstra

44:05.540 --> 44:09.540
-Algorithmus, aber was natürlich fast genauso wichtig ist, ist die

44:09.540 --> 44:11.360
Invariante, die wir aufrechterhalten.

44:13.160 --> 44:15.200
Die Invariante ist nämlich...

44:18.080 --> 44:25.440
Also beim Dijkstra-Algorithmus hat uns ja eine Entfernung angekündigt,

44:25.740 --> 44:28.880
eigentlich eine Pfadlänge von S zu dem Knoten V.

44:29.740 --> 44:30.440
Das D von V.

44:31.160 --> 44:36.480
Hier interessiert uns nicht die Entfernung entlang irgendeines Pfades,

44:36.900 --> 44:39.800
sondern die Entfernung zu dem Groß-S.

44:42.560 --> 44:51.720
Also D von V speichert ab, was ist die kürzeste Kante, die V mit dem

44:51.720 --> 44:52.720
Groß -S verbindet.

44:52.860 --> 44:57.660
Also mit irgendeinem Knoten, der bereits durch unseren wachsenden Baum

44:57.660 --> 44:59.480
da aufgespannt ist.

45:00.980 --> 45:04.280
Und dann eben diese Spezialvereinbarung, wenn es schon in Groß-S drin

45:04.280 --> 45:05.340
ist, dann ist das halt 0.

45:06.360 --> 45:08.980
Das ist die Invariante, die wir hier aufrechterhalten, ansonsten der

45:08.980 --> 45:11.960
Algorithmus geht jetzt so weiter, wie wir ihn vom Dijkstra-Algorithmus

45:11.960 --> 45:19.680
kennen, solange es noch Knoten gibt, die ich noch nicht in Groß-S

45:19.680 --> 45:24.340
aufgenommen habe, und die in dieser Schlange Q sind, nehme ich den mit

45:24.340 --> 45:25.460
der kürzesten Entfernung.

45:26.040 --> 45:27.840
Und da brauche ich jetzt diese Invariante.

45:29.780 --> 45:36.000
Weil ich will ja eben die leichteste Kante, die Groß-S, also irgendein

45:36.000 --> 45:39.340
Knoten in Groß-S mit irgendeinem Knoten außerhalb verbindet.

45:40.040 --> 45:43.300
Und das ist genau, da sorgen wir dafür, dass das immer der Fall ist,

45:43.700 --> 45:52.110
und am Anfang ist es tatsächlich der Fall, weil am Anfang mache ich

45:52.110 --> 45:55.390
hier ein bisschen was anderes, dann nehme ich ja dieses Ding mit

45:55.390 --> 45:58.290
Entfernung 0 und da brauche ich gar keine Kanten.

46:00.670 --> 46:02.630
Aber danach passt das dann.

46:03.810 --> 46:08.430
Genau, jetzt nehme ich also den Knoten, den ich mit der kürzesten

46:08.430 --> 46:13.030
Kante verbinden kann, nehme den in Groß-S auf, und zwar indem ich die

46:13.030 --> 46:15.950
Distanz auf 0 setze, und jetzt mache ich wieder so eine Scan-Operation

46:15.950 --> 46:22.390
wie bei Dijkstra, für alle Kanten, die aus U rausgehen, gucke ich mir

46:22.390 --> 46:22.950
die Länge an.

46:23.010 --> 46:24.170
Und hier gibt es jetzt einen Unterschied,

46:27.230 --> 46:30.150
also jetzt finde ich hier eine Kante UV, und dann kann es natürlich

46:30.150 --> 46:33.550
sein, dass V noch gar nicht erreicht war.

46:33.990 --> 46:37.790
Dann ist klar, dann setze ich den Wert auf die Länge dieser Kante und

46:37.790 --> 46:38.530
bin fertig.

46:39.030 --> 46:44.010
Aber es könnte natürlich sein, dass V eine andere Kante irgendwo nach

46:44.010 --> 46:48.550
Groß -S hat, und mich interessiert aber nur die leichteste, und

46:48.550 --> 46:50.710
deshalb mache ich hier diesen Vergleich, wenn das Gewicht von E

46:50.710 --> 46:56.450
kleiner ist als die momentane Entfernung, dann setze ich die momentane

46:56.450 --> 46:57.930
Entfernung auf das Gewicht von E.

46:58.410 --> 47:01.230
Und das war bei Dijkstras Algorithmus ein bisschen anders, da stand

47:01.230 --> 47:05.790
hier nicht C von E, sondern D von U plus C von E.

47:06.890 --> 47:09.410
Damit habe ich eine Pfadlänge ausgerechnet und das hier ist einfach

47:09.410 --> 47:11.090
ein Vergleich von Kantengewichten.

47:11.970 --> 47:14.770
Ansonsten geht es jetzt weiter wie gehabt, ich merke mir diese

47:14.770 --> 47:20.450
Verbindung in dem Parent Array und mache dann, je nachdem ob V bereits

47:20.450 --> 47:23.650
in der Queue drin ist oder nicht, einen Decrease Key oder einen

47:23.650 --> 47:23.990
Insert.

47:25.390 --> 47:29.970
Und ganz am Ende gebe ich einfach zurück die Menge aller Kanten, die

47:29.970 --> 47:34.170
definiert sind durch dieses Parent Array, und da interessiere ich mich

47:34.170 --> 47:37.050
nicht für S, weil Parent von S gleich S, ich will Ihnen nicht diesen

47:37.050 --> 47:38.350
Self -Loop da ausgeben.

47:39.270 --> 47:44.070
Okay, gibt es Fragen zur Erklärung des Janik-Priem-Algorithmus und zur

47:44.070 --> 47:46.310
Implementierung mittels Prioritätslisten?

47:48.870 --> 47:52.190
Jetzt wird mir die rote Karte gezeigt.

47:55.450 --> 47:59.370
Wenn mir noch eine Folie gestattet ist, dann sind wir mit Janik-Priem

47:59.370 --> 47:59.890
fertig.

48:02.590 --> 48:06.670
Analyse, das ist praktisch identisch zur Analyse vom Dijkstra

48:06.670 --> 48:07.270
-Algorithmus.

48:07.270 --> 48:11.810
Wir haben lineare Zeit außerhalb der Prioritätsliste, wir haben N

48:11.810 --> 48:15.770
-Delete -Min-Operationen, die brauchen insgesamt Zeit N log N, wir

48:15.770 --> 48:22.810
brauchen O von M Decrease-Key-Operationen, mit binären Heaps kriegen

48:22.810 --> 48:26.810
wir M plus N log N, mit Fibonacci-Heaps kriegen wir M plus N log N.

48:28.010 --> 48:31.610
Der einzige Unterschied ist hier eigentlich, dass diese

48:31.610 --> 48:35.390
Prioritätslisten nicht monoton sind, das heißt, das Minimum der Liste

48:35.390 --> 48:41.170
geht nicht monoton rauf, wie bei Dijkstras-Algorithmus, für die

48:41.170 --> 48:44.730
Prioritätslisten, die wir uns bisher angeschaut haben, ist das aber

48:44.730 --> 48:45.190
irrelevant.

48:47.290 --> 48:53.230
Für andere spielt das eine Rolle, ist auch eine schöne Übung, warum

48:53.230 --> 48:55.690
reichen hier monotone Prioritätslisten nicht.

48:55.810 --> 48:58.390
Also geben Sie einen Graphen an und einen Startknoten, wo beim Janik

48:58.390 --> 49:01.650
-Priem -Algorithmus das Minimum irgendwie schwanken kann.

49:02.430 --> 49:05.570
Das ist ein guter Punkt, zu übergeben.

49:16.710 --> 49:20.590
Ihr habt jetzt ganz viele Graph-Algorithmen gerade gesehen, wir machen

49:20.590 --> 49:21.950
ein bisschen Graph-Theorie.

49:23.730 --> 49:27.310
Es wird die ganze Zeit von Graphen geredet und es gibt eigentlich eine

49:27.310 --> 49:31.250
ganz große mathematische Disziplin, die heißt Graph-Theorie und davon

49:31.250 --> 49:33.170
möchte ich euch jetzt ein bisschen Einblick geben.

49:33.170 --> 49:36.370
Und das große Problem an Graphen ist, dass jeder eigentlich ein

49:36.370 --> 49:37.830
bisschen was anderes darunter versteht.

49:37.910 --> 49:42.010
Es gibt normale Graphen, einfache Graphen, Graphen mit parallelen

49:42.010 --> 49:46.910
Kanten, Graphen mit Schlingen und Hypergraphen gibt es auch noch.

49:47.170 --> 49:50.170
Das ist so das erste große Problem an Graph-Theorie, dass man erstmal

49:50.170 --> 49:53.230
deklarieren muss, was man eigentlich betrachtet.

49:55.650 --> 49:58.890
Und was ich jetzt in den ersten Folien hier zeigen möchte, ist, dass

49:58.890 --> 50:01.350
Graphen eigentlich etwas sind, was ihr schon kennt.

50:01.350 --> 50:04.350
Das sind nämlich nichts anderes als binäre Relationen.

50:05.270 --> 50:09.750
Ja, eine Relation ist irgendetwas wie gleich, kleinergleich oder

50:09.750 --> 50:13.290
teilt, irgendetwas, was zwei Objekte miteinander in Beziehung setzt.

50:14.270 --> 50:14.830
Mehr ist es nicht.

50:15.850 --> 50:18.710
Und mathematisch schreibt man das dann so ein bisschen komisch mit

50:18.710 --> 50:24.750
einem R dazwischen und R ist einfach dann eine Auswahl aus dem

50:24.750 --> 50:28.410
Kreuzprodukt von zwei und dem Kreuzprodukt einer Menge, was einfach

50:28.410 --> 50:30.430
nur zwei Elemente bedeutet.

50:31.670 --> 50:35.230
Ein Graph, so wie wir ihn kennengelernt haben, ein gerichteter Graph,

50:35.510 --> 50:36.910
ist eigentlich genau das Gleiche.

50:37.970 --> 50:42.010
Ich habe Knoten und die Kanten sind einfach nur die Beziehungen, die

50:42.010 --> 50:43.150
zwischen den Objekten sind.

50:46.330 --> 50:49.030
Ein ungerichteter Graph ist ein bisschen was anderes, der ist ein

50:49.030 --> 50:52.070
bisschen spezieller, weil dort geht es quasi immer hin und her.

50:52.590 --> 50:55.510
Ich habe für jede Relation von dem einen zum anderen auch zurück.

50:55.510 --> 50:59.570
Und was verboten ist in diesen ganzen Darstellungen, sind

50:59.570 --> 51:04.450
Selbstrelationen, also das Objekt ist mit sich selber in Beziehung.

51:05.310 --> 51:07.550
So wie das beispielsweise bei Gleich der Fall wäre.

51:09.450 --> 51:11.870
Okay, jetzt habe ich alle verwirrt, es gibt unheimlich viele

51:11.870 --> 51:13.190
Varianten, das ist das Problem.

51:15.990 --> 51:20.090
Beispielsweise kann man die Teilbarkeit von zwei Zahlen auch als Graph

51:20.090 --> 51:20.650
darstellen.

51:20.650 --> 51:23.710
Das ist immer mein schönstes Beispiel, weil Teilbarkeit habt ihr

51:23.710 --> 51:25.490
irgendwann mal in Mathe bestimmt schon mal gehabt.

51:25.710 --> 51:28.370
Zwei Zahlen teilen sich, wenn man irgendwie was multiplizieren kann

51:28.370 --> 51:29.750
zuerst, dann würde das zweite herauskommen.

51:30.370 --> 51:33.150
Und ich kann jetzt einen Graph daraus machen, indem ich das einfach

51:33.150 --> 51:36.850
als die unterliegende Relation dazu betrachte.

51:38.230 --> 51:42.510
Zwei Zahlen teilen sich, beispielsweise die 1 teilt alle Zahlen,

51:42.850 --> 51:46.770
deswegen geht von der 1 überall hin ein Pfeil, von der 2, die teilt

51:46.770 --> 51:50.450
alle Geraden natürlich, die 3 alle, die mit 3 und 2 und so fort.

51:51.050 --> 51:54.590
Das ist auch ein Graph, aber eigentlich auch eine Relation, nämlich

51:54.590 --> 51:54.990
teilt.

51:58.230 --> 52:00.910
Also das war ein gerichteter Graph, wahrscheinlich der einzige

52:00.910 --> 52:02.490
gerichtete, der hier so vorkommt.

52:03.170 --> 52:07.370
Ein ungerichteter ist beispielsweise der Hyperwürfel hier, und da

52:07.370 --> 52:13.930
nehme ich einfach alle binären Wörter einer gewissen Länge, nämlich 3

52:13.930 --> 52:19.590
hier, und sage, dass zwei binäre Wörter in Relation stehen, wenn sie

52:19.590 --> 52:22.050
sich nur um eine Ziffer, genau eine Ziffer unterscheiden.

52:22.890 --> 52:24.370
Dann bekomme ich so einen Würfel.

52:25.690 --> 52:27.490
Oder auch einen höherdimensionalen Würfel.

52:30.150 --> 52:33.810
Und ja, das ist ein schönes Beispiel, das ist im Prinzip die Hamming

52:33.810 --> 52:36.830
Distanz 1, ich wusste das ein bisschen kompliziert mit XOR schreiben,

52:36.970 --> 52:38.570
aber es unterscheidet sich halt um 1.

52:38.570 --> 52:43.130
Das ist jetzt mal als Beispiel für Graphen, die man eigentlich, also

52:43.130 --> 52:46.010
es wird gerne von irgendwelchen natürlichen Graphen immer gesprochen,

52:46.490 --> 52:49.870
Straßennetzwerk und so weiter, aber ein Graph ist eigentlich nichts

52:49.870 --> 52:53.670
anderes als eine Relation in der Graphentheorie.

52:54.970 --> 52:59.770
Okay, ein bisschen Definitionen, damit wir was haben, worüber wir

52:59.770 --> 53:00.150
reden.

53:00.270 --> 53:03.270
Ihr kennt schon Adjacent, zwei Knoten sind Adjacent, wenn es eine

53:03.270 --> 53:07.970
Kante gibt, aber man sagt, dass eine Kante zu einem Knoten Inzidenz

53:07.970 --> 53:08.190
sind.

53:10.810 --> 53:12.310
Das sind zwei verschiedene Wörter.

53:13.050 --> 53:16.630
Dann braucht man natürlich, dann kann man die Umgebung eines Knotens

53:16.630 --> 53:20.850
quasi sagen, also alle anderen Knoten, die mit dem Adjacent sind, und

53:20.850 --> 53:25.070
die Anzahl der umgebenden Nachbarn ist dann einfach der Knotengrad.

53:27.070 --> 53:28.690
Ist alles irgendwie klar, ja?

53:30.090 --> 53:34.410
Aber es gibt ein ganz schönes erstes Lemma, was doch ein bisschen

53:34.410 --> 53:37.870
überraschend ist, Entschuldigung, kommt gleich.

53:39.030 --> 53:42.150
Es gibt verschiedene, also mit diesem Knoten, dieser Spezifikation

53:42.150 --> 53:46.150
Knotengrad, kann man dann erstmal nochmal spezielle Knoten benennen.

53:46.590 --> 53:49.430
Einfach Knoten, die keine Nachbarn haben, heißen einfach isoliert.

53:50.290 --> 53:53.270
Knoten, die einen Nachbarn haben, das sind Randknoten.

53:55.030 --> 53:59.390
Und wenn man einen Graphen hat, in dem alle Knoten den gleichen Grad

53:59.390 --> 54:02.650
haben, dann sind das auch besondere Graphen, die heißen Knotenregulär.

54:03.430 --> 54:06.350
Zum Beispiel war dieser Hyperwürfel, den wir gerade gesehen haben,

54:07.150 --> 54:10.030
dreiregulär, weil überall drei Kanten rausgehen.

54:10.810 --> 54:16.190
Besondere Eigenschaft, muss man erstmal akzeptieren, die

54:16.190 --> 54:19.710
größtmöglichen Graphs, das sind die vollständigen Graphen, die haben

54:19.710 --> 54:23.870
eben die größtmögliche Knotenregularität, und das sind beispielsweise

54:23.870 --> 54:28.490
die, davon gibt es immer nur einen hier, pro Anzahl von Knoten.

54:29.150 --> 54:30.350
Kann man natürlich fortsetzen.

54:33.950 --> 54:37.050
Einfache Aufgabe ist, man muss sich überlegen, wie viele Kanten gibt

54:37.050 --> 54:37.870
es da jetzt eigentlich drin.

54:40.830 --> 54:43.690
Jetzt kommen wir zu dem Lemma, was ich gerade schon anschneiden

54:43.690 --> 54:43.950
wollte.

54:44.030 --> 54:48.730
Wir haben jetzt den Knotengrad, aber es gibt ein ganz einfaches Lemma,

54:48.850 --> 54:50.430
das aber doch sehr anwendungsreich ist.

54:50.510 --> 54:52.670
Wir werden das zweimal noch brauchen in der Übung.

54:53.230 --> 54:58.050
Und zwar ist einfach die Summe aller Knotengrade konstant in jedem

54:58.050 --> 54:58.950
Graphen 2e.

55:01.070 --> 55:01.630
Warum?

55:02.830 --> 55:04.210
Naja, das ist eigentlich ganz einfach.

55:06.510 --> 55:11.490
Es ist ganz einfach, der Trick ist einfach, jede Kante ist zu genau

55:11.490 --> 55:12.750
zwei Knoten inzident.

55:13.930 --> 55:14.610
Das ist der ganze Trick.

55:15.350 --> 55:19.030
Um das aber mathematisch sauber hinzuschreiben, betrachtet man eine

55:19.030 --> 55:23.750
Menge, nämlich diese hier, und zählt die jetzt auf zwei verschiedene

55:23.750 --> 55:24.810
Arten und Weisen ab.

55:25.710 --> 55:28.610
Nämlich einmal über die Knoten und einmal über die Kanten.

55:30.010 --> 55:36.910
Wenn ich, das erste ist, genau über die Kanten, ich möchte die

55:36.910 --> 55:38.850
Mächtigkeit dieser Menge hier bestimmen.

55:39.890 --> 55:41.930
Und ich betrachte zuerst dieses hier.

55:42.910 --> 55:50.270
Für alle Kanten, die es gibt, fügt jede Kante genau zwei Tupel, zwei

55:50.270 --> 55:51.790
Paare hier in diese Menge ein.

55:52.190 --> 55:53.810
Nämlich da, wo sie beginnt und da, wo sie endet.

55:56.090 --> 55:58.970
Und damit ist diese Menge, die Mächtigkeit dieser Menge, 2e.

56:00.950 --> 56:04.650
Aber auf der anderen Seite können wir auch alle Knoten betrachten.

56:05.270 --> 56:09.230
Und wenn wir alle Knoten betrachten, sehen wir, dass der Knotengrad,

56:12.170 --> 56:16.630
genau, dass für jeden Nachbarn eines Knotens in dieser Menge genauso

56:16.630 --> 56:20.450
viele drin sind, genau ein Paar in dieser Menge hinzukommt.

56:20.550 --> 56:21.910
Und das ist genau der Knotengrad.

56:21.910 --> 56:24.850
Für jeden Nachbarn gibt es ein Paar in dieser Menge.

56:26.610 --> 56:27.790
Und damit ist es wieder 2e.

56:28.910 --> 56:31.850
Beziehungsweise es ist die Summe der Knotengrade.

56:34.670 --> 56:38.170
Und es gibt ein kleines Korollar, was auch ziemlich überraschend ist,

56:38.610 --> 56:42.550
was direkt aus diesem Handshake-Glamour, wie das heißt, folgt, dass

56:42.550 --> 56:48.290
nämlich jeder Graf, egal welcher, eine gerade Anzahl von Knoten mit

56:48.290 --> 56:49.390
ungeradem Grad hat.

56:49.390 --> 56:50.510
Warum?

56:52.390 --> 56:59.290
Nun, man betrachtet quasi diese Gleichung Modulo 2, wenn rechts steht

56:59.290 --> 57:04.310
immer eine gerade Zahl, sprich 0, und links muss daher auch eine

57:04.310 --> 57:05.190
gerade Zahl stehen.

57:07.010 --> 57:11.290
Und wenn man jetzt alle Knoten, die geraden Grad haben, wir fallen

57:11.290 --> 57:15.750
quasi nicht ins Gewicht in dieser Modulogleichung, aber alle Knoten,

57:15.890 --> 57:18.690
die ungeraden Grad haben, brauchen einen Partner, damit es wieder 0

57:18.690 --> 57:18.910
wird.

57:20.130 --> 57:24.650
Und deswegen gibt es eine gerade Anzahl von Knoten, ungeraden Grades

57:24.650 --> 57:26.390
in jedem Grafen.

57:27.390 --> 57:31.550
Eigentlich überraschend, da es doch unheimliche Vielfalt von Grafen

57:31.550 --> 57:31.810
gibt.

57:33.450 --> 57:37.750
Okay, jetzt gibt es wieder mehr Definitionen, die ihr auch alle schon

57:37.750 --> 57:40.130
wahrscheinlich kennt, aber wichtig sind.

57:41.170 --> 57:46.230
Und zwar, was ein Kantenweg ist, beziehungsweise eine Kantenfolge oder

57:46.230 --> 57:47.030
ein Kantenweg.

57:47.030 --> 57:51.230
Und je nachdem, wie kompliziert die Grafen sind, die man betrachtet,

57:51.670 --> 57:54.430
desto genauer muss man spezifizieren, was eigentlich ein Weg ist.

57:55.730 --> 57:59.690
Wenn beispielsweise zwischen zwei Knoten verschiedene Kanten laufen

57:59.690 --> 58:04.230
können, muss man auch diese Kante, die quasi in diesem Weg ist, auch

58:04.230 --> 58:04.850
dazu schreiben.

58:05.870 --> 58:09.450
Deswegen, das ist die maximal komplizierteste Schreibweise, indem man

58:09.450 --> 58:14.750
den Knoten die Kante dieses Weges aufschreibt.

58:15.390 --> 58:19.850
In diesen etwas einfacheren Grafen, die wir hier immer betrachten, in

58:19.850 --> 58:23.670
denen es immer nur eine mögliche Kante zwischen zwei Knoten gibt, kann

58:23.670 --> 58:26.490
man im Prinzip diese Es, die dazwischen stehen, weglassen.

58:26.590 --> 58:30.010
Und dann hat man nur die Knotenspur, nicht nur die Knoten, die man da

58:30.010 --> 58:30.250
hat.

58:30.790 --> 58:33.510
Aber wenn man mehrere Möglichkeiten hätte, müsste man die mit

58:33.510 --> 58:33.970
aufschreiben.

58:37.170 --> 58:41.430
Eine spezielle Benennung gibt es noch, die heißt Knotenpfad, wenn die

58:41.430 --> 58:42.710
ganzen Kanten verschieden sind.

58:44.350 --> 58:48.390
In Englisch heißen die alle Path, und ich weiß nicht, die haben

58:48.390 --> 58:52.990
wahrscheinlich kein anderes Wort für Path, deswegen heißen die Simple

58:52.990 --> 58:53.310
Path.

58:56.610 --> 59:01.370
Und dann gibt es die ganz grundlegende Definition, ein Graf, also zwei

59:01.370 --> 59:03.870
Knoten sind verbindbar, wenn es irgendeinen Weg gibt, und wenn

59:03.870 --> 59:07.830
zwischen allen Paaren von Knoten in dem Grafen immer ein Weg

59:07.830 --> 59:11.610
existiert, dann ist der Connected, beziehungsweise zusammenhängend.

59:11.850 --> 59:16.470
Ganz wichtig, wir betrachten im Prinzip immer gerne zusammenhängende

59:16.470 --> 59:22.350
Sachen, weil man Grafen, die nicht zusammenhängend sind, quasi in die

59:22.350 --> 59:25.090
einzelnen Zusammenhangskomponenten, wie man das nennt, zerlegen kann

59:25.090 --> 59:26.490
und dann die betrachten kann.

59:29.930 --> 59:33.490
Noch mehr Deklarationen, ein Kreis ist das, was ihr euch vorstellt

59:33.490 --> 59:36.430
unter einem Kreis, es ist ein Pfad, der sich schließt, sprich am Ende

59:36.430 --> 59:37.870
sind zwei Knoten zusammen.

59:38.450 --> 59:40.450
Also Anfang und Endknoten sind gleich.

59:42.330 --> 59:46.570
Und jetzt gibt es ganz wichtig, ein Graf, der kreisfrei ist, ist etwas

59:46.570 --> 59:47.290
Besonderes.

59:50.270 --> 59:52.170
Und darauf kommen wir jetzt gleich zu sprechen.

59:53.090 --> 59:55.610
Erstmal, genau, kreisfreie Grafen.

59:56.530 --> 59:58.570
Und zwar kommen wir jetzt auf Bäume.

59:59.730 --> 01:00:03.410
In der Vorlesung waren gerade schon minimale Spannbäume, wir machen

01:00:03.410 --> 01:00:06.370
jetzt erstmal noch einen Exkurs in allgemeine Bäume, aber nicht

01:00:06.370 --> 01:00:09.090
solche, sondern solche.

01:00:10.710 --> 01:00:14.390
Und zwar, was hat das hier jetzt mit Bäumen zu tun, das sieht nach

01:00:14.390 --> 01:00:15.090
Chemie aus.

01:00:15.530 --> 01:00:19.090
Und es ist tatsächlich so, dass die Bäume, so wie wir sie jetzt

01:00:19.090 --> 01:00:22.930
lernen, erfunden wurden, um chemische Formeln zu untersuchen.

01:00:23.590 --> 01:00:29.550
Nämlich, lasst mich nachgucken, 1857 von Herrn Cayley, der hat sich

01:00:29.550 --> 01:00:35.530
für Alkane interessiert, und zwar für lineare, also kreisfreie Alkane,

01:00:35.590 --> 01:00:36.630
azyklische Alkane.

01:00:37.550 --> 01:00:42.010
Und zwar sind da einfach die Knoten in diesem Grafen Atome.

01:00:43.070 --> 01:00:47.750
Und alle Knoten, die Knotengrad 4 haben, sind Kohlenstoffatome, alle

01:00:47.750 --> 01:00:50.410
Knoten, die Knotengrad 1 haben, sind Wasserstoffatome.

01:00:50.950 --> 01:00:54.810
Und die Frage, die ihn jetzt da interessiert hat, ist, wie viele gibt

01:00:54.810 --> 01:00:57.230
es, wenn ich acht Kohlenstoffatome habe?

01:00:58.410 --> 01:01:00.050
Wie viele verschiedene gibt es?

01:01:00.150 --> 01:01:02.050
Und zwar haben die dann auch alle möglichen verschiedenen

01:01:02.050 --> 01:01:03.690
Eigenschaften.

01:01:04.130 --> 01:01:08.790
Zum Beispiel hat auch dieses Molekül acht Kohlenstoffatome hier drin,

01:01:09.150 --> 01:01:10.430
aber in einer anderen Anordnung.

01:01:11.670 --> 01:01:13.810
Und die Frage ist jetzt, wie viele Anordnungen gibt es?

01:01:15.570 --> 01:01:18.610
Deswegen hat er Bäume erfunden und eine ganze Theorie dazu.

01:01:21.350 --> 01:01:25.130
Der wichtigste Satz zu Bäumen ist dieser hier.

01:01:25.130 --> 01:01:32.810
Und zwar sind Bäume, also die Definition von Bäumen ist in jedem Buch

01:01:32.810 --> 01:01:36.050
ein bisschen anders, ist nämlich eins von diesen verschiedenen

01:01:36.050 --> 01:01:38.570
äquivalenten Bedingungen.

01:01:39.470 --> 01:01:43.650
Meine Lieblingsbedingung ist irgendwie die, dass zwischen je zwei

01:01:43.650 --> 01:01:47.370
Knoten es genau einen Pfad irgendwo gibt und keinen zweiten.

01:01:49.610 --> 01:01:53.010
Es gibt aber auch diese ganze Latte von äquivalenten Bedingungen.

01:01:54.010 --> 01:01:59.250
Und eine möchte ich euch davon noch zeigen, wie man die beweist.

01:02:02.570 --> 01:02:07.210
Während ihr das mal lest, ist es eigentlich ziemlich überraschend,

01:02:07.290 --> 01:02:12.110
dass ein einfaches Konstrukt wie ein Baum so viele verschiedene

01:02:12.110 --> 01:02:16.650
äquivalente Eigenschaften hat.

01:02:18.630 --> 01:02:19.950
Das sieht gut aus.

01:02:20.990 --> 01:02:26.350
Okay, Eigenschaft, genau, wir zeigen die erste Eigenschaft, also alle

01:02:26.350 --> 01:02:31.390
will ich natürlich nicht zeigen, aber wie folge ich aus eins, zwei?

01:02:35.730 --> 01:02:41.190
Eins war, dass es von jedem Knoten genau einen Weg zu irgendeinem

01:02:41.190 --> 01:02:41.750
anderen gibt.

01:02:42.310 --> 01:02:44.030
Also die Definition des Baumes.

01:02:44.790 --> 01:02:48.110
Und was ich jetzt zeigen will, ist diese Eigenschaft hier mit dem,

01:02:48.710 --> 01:02:54.670
dass es zusammenhängend ist, und dass es tatsächlich, also das Vertrag

01:02:54.670 --> 01:02:59.290
von E minus die Anzahl der Kanten genau eins weniger sind als die

01:02:59.290 --> 01:03:00.050
Anzahl der Knoten.

01:03:02.370 --> 01:03:03.930
Überraschend, wie zeige ich sowas?

01:03:05.550 --> 01:03:11.370
Und zwar ist es jetzt auch so, grafentheoretische Methode, mit der man

01:03:11.370 --> 01:03:12.870
da arbeitet, macht Induktion.

01:03:16.740 --> 01:03:19.080
Über die Anzahl der Knoten.

01:03:24.470 --> 01:03:28.610
Und zwar ist das natürlich für n gleich eins sehr einfach.

01:03:29.970 --> 01:03:30.510
Induktionsanfang.

01:03:32.830 --> 01:03:36.830
Also was gilt in unserem Grafen G ist die obere Bedingung, diese

01:03:36.830 --> 01:03:38.370
Wegeeigenschaft.

01:03:38.950 --> 01:03:40.970
Die kann man aber irgendwie bei einem Knoten noch nicht wirklich

01:03:40.970 --> 01:03:41.430
verwenden.

01:03:41.870 --> 01:03:43.590
Und zusammenhängend ist dieser eine Knoten auch.

01:03:43.590 --> 01:03:47.350
Das einzige, was wir da testen müssen, ist diese Gleichheit, diese

01:03:47.350 --> 01:03:49.030
Gleichung.

01:03:49.610 --> 01:03:52.890
Der Betrag von E ist in dem Fall natürlich null.

01:03:53.610 --> 01:03:56.350
Und der ist natürlich ein Betrag von V minus eins.

01:03:56.730 --> 01:03:58.310
Sprich, ja, eins minus eins.

01:03:59.450 --> 01:03:59.690
Locker.

01:04:00.610 --> 01:04:01.590
So, und jetzt machen wir einen Induktionsschritt.

01:04:03.230 --> 01:04:07.050
Für alle n größer als eins, also für alle Grafen, die größer als einen

01:04:07.050 --> 01:04:11.350
Knoten haben, wählen wir einfach eine beliebige Kante.

01:04:16.030 --> 01:04:20.770
Wir wählen eine Kante und zerschneiden den Grafen damit.

01:04:23.410 --> 01:04:30.310
Wenn wir eine Kante nehmen und betrachten den Grafen ohne diese Kante.

01:04:35.630 --> 01:04:37.190
Was passiert?

01:04:38.770 --> 01:04:40.710
Dieser Graf zerfällt.

01:04:40.870 --> 01:04:41.850
Das ist ganz wichtig.

01:04:41.850 --> 01:04:48.330
Da in diesem Grafen es nur genau einen Kantenweg von jedem Knoten zu

01:04:48.330 --> 01:04:52.790
jedem anderen Knoten gibt und ich eine Kante rausgenommen habe,

01:04:53.930 --> 01:04:55.850
zerfällt dieser Graf in zwei Teile.

01:04:56.830 --> 01:04:57.090
Immer.

01:04:58.050 --> 01:05:02.190
Das eine kann trivial ein Knoten sein, aber es zerfällt immer in zwei

01:05:02.190 --> 01:05:03.010
Komponenten.

01:05:04.610 --> 01:05:17.770
Also, unser Graf zerfällt in zwei Teile, nämlich in G1 und G2.

01:05:19.050 --> 01:05:23.590
Wir nennen die jetzt Gi, es hat einfach die Knotenmenge Vi und Ei.

01:05:25.070 --> 01:05:28.450
Und jetzt wissen wir noch ein paar Sachen über diese Knotenmengen,

01:05:29.110 --> 01:05:35.890
nämlich, dass wir hatten am Anfang E-Kanten, haben eine entfernt und

01:05:35.890 --> 01:05:38.810
in dem einen oder in dem anderen sind die gelandet.

01:05:46.570 --> 01:05:53.730
Und wir wissen noch weiter, dass die V-Mengen kleiner sind als die

01:05:53.730 --> 01:05:55.170
ursprünglichen Knotenmengen.

01:05:56.970 --> 01:05:58.050
Warum kleiner?

01:05:58.570 --> 01:05:59.650
Ja genau, sind immer kleiner.

01:06:00.090 --> 01:06:00.330
Warum?

01:06:00.510 --> 01:06:08.210
Weil es zerfallen ist und zumindest in Vi, den Graf habe ich irgendwo

01:06:08.210 --> 01:06:08.750
zerschnitten.

01:06:09.610 --> 01:06:11.890
Deswegen landet mindestens ein Knoten auf der anderen Seite.

01:06:13.150 --> 01:06:15.950
Deswegen ist die Knotenmenge von diesen beiden kleiner als V.

01:06:17.390 --> 01:06:20.530
Und damit können wir dann unsere Induktionsvoraussetzung anwenden,

01:06:20.870 --> 01:06:24.210
denn wir können davon ausgehen, dass für kleinere Grafen unsere

01:06:24.210 --> 01:06:24.950
Eigenschaft gilt.

01:06:26.170 --> 01:06:32.930
Also Eigenschaft 2 gilt für die beiden Grafen.

01:06:36.950 --> 01:06:37.630
So,

01:06:40.870 --> 01:06:42.310
und was war denn unsere Eigenschaft 2?

01:06:42.470 --> 01:06:46.810
Das war A, dass es zusammenhängt, Eigenschaft 2,

01:06:49.890 --> 01:06:53.350
und diese Gleichung zwischen Knoten- und Kantenzahl.

01:06:55.770 --> 01:07:00.970
Sprich, wir wissen hier, dass diese Gleichung in diesen beiden Grafen

01:07:00.970 --> 01:07:01.310
gilt.

01:07:07.290 --> 01:07:16.810
Die 1 gleicht nämlich V1-1 und das Gleiche natürlich für den anderen.

01:07:19.590 --> 01:07:21.890
So, und jetzt rechnen wir einfach mal aus, was das I ist.

01:07:26.250 --> 01:07:32.990
Nämlich 1 plus den Teil plus den zweiten Teil.

01:07:35.130 --> 01:07:36.390
Und was kommt dabei heraus?

01:07:36.550 --> 01:07:40.110
Da die V unverändert sind, da ich ja keinen Knoten entfernt habe, ist

01:07:40.110 --> 01:07:44.970
es einfach Betrag von V und es kommt Minus 1 raus, wie man es erwartet

01:07:44.970 --> 01:07:45.250
hat.

01:07:46.270 --> 01:07:48.230
Wir müssen uns noch einen Gedanken machen, dass der wieder

01:07:48.230 --> 01:07:48.490
zusammenhängt.

01:07:50.330 --> 01:07:51.510
Das ist aber klar.

01:07:55.870 --> 01:07:56.830
Und zusammenhängt.

01:07:59.870 --> 01:08:00.810
Damit sind wir fertig.

01:08:08.310 --> 01:08:14.610
Genau, da ich noch viele andere Sachen zu sagen habe, springen wir mal

01:08:14.610 --> 01:08:15.030
zurück.

01:08:17.370 --> 01:08:18.770
Da der Chris auch noch mal drankommt.

01:08:19.330 --> 01:08:21.130
Vielleicht zeige ich euch jetzt keine anderen Äquivalenzen.

01:08:22.410 --> 01:08:24.970
Das werdet ihr, wenn ihr irgendwo mal Grafentheorie ein bisschen

01:08:24.970 --> 01:08:26.190
macht, garantiert mal zeigen.

01:08:27.310 --> 01:08:27.950
Okay.

01:08:29.090 --> 01:08:32.310
Der Herr Cayley hat die ganzen Bäume deswegen untersucht, weil er die

01:08:32.310 --> 01:08:35.350
verschiedenen Anzahl wissen wollte.

01:08:35.450 --> 01:08:40.010
Und es gibt einen unheimlich berühmten Satz, einen richtig tollen

01:08:40.010 --> 01:08:43.830
Satz, nämlich der Satz von Cayley, der sagt, wie viele aufspannenden

01:08:43.830 --> 01:08:46.870
Bäume in dem vollständigen Graf mit N Knoten sind.

01:08:48.030 --> 01:08:50.450
Und das sind einfach N hoch N minus 2.

01:08:52.290 --> 01:08:56.030
Und es gibt unheimlich viele verschiedene Beweise von diesem

01:08:56.030 --> 01:08:59.530
kombinatorischen Ergebnis, weil es einfach oft vorkommt.

01:08:59.990 --> 01:09:03.530
Das sind beispielsweise die ganzen aufspannenden Bäume, die der K4

01:09:03.530 --> 01:09:03.850
hat.

01:09:05.170 --> 01:09:09.410
Wobei die natürlich alle irgendwie, also Rotation wird nicht

01:09:09.410 --> 01:09:10.850
weggeisomorphiert.

01:09:14.550 --> 01:09:14.890
Okay.

01:09:15.790 --> 01:09:22.210
Noch zu einem anderen unheimlich berühmten grafentheoretischen

01:09:22.210 --> 01:09:26.250
Problem, nämlich den Euler-Grafen und den Hamilton'schen Grafen.

01:09:28.290 --> 01:09:33.070
Und zwar ist das auch, also die Euler-Touren sind der Grund, warum es

01:09:33.070 --> 01:09:34.610
überhaupt Grafentheorie gibt.

01:09:35.230 --> 01:09:41.470
Und zwar hat der Herr Euler in 1736 sich überlegt, wie er die

01:09:41.470 --> 01:09:43.090
Königsberger Brücken überqueren wollte.

01:09:43.870 --> 01:09:45.470
Und daraus ist dann die Grafentheorie.

01:09:45.790 --> 01:09:48.070
Das ist der offizielle Startschuss der Grafentheorie.

01:09:48.990 --> 01:09:53.970
Ein Graf, also ein Kantenkreis, die Aufgabe ist, einen Kantenkreis in

01:09:53.970 --> 01:09:57.350
einem Grafen zu finden, der alle Kanten genau einmal besucht.

01:09:58.170 --> 01:09:59.810
Das ist dann ein Euler-Kreis.

01:10:00.970 --> 01:10:06.590
Oder das alternative Problem ist, der Hamilton'sche Kreis, alle Knoten

01:10:06.590 --> 01:10:13.030
mit einem einzigen Zug einmal zu besuchen und keinen Doppelt.

01:10:16.180 --> 01:10:19.480
Das sind die beiden berühmtesten Probleme vielleicht, die es gibt.

01:10:19.920 --> 01:10:24.020
Und das Erstaunliche ist, also ihr könnt mal ein bisschen gucken, ob

01:10:24.020 --> 01:10:26.720
es da irgendeinen gibt drin, einen Euler-Kreis, einen Hamilton-Kreis.

01:10:28.640 --> 01:10:32.620
Das Erstaunliche dabei ist, dass der Euler-Kreis sehr einfach zu

01:10:32.620 --> 01:10:35.060
finden ist und der Hamilton'sche Kreis sehr schwierig ist.

01:10:37.640 --> 01:10:40.160
Obwohl die eigentlich sehr ähnlich aussehen.

01:10:41.040 --> 01:10:42.020
Okay, genug geguckt.

01:10:42.560 --> 01:10:45.800
Ein Graf heißt einfach Eulerisch und Hamiltonisch, wenn es einen Kreis

01:10:45.800 --> 01:10:46.780
solcher Art gibt.

01:10:48.500 --> 01:10:52.700
Also, ich frage jetzt hier nicht rum, ich zeige hier einfach mal was.

01:10:53.220 --> 01:10:56.280
Das ist sowohl Euler- als auch Hamilton-Kreis, weil er alle Knoten

01:10:56.280 --> 01:10:56.740
besucht.

01:10:57.860 --> 01:10:59.540
Ach nee, Quatsch, es ist kein Hamilton-Kreis.

01:10:59.940 --> 01:11:02.720
Es ist kein Hamilton-Kreis, weil er die hier doppelt besucht.

01:11:03.440 --> 01:11:06.020
Aber es ist ein Euler-Kreis, weil er alle Kanten abgelaufen ist.

01:11:06.820 --> 01:11:10.140
Und das ist ein Hamilton-Kreis, weil er alle Knoten hier besucht hat.

01:11:10.800 --> 01:11:11.700
Und da gibt es weder noch.

01:11:14.900 --> 01:11:16.300
Aber das ist nicht so einfach zu sehen.

01:11:17.200 --> 01:11:20.820
Deswegen, ich habe gerade schon verraten, Euler-Kreise sind sehr

01:11:20.820 --> 01:11:26.040
einfach, also berechnungstechnisch sehr einfach, weil es ein ganz

01:11:26.040 --> 01:11:30.660
bestimmtes Kriterium gibt, ihr könnt es jetzt nachher nochmal

01:11:30.660 --> 01:11:34.020
angucken, ich habe euch noch schwierigere Probleme, weil es ein ganz

01:11:34.020 --> 01:11:37.880
konkretes Kriterium gibt, wann ein Graf einen Euler-Kreis enthält.

01:11:38.320 --> 01:11:42.040
Und zwar, wenn er zusammenhängt und alle Knoten gerade sind.

01:11:43.760 --> 01:11:44.240
Erstaunlich.

01:11:45.680 --> 01:11:50.500
Kurzer Beweis, da der Chris auch noch dran kommen will, ganz schneller

01:11:50.500 --> 01:11:53.020
Beweis, und zwar, die eine Richtung ist mega einfach.

01:11:53.120 --> 01:11:56.040
Wenn ich so einen Euler-Kreis habe, dann besucht er jeden Knoten

01:11:56.040 --> 01:11:58.140
zweimal, deswegen muss der Knotengrad zweimal sein.

01:11:58.520 --> 01:12:00.220
Zusammenhängen muss er auch, offensichtlich.

01:12:01.720 --> 01:12:03.320
Etwas schwieriger ist die Rückrichtung.

01:12:04.160 --> 01:12:08.960
Wenn mein Graf so aussieht, wie garantiere ich, dass da ein Euler

01:12:08.960 --> 01:12:09.740
-Kreis drin ist?

01:12:10.400 --> 01:12:12.820
Nun, das geht über ein Maximalitätsargument.

01:12:13.360 --> 01:12:17.460
Ich betrachte einen Kreis maximaler Länge, beziehungsweise im Moment

01:12:17.460 --> 01:12:20.980
erst einen Pfad maximaler Länge, und jetzt zeige ich, dass dieser Pfad

01:12:20.980 --> 01:12:24.100
ein Kreis sein muss, weil ich ihn sonst verlängern kann.

01:12:25.120 --> 01:12:29.500
Auch das ist ziemlich klar, man muss es aber bis ins Detail

01:12:29.500 --> 01:12:32.800
aufdröseln, um einen richtigen grafentheoretischen Beweis zu haben.

01:12:33.320 --> 01:12:36.660
Und zwar nehme ich meinen Kantenpfad maximaler Länge.

01:12:37.180 --> 01:12:38.560
Warum muss das ein Kreis sein?

01:12:38.960 --> 01:12:44.880
Das muss deswegen ein Kreis sein, weil der Endknotengrad ein Grad hat.

01:12:47.420 --> 01:12:54.560
Dieser Endknoten V0 hat gerade ein Grad, aber da es der Endknoten ist,

01:12:54.700 --> 01:13:01.180
ist nur eine Kante von diesem Grad nur eine ungerade Anzahl von Kanten

01:13:01.180 --> 01:13:01.760
verwendet.

01:13:01.760 --> 01:13:05.000
Deswegen kann ich an dieser Stelle meinen Pfad verlängern.

01:13:06.440 --> 01:13:08.960
Das geht nur dann nicht, wenn es ein Kreis ist.

01:13:09.860 --> 01:13:11.060
Das ist das erste Argument.

01:13:11.540 --> 01:13:16.000
Das zweite Argument ist, wenn man so, also ich habe so einen

01:13:16.000 --> 01:13:20.440
Kantenkreis, und der soll maximale Größe haben,

01:13:25.060 --> 01:13:29.700
und wenn der maximale Größe hat, dann umfasst der sämtliche Kanten.

01:13:30.400 --> 01:13:31.520
Warum ist das so?

01:13:32.340 --> 01:13:37.580
Weil wenn das nicht der Fall wäre, dann würde er an einer Stelle einen

01:13:37.580 --> 01:13:42.020
Knoten enthalten, bei dem nicht alle Kanten verwendet werden.

01:13:43.680 --> 01:13:50.640
Da es eine gerade Anzahl von Kanten in diesem Knoten gibt, und einige

01:13:50.640 --> 01:13:53.520
sind nicht verwendet, gibt es mindestens ein Paar, was nicht verwendet

01:13:53.520 --> 01:13:53.720
ist.

01:13:54.380 --> 01:13:58.380
Von diesem Paar kann ich abzweigen und einen anderen Kreis bauen.

01:13:59.700 --> 01:14:01.200
Das ist, was hier auf den Folien draufsteht.

01:14:02.080 --> 01:14:05.080
Und wenn ich diesen Kreis gefunden habe, kann ich den zum

01:14:05.080 --> 01:14:06.460
Ursprünglichen hinzufügen.

01:14:06.840 --> 01:14:09.760
Der wird dadurch größer, weil diese beiden Kanten nicht dabei waren.

01:14:11.200 --> 01:14:16.460
Und das ist wieder ein Widerspruch zur Maximalität, und damit kann man

01:14:16.460 --> 01:14:17.380
einen Größeren finden.

01:14:17.640 --> 01:14:21.140
Damit war der Ursprüngliche schon maximal, sprich, er enthielt alle

01:14:21.140 --> 01:14:22.380
Kanten, weil es maximal ist.

01:14:25.040 --> 01:14:26.660
Du guckst mich so skeptisch an.

01:14:29.940 --> 01:14:32.520
Okay, aber das ist das Argument.

01:14:34.800 --> 01:14:37.980
Ja, könnt ihr euch daheim durchschauen.

01:14:38.700 --> 01:14:41.500
Jetzt ist aber die Schwierigkeit daraus, einen Algorithmus zu bauen.

01:14:46.120 --> 01:14:47.060
Fangen wir mal an.

01:14:47.700 --> 01:14:49.760
Algorithmus bauen, ein Euler-Kreis in meinem.

01:14:51.200 --> 01:14:54.460
Und zwar ist das Problem, ich fange jetzt einfach mal irgendwo an,

01:14:56.300 --> 01:15:01.740
einen Kreis zu bauen, lauf hier lang, lauf da lang, lauf da lang, lauf

01:15:01.740 --> 01:15:05.320
da lang und komme nicht mehr weiter.

01:15:07.720 --> 01:15:08.960
Wie verhindere ich das?

01:15:10.440 --> 01:15:12.740
Im Prinzip denkt man sich, jetzt sei es doch einfach.

01:15:13.720 --> 01:15:14.800
Ich komme doch immer weiter.

01:15:15.280 --> 01:15:16.060
Das ist nicht der Fall.

01:15:18.340 --> 01:15:22.080
Man muss sich ein bisschen ein anderes Argument zurechtlegen, und zwar

01:15:22.080 --> 01:15:29.180
darf man nur Kanten anfügen, also man muss beim Anfügen von Kanten

01:15:29.180 --> 01:15:32.600
Brücken benachteiligen.

01:15:33.460 --> 01:15:34.220
Was ist eine Brücke?

01:15:34.780 --> 01:15:38.900
Eine Brücke ist eine Kante, so dass der Graph zerfällt,

01:15:41.240 --> 01:15:44.500
beziehungsweise eine Komponente mehr danach enthält.

01:15:46.900 --> 01:15:48.460
Wo ist das hier passiert?

01:15:50.200 --> 01:15:54.280
Wenn man hier irgendwie hinzufügt, kann man diese Kanten wegmachen und

01:15:54.280 --> 01:15:56.040
der Graph hängt noch immer zusammen.

01:15:56.620 --> 01:15:57.400
Hier ist es passiert.

01:15:59.080 --> 01:16:01.440
Wenn man die wegmacht, ist dieser Knoten einzeln.

01:16:01.920 --> 01:16:03.560
Aber hier hatte ich keine andere Wahl.

01:16:04.860 --> 01:16:06.380
Also eine Brücke ist sowas.

01:16:06.780 --> 01:16:09.380
Ich habe so einen Graphen hier, einen Knoten hier.

01:16:12.060 --> 01:16:12.880
Das ist eine Brücke.

01:16:14.640 --> 01:16:17.080
Und das hier war eine Brücke, aber es gab keine andere Wahl.

01:16:17.880 --> 01:16:19.040
Und deswegen durfte ich die nehmen.

01:16:19.860 --> 01:16:20.440
Wie geht es weiter?

01:16:23.500 --> 01:16:27.740
Das ist alles okay, weil hier lauter extra Verbindungen sind.

01:16:28.900 --> 01:16:33.000
Hier auch noch, aber dieser letzte war nicht okay, weil der dann hier

01:16:33.000 --> 01:16:35.720
zerfällt und ich hatte die Wahl, einen anderen zu nehmen.

01:16:36.420 --> 01:16:39.680
Und in dem Moment, in dem ich hier jetzt einen anderen nehme, wird das

01:16:39.680 --> 01:16:40.800
Ganze einfach.

01:16:44.940 --> 01:16:46.920
Das ist dieses Brücken-Argument.

01:16:47.220 --> 01:16:49.860
Schwierig nachzuvollziehen, warum das dann korrekt ist.

01:16:55.070 --> 01:16:56.650
Und danach geht es einfach.

01:16:59.950 --> 01:17:01.470
Okay, das mache ich jetzt aber nicht.

01:17:11.930 --> 01:17:13.770
Stattdessen zeige ich euch mal den Algorithmus.

01:17:13.870 --> 01:17:15.010
Den könnt ihr euch daheim angucken.

01:17:16.990 --> 01:17:18.450
Warum das mit den Brücken nicht geht?

01:17:18.530 --> 01:17:22.130
Ja genau, es geht deswegen mit den Brücken nicht, weil du dann wieder

01:17:22.130 --> 01:17:23.310
zurückkommst zu dem Ursprünglichen.

01:17:23.310 --> 01:17:26.010
Weil es einen anderen Weg gibt, dorthin zu kommen.

01:17:26.690 --> 01:17:28.950
Ich glaube, das ist das Grundargument, warum es dann geht.

01:17:30.730 --> 01:17:33.450
Okay, da der Chris auch noch möchte, gebe ich euch noch ein kleines

01:17:33.450 --> 01:17:34.510
Schmankerl hinterher.

01:17:34.910 --> 01:17:37.550
Es gibt noch viel schwierigere Graph-Probleme.

01:17:37.970 --> 01:17:42.370
Ich lade euch mal ein, hier bei diesen Graphen festzustellen, welche

01:17:42.370 --> 01:17:44.050
eigentlich überhaupt gleich sind.

01:17:45.110 --> 01:17:46.310
Wie so Morphs sind.

01:17:48.710 --> 01:17:51.510
Morphie ist auch ein NP-vollständiges Problem, genauso wie die

01:17:51.510 --> 01:17:52.390
Hamilton -Kreise.

01:17:52.390 --> 01:17:56.490
Und die Hamilton-Kreise kennt man eigentlich eher unter dem Namen

01:17:56.490 --> 01:17:59.530
Travelling -Salesman-Problem, aber Travelling-Salesman ist dann die

01:17:59.530 --> 01:18:01.670
gewichtete Version, die noch viel schwieriger ist.

01:18:03.690 --> 01:18:04.610
Viel Spaß beim Finden.

01:18:04.710 --> 01:18:07.630
Ich verrate euch noch, dass es genau fünf Klassen gibt, sprich zwei

01:18:07.630 --> 01:18:10.270
sind, also zwei Paare sind gleich.

01:18:11.250 --> 01:18:12.510
Aber dafür gibt es jetzt keine Punkte.

01:18:13.670 --> 01:18:14.150
Du bist dran.

01:18:25.410 --> 01:18:27.770
So, nachdem ich jetzt noch ca.

01:18:27.810 --> 01:18:32.990
fünf Minuten habe für den Rest der Übung, kommt hier nochmal eine

01:18:32.990 --> 01:18:35.790
kleine Wiederholung von Bellman-Ford, weil das ein relativ wichtiger

01:18:35.790 --> 01:18:36.490
Algorithmus ist.

01:18:36.950 --> 01:18:40.450
Und eigentlich hatte ich vor, noch zwei Anwendungen zu erklären.

01:18:41.110 --> 01:18:43.070
Ich werde wahrscheinlich jetzt nur eine Anwendung erklären und die

01:18:43.070 --> 01:18:44.590
andere werden wir dann im Tutorium machen.

01:18:45.890 --> 01:18:48.550
Okay, also hier ist nochmal der Algorithmus von Bellman-Ford

01:18:48.550 --> 01:18:49.050
aufgezeigt.

01:18:50.550 --> 01:18:54.890
Was der im Wesentlichen macht, ist, der setzt erstmal die Distanz von

01:18:54.890 --> 01:18:56.050
allen Knoten auf unendlich.

01:18:56.410 --> 01:18:57.490
Oder beziehungsweise, was ist das Ziel?

01:18:57.590 --> 01:19:00.790
Wir haben einen Startknoten S und wir wollen den kürzesten Wegebaum

01:19:00.790 --> 01:19:03.190
aufbauen, ausgehend von S.

01:19:03.450 --> 01:19:06.310
Also das heißt zum einen die kürzesten Wegedistanzen von allen Knoten

01:19:06.310 --> 01:19:09.590
im Graphen zu S und zum anderen der Baum, der mir nachher auch die

01:19:09.590 --> 01:19:10.530
kürzesten Wege liefert.

01:19:11.810 --> 01:19:15.790
Jetzt ist das so, das ein Algorithmus, um das zu lösen, ist ja

01:19:15.790 --> 01:19:18.970
Dijkstra, aber Dijkstra kann nicht mit negativen Kantengewichten

01:19:18.970 --> 01:19:19.270
umgehen.

01:19:20.570 --> 01:19:23.370
Beziehungsweise kann das Problem nicht lösen, wenn negative Kreise da

01:19:23.370 --> 01:19:25.170
sind in dem Graphen.

01:19:25.530 --> 01:19:28.510
Deswegen hat Bellman-Ford dann seinen Algorithmus hier aufgestellt und

01:19:28.510 --> 01:19:31.070
der macht im Wesentlichen nichts anderes, als zunächst mal die

01:19:31.070 --> 01:19:34.490
Distanzen alle auf unendlich zu setzen und keiner von den Knoten hat

01:19:34.490 --> 01:19:36.730
einen Elternteil, also einen Vorgänger in dem Baum.

01:19:38.710 --> 01:19:44.350
Dann initialisiert man die Distanz für den Startknoten als 0 und der

01:19:44.350 --> 01:19:51.670
Vaterknoten zu dem Knoten S ist halt der Knoten S selber.

01:19:52.710 --> 01:19:58.470
So, und jetzt iteriert man N-1 mal über alle Kanten drüber und macht

01:19:58.470 --> 01:19:58.970
diesen Relaxierungsschritt.

01:19:59.570 --> 01:20:04.630
Und dieser Relaxierungsschritt sagt im Wesentlichen, für eine Kante UV

01:20:05.490 --> 01:20:12.050
setzt man die Distanz neu, wenn die kürzeste Wegedistanz die aktuelle

01:20:12.050 --> 01:20:15.610
zu U plus das Kantengewicht kleiner ist als die kürzeste Wegedistanz

01:20:15.610 --> 01:20:15.910
zu V.

01:20:16.010 --> 01:20:19.050
Also wenn ich quasi einen kürzeren Weg zu V gesetzt habe, dann setze

01:20:19.050 --> 01:20:22.770
ich die kürzeste Wegedistanz hier drüben neu und dann setze ich auch

01:20:22.770 --> 01:20:23.770
den Vater entsprechend.

01:20:27.990 --> 01:20:31.450
Das zeigt im Wesentlichen nochmal, warum das korrekt ist.

01:20:31.450 --> 01:20:35.610
Ganz kurz, also hier, was wir ja machen ist, wir relaxieren alle

01:20:35.610 --> 01:20:38.210
Kanten in einer beliebigen Reihenfolge genau N-1 mal.

01:20:39.150 --> 01:20:43.590
Und wenn man sich jetzt nochmal überlegt, dass ein kürzester Weg in

01:20:43.590 --> 01:20:47.410
diesem Graphen höchstens N-1 Kanten haben kann, weil ich sonst halt

01:20:47.410 --> 01:20:54.090
eine Kante, einen Knoten mehrfach betrachte, dann gilt insbesondere,

01:20:54.370 --> 01:20:59.730
dass jeder kürzeste Pfad eine Teilfolge dieser Relaxierungen ist.

01:21:01.230 --> 01:21:05.330
Und jetzt schaue ich mir diesen kürzesten Pfad an, in diesem Bild

01:21:05.330 --> 01:21:09.990
hier, das ist also der stärkste Knoten V, V1, über V2, V3 und so

01:21:09.990 --> 01:21:12.570
weiter bis Vk, das ist dieser kürzeste Pfad bis Vk.

01:21:14.750 --> 01:21:19.010
Und die Kanten hier, das sind jeweils die Kanten E1, E2, E3 und so

01:21:19.010 --> 01:21:19.250
weiter.

01:21:20.190 --> 01:21:24.390
Und dadurch, dass ich wirklich jede Kante N-1 mal relaxiere, kriege

01:21:24.390 --> 01:21:27.010
ich dann nachher insgesamt den kürzesten Weg, weil in irgendeiner Art

01:21:27.010 --> 01:21:34.290
und Weise relaxiere ich diese Kanten und kriege dann nach der ersten

01:21:34.290 --> 01:21:39.050
Runde die kürzesten Wege der Länge 1, nach der zweiten Runde die

01:21:39.050 --> 01:21:43.670
kürzesten Wege der Länge 2 und kriege dann eine Art Invariante, dass

01:21:43.670 --> 01:21:51.190
ich in jeder Iteration kürzeste Wege der Länge K kriege, also die K

01:21:51.190 --> 01:21:51.850
-Kanten haben.

01:21:52.570 --> 01:21:52.870
Gut,

01:21:55.930 --> 01:21:59.630
die Korrektheit lasse ich jetzt mal aus Zeitgründen weg.

01:22:00.610 --> 01:22:04.930
Was ganz interessant ist an diesem Algorithmus ist, dass man dadurch

01:22:04.930 --> 01:22:06.730
auch negative Kreise im Graphen finden kann.

01:22:07.450 --> 01:22:15.030
Also wenn der Graph negative Kreise enthält, dann ist der Bellman-Ford

01:22:15.030 --> 01:22:20.570
-Algorithmus eine Möglichkeit, um diese negativen Kreise zu finden und

01:22:20.570 --> 01:22:23.490
ein negativer Kreis ist also nichts anderes als ein gerichteter Kreis

01:22:23.490 --> 01:22:24.210
mit Gewicht 0.

01:22:25.150 --> 01:22:28.650
Wenn man von ungerichteten Kreisen spricht, dann bringt einem dieser

01:22:28.650 --> 01:22:31.370
Algorithmus vom Bellman-Ford nicht mehr so viel und es wird ein viel,

01:22:31.470 --> 01:22:33.870
viel schwierigeres Problem, zumindest was die Algorithmik angeht

01:22:33.870 --> 01:22:34.530
hinter dem Problem.

01:22:36.450 --> 01:22:39.230
Dennoch kann man den Algorithmus hier zum Finden von negativen Kreisen

01:22:39.230 --> 01:22:39.890
verwenden.

01:22:46.150 --> 01:22:50.350
Das machen wir im Wesentlichen auf dem Übungsblatt, also auf dem

01:22:50.350 --> 01:22:53.750
Übungsblatt, Aufgabe 1 diese Woche gibt es eine Aufgabe, wo man dann

01:22:53.750 --> 01:22:58.770
einen Algorithmus angibt, um einen negativen Kreis auszugeben.

01:23:00.330 --> 01:23:03.070
Also das Ziel ist, den Algorithmus von Bellman-Ford so zu

01:23:03.070 --> 01:23:05.590
modifizieren, um nachher wirklich einen negativen Kreis auszugeben.

01:23:08.190 --> 01:23:14.630
Ein kleiner Tipp, den wir da geben möchten ist, also dieser

01:23:14.630 --> 01:23:19.270
Algorithmus von Bellman-Ford startet ja von einem Knoten S und man

01:23:19.270 --> 01:23:23.710
kann sich vorstellen, also genau, initial sind alle Distanzen in

01:23:23.710 --> 01:23:27.450
dieser rechten Komponente hier auf unendlich gesetzt und dadurch, dass

01:23:27.450 --> 01:23:31.850
ich diese Relaxierungen nur auf Kanten durchführe, bleiben die

01:23:31.850 --> 01:23:35.470
Distanzen hier drüben auf unendlich gesetzt und ich finde nachher auch

01:23:35.470 --> 01:23:37.310
keinen negativen Kreis, ich komme da überhaupt nicht an.

01:23:38.090 --> 01:23:42.390
Deswegen, was man macht, um negative Kreise zu finden, das ist aber

01:23:42.390 --> 01:23:47.910
noch nicht, wie man das ausgibt, man fügt einen Hilfsknoten H ein und

01:23:47.910 --> 01:23:53.290
verbindet H mit allen Knoten in diesem Graphen und setzt das Gewicht

01:23:53.290 --> 01:23:56.450
von diesen Kanten auf 0 und hat damit dieses Erreichbarkeitsproblem

01:23:56.450 --> 01:24:02.490
gelöst.

01:24:02.490 --> 01:24:06.870
Also wenn ich diesen Knoten H hier einfüge und dieses Kantengewicht 0

01:24:06.870 --> 01:24:10.790
setze, dann kann ich jeden negativen Kreis in diesem Graph finden und

01:24:10.790 --> 01:24:14.350
insbesondere die Fragestellung, gegeben ein gerichteter Graph mit

01:24:14.350 --> 01:24:17.870
positiven und negativen Kantengewichten, gib einen negativen Kreis

01:24:17.870 --> 01:24:18.150
aus.

01:24:20.150 --> 01:24:24.030
Und hier ist ein Kriterium für diese negativen Kreise, also die

01:24:24.030 --> 01:24:29.230
Korrektheit sagt uns ja, dass ich nach N-1-Iterationen alle kürzesten

01:24:29.230 --> 01:24:32.630
Wege gefunden habe und insbesondere, dass wenn ich auf einem kürzesten

01:24:32.630 --> 01:24:36.390
Pfad bin oder wenn ein kürzester Pfad existiert, dass die Kanten sich

01:24:36.390 --> 01:24:37.330
nicht mehr relaxieren lassen.

01:24:37.610 --> 01:24:39.350
Also ich kann keine kürzeren Wege mehr finden.

01:24:40.210 --> 01:24:44.030
Und das heißt, wenn ich einen negativen Kreis habe, C, dann existiert

01:24:44.030 --> 01:24:47.270
eine Kante in diesem Kreis, sodass ich die noch relaxieren kann und

01:24:47.270 --> 01:24:50.170
das ist vielleicht ein guter Startpunkt, um nachher tatsächlich einen

01:24:50.170 --> 01:24:51.370
negativen Kreis auszugeben.

01:24:53.710 --> 01:24:56.450
Genau, also habe ich eben schon gesagt, das ist Teil von der Übung,

01:24:56.610 --> 01:24:57.370
also vom Übungsblatt.

01:25:00.530 --> 01:25:02.090
Genau, das lasse ich jetzt aber auch weg.