WEBVTT 00:01.350 --> 00:06.840 Also für das Fakultätsfest mache ich natürlich mit Reklame. 00:09.400 --> 00:11.900 Für die Demo mache ich es weniger. 00:16.530 --> 00:17.530 Geht's jetzt? 00:19.710 --> 00:26.050 So, wir sind leider am Montag so mittendrin hängen geblieben bei 00:26.050 --> 00:30.750 diesem Algorithmus, bei dem es darum geht, die kürzesten Wege zu 00:30.750 --> 00:31.330 konstruieren. 00:31.330 --> 00:35.010 Wir geben uns einen Knoten vor in einem Graphen und versuchen jetzt 00:35.010 --> 00:39.490 rauszukriegen, zu jedem verbleibenden Knoten, aus allen restlichen 00:39.490 --> 00:42.250 Knoten, jeweils die kürzesten Wege zu konstruieren. 00:43.210 --> 00:45.250 Das geht immer eigentlich rekursiv vor sich. 00:46.050 --> 00:51.750 Ich marschiere los, hole mir zunächst mal die Knoten, die ich direkt 00:51.750 --> 00:56.810 erreichen kann, bestimme jeweils, welches der kürzeste Weg zu diesen 00:56.810 --> 00:57.630 Knoten ist. 00:57.630 --> 01:02.430 Das ist klar, das ist, wenn mehrere Pfade existieren, dann der jeweils 01:02.430 --> 01:03.010 der kürzeste. 01:03.970 --> 01:08.310 Wenn ich das geschafft habe, verlängere ich die allerkürzesten Pfade 01:08.310 --> 01:13.270 wiederum um genau eine Kante und muss dann wieder prüfen, falls der 01:13.270 --> 01:16.430 gleiche Knoten über mehrere Pfade erreicht wird, welches davon der 01:16.430 --> 01:20.390 kürzeste ist und so lange, bis ich schließlich alle Knoten erreicht 01:20.390 --> 01:20.770 habe. 01:21.550 --> 01:26.030 So, und da steht eigentlich auch in diesem Algorithmus drin, das ist 01:26.030 --> 01:27.790 also der berühmte von Dijkstra. 01:29.230 --> 01:31.930 Bei dem, wie wir sehen, bearbeiten wir wieder Markierung. 01:33.330 --> 01:37.070 Und wir betrachten zunächst mal, markieren wir alle Knoten als 01:37.070 --> 01:37.730 unbesucht. 01:42.950 --> 01:46.290 Jetzt kommt so ein üblicher Programmiertrick. 01:46.970 --> 01:51.130 Wir setzen für unseren eigenen Knoten, von dem wir aus starten, die 01:51.130 --> 01:53.650 Länge des kürzesten Pfades natürlich gleich 0. 01:55.830 --> 02:00.070 Und für alle anderen setzen wir sie auf unendlich. 02:00.430 --> 02:04.290 Da sehen wir schon, die Überlegung ist immer, wir suchen nach einem 02:04.290 --> 02:07.770 Minimum, das heißt, wenn wir einen kürzeren Pfad finden, dann wird der 02:07.770 --> 02:11.230 an die Stelle des bisherigen Wertes für länger eingetragen. 02:12.530 --> 02:15.850 So, und jetzt brauchen wir nur so lange vorzugehen, als noch nicht 02:15.850 --> 02:18.110 besuchte Knoten existieren. 02:20.090 --> 02:22.930 Das heißt, wenn wir alle Knoten besucht haben, dann sind wir fertig. 02:24.170 --> 02:29.350 So, wir wählen unter diesen Knoten den Knoten, dessen Länge minimal 02:29.350 --> 02:29.910 ist. 02:30.170 --> 02:33.610 Das heißt, wir sind an einem Knoten angelangt und versuchen jetzt, für 02:33.610 --> 02:40.270 jeden noch nicht besuchten Knoten rauszukriegen, denjenigen Knoten, 02:40.470 --> 02:44.470 der mit minimaler Länge erreichbar, der minimal im Augenblick ist, 02:45.090 --> 02:47.870 markieren den als besucht und jetzt marschieren wir los 02:51.310 --> 02:56.970 und ergreifen uns den Knoten heraus, die nächsten Knoten, die wir über 02:56.970 --> 02:58.570 eine zusätzliche Kante erreichen. 02:59.790 --> 03:03.310 Hier diese Entscheidung an dieser Stelle besagt einfach, ich nehme mal 03:03.310 --> 03:06.810 alle Knoten, die noch nicht besucht sind, die haben ja alle im 03:06.810 --> 03:12.370 Augenblick eine Angabe über die Länge, möglicherweise unendlich, und 03:12.370 --> 03:17.250 da möglicherweise für den selbst auch mehrere Längen existieren, nehme 03:17.250 --> 03:18.830 ich zunächst mal die kürzeste Länge. 03:20.610 --> 03:23.670 Dann bin ich auch mit dem Knoten fertig und kann den Folgeknoten 03:23.670 --> 03:24.110 übergehen. 03:24.670 --> 03:29.970 So, bei den Folgeknoten, die ich erreiche, muss ich mal prüfen, ist 03:29.970 --> 03:33.090 die Länge, die ich auf die Art erreiche, kürzer als die mir bisher 03:33.090 --> 03:34.870 bekannte kürzeste Länge? 03:35.330 --> 03:42.510 Wenn ja, dann wird das neue Minimum eingetragen, sonst wird einfach 03:43.980 --> 03:46.880 ignoriert, dann ergibt es offenbar schon einen kürzeren Pfad. 03:48.460 --> 03:51.020 Das ist eigentlich hier die anschauliche Lösung. 03:52.520 --> 03:58.700 Nehmen wir also an, den Knoten Z hätten wir schon mal erreicht. 04:00.980 --> 04:02.460 Er ist aber noch nicht markiert. 04:02.540 --> 04:04.300 Markiert ist er erst, wenn wir von ihm weitergehen. 04:04.800 --> 04:07.080 Und wir haben einen weiteren Knoten W. 04:08.880 --> 04:10.900 Und wir finden eine Kante von W nach Z. 04:11.200 --> 04:16.900 Dann erhebt sich die Frage, ob der blaue Pfad plus die schwarze Kante 04:16.900 --> 04:21.160 kürzer ist, als der bisher kürzeste Pfad zu Z, nämlich der rote. 04:21.940 --> 04:24.820 Und wenn das der Fall ist, dann tragen wir eben als neuen kürzesten 04:24.820 --> 04:29.840 Pfad die Länge von V nach W plus die Länge von W nach Z ein. 04:30.200 --> 04:32.920 Also die Frage ist, ist das kleiner oder nicht? 04:32.920 --> 04:38.100 Wenn ja, dann tritt genau diese Situation hier ein. 04:40.660 --> 04:43.660 So, und jetzt nehmen wir einen Beispielgraf und exerzieren das einfach 04:43.660 --> 04:44.380 mal an dem durch. 04:47.160 --> 04:51.400 Der Ausgangsknoten ist offensichtlich der rot markierte V. 04:52.940 --> 04:56.200 So, der erste Schritt besteht ja darin, dass wir V als besucht 04:56.200 --> 04:56.880 markieren. 04:57.060 --> 05:00.160 Das heißt, wir werden V kein neues Mal aufsuchen. 05:01.440 --> 05:09.580 So, und jetzt gehen wir los und besuchen zunächst einmal unter den 05:09.580 --> 05:14.200 Knoten, die da noch nicht besucht worden sind, sind ja alle anderen, 05:14.900 --> 05:19.800 denjenigen, für den die Länge minimal ist. 05:20.960 --> 05:24.220 Jetzt müssen wir bedenken, wir haben bei allen Knoten im Augenblick 05:24.220 --> 05:27.040 die Länge unendlich eingetragen. 05:28.040 --> 05:30.860 Also unterscheiden die sich in nichts voneinander. 05:31.360 --> 05:33.380 Das heißt, jeder Knoten kommt zunächst einmal in Frage. 05:37.080 --> 05:42.120 So, also greifen wir einen heraus, markieren den als besucht und 05:42.120 --> 05:43.880 wählen dann... 05:44.600 --> 05:48.120 Das heißt, wir wählen also erstmal überhaupt das V, richtig, V hat 0. 05:48.580 --> 05:51.220 Wir wählen also jetzt V als ersten Knoten aus. 05:52.580 --> 05:55.820 Wir markieren ihn als besucht, das heißt, erst jetzt wird er als 05:55.820 --> 05:59.600 markiert besucht, nachdem wir an der zweiten Stelle angekommen sind. 06:00.200 --> 06:05.140 Und jetzt versuchen wir alle Kanten, die zu unmarkierten Knoten 06:05.140 --> 06:05.460 führen. 06:05.640 --> 06:08.020 Das ist in dem Fall A und B. 06:09.200 --> 06:12.780 A und B sind also Knoten, die wir unmittelbar über Kanten erreichen 06:12.780 --> 06:13.120 können. 06:13.940 --> 06:17.200 So, also ist der erste Schritt daher, dass wir zunächst einmal 06:17.200 --> 06:21.640 beginnen mit Länge V gleich 0, das war unser erster Schritt. 06:22.440 --> 06:26.680 Und dann kommen als nächstes zunächst einmal die Knoten in Frage, die 06:26.680 --> 06:29.640 direkt erreichbar sind, über Kanten, das ist Länge A, das ist der 06:29.640 --> 06:30.960 Knoten A und der Knoten B. 06:31.320 --> 06:34.040 Also können wir sagen, die Länge, die wir augenblicklich kennen, die 06:34.040 --> 06:42.160 kürzeste Länge von V zu A ist 5 und zu B ist 12, so wie das auch da 06:42.160 --> 06:42.500 steht. 06:44.460 --> 06:46.840 So, jetzt sind wir bei A und B angelangt. 06:46.840 --> 06:51.540 Und jetzt lautet der nächste Schritt wieder, wir gehen erneut durch 06:51.540 --> 06:52.100 die Schleife. 06:52.200 --> 06:56.560 Die Schleife sagt, greife wieder den Knoten mit dem kürzesten Gewicht, 06:56.640 --> 06:58.020 also mit der kürzesten Länge auf. 06:58.400 --> 07:01.400 Das ist offensichtlich A an dieser Stelle. 07:03.180 --> 07:09.280 So, jetzt markieren wir den als besucht und das heißt zudem werden wir 07:09.280 --> 07:10.220 nie mehr zurückkehren. 07:11.460 --> 07:14.880 Und wir gehen von A aus jetzt wieder mit Kanten weiter. 07:14.880 --> 07:21.800 Und die Kanten, die in Frage kommen von A, wie wir sehen, ist 3 zu C 07:21.800 --> 07:25.500 mit dem Gewicht 3 und zu D mit dem Gewicht 8. 07:26.040 --> 07:30.920 Also nächster Schritt besteht jetzt darin, dass wir neben V auch A 07:30.920 --> 07:32.380 markieren, gerade gesagt. 07:33.400 --> 07:39.460 Wir berechnen jetzt die Länge von unserem Ausgangsknoten V zu C, das 07:39.460 --> 07:45.360 ist 5, die bisherige kürzeste Länge und 3 ist kleiner als unendlich, 07:45.460 --> 07:46.780 das ist ja der Vergleich den wir durchführen. 07:46.920 --> 07:51.400 Also haben wir eine neue kürzte Länge zum Knoten C bestimmt und die 07:51.400 --> 07:55.060 Länge ist dann 8 und das gleiche machen wir mit D, ergibt sich Länge 07:55.060 --> 07:55.500 13. 07:56.640 --> 07:59.380 So, wir haben jetzt an dieser Stelle also folgende Situation. 08:00.080 --> 08:05.800 V und A sind markiert und wir haben als neue Längen eingetragen die 08:05.800 --> 08:07.340 Länge von C und die Länge von D. 08:09.300 --> 08:12.880 Und natürlich auch noch die Länge von A, aber da A markiert ist, kommt 08:12.880 --> 08:13.640 es nicht mehr in Frage. 08:14.360 --> 08:16.360 Also ist der nächste Schritt jetzt, wen wählen wir aus? 08:16.460 --> 08:20.840 Wir wählen aus wiederum denjenigen Knoten, der bisher die kürzeste 08:20.840 --> 08:26.340 Länge von V aus- und aufweist und das ist offensichtlich der Knoten C. 08:26.340 --> 08:27.600 Entschuldigung, der Knoten C. 08:28.900 --> 08:31.140 So, also setzen wir als nächstes an C an. 08:32.900 --> 08:36.820 C bedeutet also hier, wir markieren das C und jetzt gehen wir von C 08:36.820 --> 08:37.480 aus weiter. 08:38.240 --> 08:43.340 Und von C aus haben wir wieder zwei Kanten zur Verfügung, nämlich der 08:43.340 --> 08:48.260 Übergang zu B mit der Länge 2 und der Übergang zu D mit der Länge 4. 08:48.940 --> 08:50.400 Also führen wir das durch. 08:51.160 --> 08:54.640 Wir gehen von 8 plus 2 ergibt 10. 08:55.760 --> 08:58.260 Und wir kennen ja schon die Länge von B, die kennen wir nämlich hier, 08:58.360 --> 08:58.940 die ist 12. 08:59.960 --> 09:02.640 Also ist der neue Wert 10 kleiner als 12. 09:03.040 --> 09:07.500 Also tragen wir jetzt als neue kürzeste Länge B, die Länge für B, 10 09:07.500 --> 09:07.820 ein. 09:08.360 --> 09:09.600 Und das gleiche machen wir für D. 09:11.300 --> 09:13.780 Bei D ist das 8 plus 4. 09:14.280 --> 09:16.320 Richtig, da haben wir auch D schon 13. 09:16.320 --> 09:20.340 8 plus 4 ist 12, ist kleiner 13, also wird die neue Länge 12. 09:20.660 --> 09:23.680 Und natürlich, was wir noch nebenbei tun sollten, ist immer 09:23.680 --> 09:25.540 registrieren, wie wir dort hingekommen sind. 09:26.140 --> 09:28.440 Das spielt jetzt im Augenblick noch keine Rolle, wird aber später eine 09:28.440 --> 09:28.920 Rolle spielen. 09:30.380 --> 09:31.960 So, der letzte Schritt ist klar. 09:32.740 --> 09:36.060 Wir sind jetzt bei B angelangt als demjenigen, der die kleinste Länge 09:36.060 --> 09:37.700 aufweist und noch nicht besucht ist. 09:38.540 --> 09:40.200 Wir markieren in Folge dessen das B. 09:41.640 --> 09:46.080 Und von B geht nur noch eine Kante aus, die wir noch nicht besucht 09:46.080 --> 09:48.480 haben, nämlich die Kante zu D. 09:49.220 --> 09:51.640 Also fügen wir die hinzu, die ist 11. 09:51.760 --> 09:54.480 Und die ist kleiner als diejenige, die wir bisher berechnet haben. 09:55.220 --> 09:56.740 Also ist die kürzeste Länge 11. 09:57.300 --> 10:01.380 Und jetzt müssen wir uns immer im Kopf behalten, wie sind wir da 10:01.380 --> 10:01.840 hingekommen. 10:02.820 --> 10:07.740 So, aber damit haben wir jetzt die Länge D. 10:07.740 --> 10:10.260 Und jetzt haben wir alle Knoten besucht, ist keine übrig geblieben, 10:10.320 --> 10:11.000 sind alle fertig. 10:13.660 --> 10:16.640 So, und jetzt können wir auch sagen, wenn wir uns nochmal ansehen, wie 10:16.640 --> 10:20.260 wir da diese Schritte vollzogen haben, dann sehen wir, wir haben 10:20.260 --> 10:22.300 zunächst einmal diesen Schritt getan. 10:22.920 --> 10:24.280 Dann haben wir den hier getan. 10:25.720 --> 10:28.580 Dann haben wir den hier getan. 10:28.940 --> 10:29.960 Und schließlich diesen letzten. 10:31.560 --> 10:32.900 Das hätte übrigens weg gehört hier. 10:34.180 --> 10:38.840 So, und wir sehen jetzt, dass der Durchlauf zu den kürzesten Pfaden 10:38.840 --> 10:43.040 sogar an dieser Stelle ein entarteter Baum ist, nämlich das ist 10:43.040 --> 10:47.840 einfach ein linearer Pfad, der von V nach A, nach C, nach B und dann 10:47.840 --> 10:48.520 nach D führt. 10:49.300 --> 10:50.040 Das muss nicht sein. 10:50.460 --> 10:52.280 Normalerweise wird da irgendein Baum rauskommen. 10:53.700 --> 10:56.220 Übrigens kann man sich auch die Frage stellen, kommt da eigentlich ein 10:56.220 --> 10:57.960 Baum raus oder kommt da ein Graf raus? 10:59.500 --> 11:00.720 Also hier ist es ja einfach. 11:00.980 --> 11:05.040 Hier kommt zufällig eine reine lineare Folge, also ein Pfad heraus. 11:05.200 --> 11:06.240 Aber was ist so die Vorstellung? 11:07.760 --> 11:10.820 Ein Baum kann rauskommen, das kann man sich noch lebhaft vorstellen, 11:10.960 --> 11:12.460 kann ein Graf rauskommen? 11:14.600 --> 11:21.060 Also einer, der nicht ein Baum ist, also bei dem irgendein Knoten über 11:21.060 --> 11:22.980 mehr als ein Pfad erreicht werden kann. 11:22.980 --> 11:25.960 Also, nochmal Frage, wer war für Ja? 11:36.030 --> 11:39.310 Ja, der hier wird er nur einmal besucht und in Folge dessen... 11:39.310 --> 11:44.510 Nein, nein, nein, der wird zwar mehrfach besucht, nur der kürzeste 11:44.510 --> 11:48.230 Pfad wird markiert, wenn wir von dem aus weiterlaufen. 11:50.270 --> 11:52.590 Es kommt doch ein Baum raus und nicht ein Graf und das können Sie sich 11:52.590 --> 11:53.330 folgendermaßen überlegen. 11:53.450 --> 11:58.590 Nehmen Sie mal an, Sie erreichen einen Knoten erst über einen Weg und 11:58.590 --> 11:59.710 dann über einen zweiten Weg. 12:00.870 --> 12:05.010 Es lautet ja unsere Bedingung, wir wollen den kürzesten Pfad haben. 12:05.630 --> 12:09.330 Wir vergleichen deshalb, wenn wir zum zweiten Mal dorthin kommen, ob 12:09.330 --> 12:15.370 die Länge kürzer ist als die Länge, die wir bisher berechnet haben. 12:16.190 --> 12:19.830 Wenn das der Fall ist, dann nehmen wir den Pfad, sonst nicht. 12:21.070 --> 12:23.690 Das heißt, wir werden auf jeden Fall immer nur genau zu jedem Knoten 12:23.690 --> 12:24.930 nur einen Pfad konstruieren. 12:24.930 --> 12:29.270 Also kommt tatsächlich ein Baum raus und nicht ein allgemeiner Graf. 12:30.110 --> 12:33.270 Durch das sind so Überlegungen, können Sie leicht selbst anstellen, 12:33.410 --> 12:34.050 alles kein Problem. 12:40.880 --> 12:44.700 So, dann kann man sich noch überlegen, was der Aufwand ist und der 12:44.700 --> 12:48.540 Aufwand ist, wenn man das einigermaßen geschickt implementiert, ist 12:48.540 --> 12:55.200 also die Zahl der Knoten, der Logarithmus der Zahl der Knoten mal V 12:55.200 --> 12:58.000 und dann nochmal die Zahl der Kanten. 12:59.300 --> 13:01.340 Das werde ich jetzt nicht bei Einzelnen ausrechnen. 13:03.640 --> 13:11.760 So, das bringt uns eigentlich auf die Idee zu sagen, wäre eigentlich 13:11.760 --> 13:15.460 schön, wir würden überhaupt bei einem Graf, bei einem Graf, 13:15.660 --> 13:22.220 allgemeiner Graf, mal versuchen, einen Baum zu konstruieren, mit dem 13:22.220 --> 13:24.200 wir bereits alle Knoten erreichen können. 13:24.260 --> 13:26.400 Das hat man schon das letzte Mal am Montag. 13:26.480 --> 13:30.000 Man sieht hier wieder, wenn ich sage, dass die Menge der kürzesten 13:30.000 --> 13:35.780 Pfade einen Baum bilden und dann erreichen wir auch jeden der Knoten. 13:35.780 --> 13:39.920 Da kann man sich überlegen, ob man nicht generell so etwas einführen 13:39.920 --> 13:43.160 kann, wie einen Baum, mit dem ich jeden Knoten erreichen kann. 13:46.270 --> 13:49.390 Nun, wir geben uns wieder vor, einen ungerichteten Graf mit 13:49.390 --> 13:50.830 Kantengewichten, wie bisher. 13:52.910 --> 13:57.610 Wir wollen einen zusammenhängenden Teilgraf, derart, dass die Summe 13:57.610 --> 13:59.590 der Kantengewichte minimal ist. 14:00.390 --> 14:03.470 Und jetzt kommt genau das, was ich Ihnen schon gesagt habe, der 14:03.470 --> 14:09.450 gesuchte Teilgraf ist a-zyklisch, weil eben, wenn er zyklisch wäre, 14:09.550 --> 14:13.310 das heißt, wenn wir über zwei verschiedene Pfade an denselben Knoten 14:13.310 --> 14:18.010 kommen, dann muss einer zwangsläufig entweder gleich oder größer im 14:18.010 --> 14:20.730 Gewicht sein, als der andere. 14:22.530 --> 14:27.410 So, und wir nennen jetzt einen spannenden Baum den Teilgraf der 14:27.410 --> 14:30.650 Baumform, der alle Knoten des Grafen enthält. 14:33.980 --> 14:39.100 So, das heißt noch nicht unbedingt, dass wir, ja gut, wenn wir das 14:39.100 --> 14:42.320 Gewicht als Kriterium nehmen, dann haben wir gesehen, wird es ein 14:42.320 --> 14:48.040 Baum. 14:48.740 --> 14:52.040 Hier sieht man auch so mal ein Beispiel, wenn das so ein Graf ist, 14:52.180 --> 14:57.200 dann sehen Sie hier, jetzt ohne Gewichte, dass das, was hier rot 14:57.200 --> 15:00.680 markiert ist, ein solch spannender Baum ist. 15:01.500 --> 15:07.840 So, das Einzige, was sich jetzt unterscheidet gegenüber dem von 15:07.840 --> 15:12.040 früher, also dem, was ich gerade vorgeführt habe, mit der Menge der 15:12.040 --> 15:19.320 kürzesten Pfade ist, dass das Gesamtgewicht minimal werden soll. 15:20.620 --> 15:24.460 Und dann muss man erstmal nachweisen, dass tatsächlich das eine das 15:24.460 --> 15:25.140 andere bedingt. 15:25.420 --> 15:26.860 Das muss ja nicht unbedingt der Fall sein. 15:33.870 --> 15:34.950 So, hier gibt es so Beispiele. 15:35.570 --> 15:36.990 Wozu soll das gut sein? 15:37.110 --> 15:41.390 Gibt es Anwendungsprobleme, bei denen man einen solchen minimalen 15:41.390 --> 15:42.530 spannenden Baum sucht? 15:43.430 --> 15:49.210 Ganz typisch, Sie können eine Menge Probleme auf Grafen zurückführen. 15:49.350 --> 15:51.890 Hatte ich schon das letzte Mal gesagt, auch Anwendungsprobleme kann 15:51.890 --> 15:52.990 man auf Grafen überführen. 15:53.470 --> 15:58.950 Zum Beispiel, unsere ganzen Versorgungsnetze sind Netze und als solche 15:58.950 --> 16:00.230 als Grafen darstellbar. 16:00.430 --> 16:06.990 Also Abwassernetze, Wasserversorgungsnetze, Telekommunikationsnetze, 16:08.010 --> 16:10.510 Energieversorgungsnetze, Gasrohrnetze. 16:10.510 --> 16:14.430 Alles lässt sich mit Grafen darstellen. 16:14.950 --> 16:16.350 Und dann erheben sich immer sofort die Fragen. 16:16.870 --> 16:19.570 Jeder, der sowas betreiben muss, oder wenn er es erstmal überhaupt 16:19.570 --> 16:22.910 investieren muss, um es aufzubauen, der fragt immer nach den minimalen 16:22.910 --> 16:23.230 Kosten. 16:25.070 --> 16:28.510 Also Grafene Algorithmen sehen so aus, dass wenn ich mit den Kanten 16:28.510 --> 16:33.570 irgendwelche Kosten verbinde, dass ich dann auch so etwas wie 16:33.570 --> 16:36.430 Algorithmen entwickeln kann, die dann mir die minimalen Kosten 16:36.430 --> 16:36.870 liefern. 16:36.870 --> 16:41.550 Also schauen wir zum Beispiel an, wir geben uns so eine Landkarte vor 16:41.550 --> 16:46.910 mit so einem Netz und wir wollen ein Wasserleitungsnetz jetzt aufbauen 16:46.910 --> 16:49.370 mit minimalen Kosten. 16:50.650 --> 16:53.510 Aber was wir auf jeden verlangen, was wir wollen, ist, dass alle 16:53.510 --> 16:55.230 Ortschaften versorgt werden. 16:56.830 --> 16:59.950 Ich finde, da kann man sich schnell überlegen, dass die Gesamtkosten 16:59.950 --> 17:09.750 unseres Netzes einfach die Summe der Längen aller Kanten sind, die wir 17:09.750 --> 17:13.050 irgendwie in diese Versorgung mit einbeziehen müssen. 17:13.630 --> 17:17.650 Und da werden wir zu jedem Ort nur genau einmal kommen müssen, wir 17:17.650 --> 17:21.850 wollen eigentlich aus verschiedenen Systemen über verschiedene 17:21.850 --> 17:26.310 Leitungen versorgen, kommt auch automatisch, wird ein Baum verlangt. 17:26.990 --> 17:29.890 So, Rechnernetze kann man ganz ähnlich machen, nur bei Rechnernetzen 17:29.890 --> 17:33.130 ist es manchmal etwas komplizierter, weil wir dort aus 17:33.130 --> 17:38.250 Sicherheitsgründen, nehmen wir das Internet, da man sie so vermarscht, 17:38.430 --> 17:43.190 dass man alle Knoten über mehr als einen Weg erreichen kann. 17:43.190 --> 17:46.290 Aber es gibt gewisse Rechnernetze, bei denen man darauf verzichtet. 17:50.640 --> 17:52.420 So, hier sehen wir zum Beispiel sowas. 17:52.540 --> 18:00.360 Nehmen wir mal an, unser Netz sähe so aus, also unsere Ortschaften, 18:00.480 --> 18:03.640 und wir zeichnen jetzt mal die Verbindungen ein, dass man Leitungen 18:03.640 --> 18:08.440 ziemlich direkt in der Luftlinie miteinander verbinden kann. 18:09.320 --> 18:14.360 Dann, ja, zum Beispiel, das ist ein Baum. 18:15.480 --> 18:20.360 Und zwar zweifellos, jeder Knoten ist mit jedem verbunden, wenn auch 18:20.360 --> 18:21.780 auf komplizierte Weise. 18:22.680 --> 18:26.480 Wir haben ja auch nicht gesagt, wo jetzt die Pumpstationen sind, aber 18:26.480 --> 18:29.820 jedenfalls zunächst mal als einfaches Problem, erreichen wir auf die 18:29.820 --> 18:31.360 Art jeden Ort. 18:31.600 --> 18:35.600 Und das Ganze ist, wie wir sehen, auch tatsächlich ein Baum, übrigens 18:35.600 --> 18:40.160 mit zwei Zweigen, ein Unterbaum, der hier weg geht, und einer, der 18:40.160 --> 18:41.980 hier rüber geht. 18:44.980 --> 18:47.620 Oder, da gibt es noch einen anderen, der sieht so aus. 18:48.760 --> 18:51.540 So, welcher ist besser? 18:57.680 --> 19:00.820 Also, es sind keine Gewichte im Augenblick da, infolgedessen ist die 19:00.820 --> 19:02.200 Frage etwas unfair. 19:02.360 --> 19:05.840 Wenn wir aber mal annehmen, für einen Augenblick, dass die Gewichte 19:05.840 --> 19:09.400 überall eins sind, dann sehen Sie hier, dass die Gesamtkosten hier 19:09.400 --> 19:10.080 vier sind. 19:11.660 --> 19:15.840 Und hier sind sie auch vier. 19:19.280 --> 19:20.920 Also, damit können wir nicht viel anfangen. 19:25.360 --> 19:28.360 Wenn es etwas größer wird, dann wird es nicht, also man muss irgendwie 19:28.360 --> 19:31.700 erreichen, dass man zunehmend eine Kante mehrfach benutzt, für 19:31.700 --> 19:32.340 verschiedene Zwecke. 19:33.020 --> 19:35.940 Dann muss man aber auch einen größeren Querschnitt wählen, dann 19:35.940 --> 19:37.120 steigen die Kosten wieder. 19:37.760 --> 19:40.020 Also, man kann es beliebig kompliziert machen, das Problem. 19:41.040 --> 19:43.020 So, aber wenn wir Gewichte dranhängen würden, dann würde es vielleicht 19:43.020 --> 19:44.220 schon interessanter werden, das Problem. 19:46.400 --> 19:49.360 Hier ist noch so ein anderes Beispiel, kann man sich von UPS 19:49.360 --> 19:52.000 vorstellen, oder auch von DLH. 19:53.700 --> 19:58.160 Wir geben uns wieder eine Landkarte vor, und wir nehmen also an, dass 19:58.160 --> 20:00.820 alle Ortschaften versorgt werden, jetzt über das Straßennetz. 20:04.280 --> 20:07.620 Und da lohnt es sich unter Umständen erst einmal hierarchisch 20:07.620 --> 20:10.680 vorzugehen, das macht ja auch die Post üblicherweise, oder alle 20:10.680 --> 20:12.840 Briefzusteller, die global arbeiten. 20:13.360 --> 20:15.940 Die arbeiten hierarchisch, irgendeine Strecke wird zum Beispiel mit 20:15.940 --> 20:19.680 Flugzeugen überwunden, eine zweite Strecke wird mit großen Lastwagen 20:19.680 --> 20:23.600 überwunden, und erst dann geht es sofort in die Verteilung mit 20:23.600 --> 20:26.060 einzelnen, mit kleineren Automobilen. 20:26.060 --> 20:31.040 So, da kann man sagen, in jedem Ort kommt ein großes Paket an, und das 20:31.040 --> 20:33.220 muss auf mehrere kleine verteilt werden. 20:33.540 --> 20:38.300 Dann haben wir automatisch von vornherein eine Art Baumstruktur, die 20:38.300 --> 20:39.200 wir erzeugen wollen. 20:40.820 --> 20:44.680 Und wiederum gilt, dass die Gesamtkosten proportional der Summe der 20:44.680 --> 20:47.860 Längen sein soll, und dann hebt sich wieder die Frage, wie die 20:47.860 --> 20:49.260 Transportwege aussehen sollen. 20:51.620 --> 20:54.780 So, jetzt überlegen wir uns mal, wie wir vorgehen können. 20:55.780 --> 20:59.840 Wir suchen also nicht nur irgendeinen Spannbaum, sondern wir suchen 20:59.840 --> 21:01.400 den mit minimalen Kosten. 21:05.640 --> 21:10.240 Ja, jetzt können wir ja schon sagen, unser Algorithmus mit dem 21:10.240 --> 21:21.060 kürzesten Pfad, der liefert ja für einen gegebenen Knoten einen 21:21.060 --> 21:21.820 Spannbaum. 21:23.380 --> 21:28.560 So, jetzt haben wir nur, leider wissen wir natürlich noch nicht, ob 21:28.560 --> 21:29.840 das jetzt von jedem... 21:31.040 --> 21:33.560 Wir wissen nur für einen Knoten, wir müssen es jetzt feststellen für 21:33.560 --> 21:34.240 alle Knoten. 21:34.660 --> 21:38.160 Wenn wir durch alle Knoten durchgehen, jeden Knoten als Ausgangspunkt 21:38.160 --> 21:42.140 eines Spannbaums nehmen, dann bilden wir einfach über diese ganzen 21:42.140 --> 21:46.520 Mengen nochmal das Minimum, und dann haben wir schließlich den Baum 21:46.520 --> 21:51.220 mit minimalen Kosten. 21:51.980 --> 21:57.860 So, das heißt aber, dass der Aufwand, von dem wir vorhin festgestellt 21:57.860 --> 22:04.900 haben, der ist von dieser Form, also die Menge der Kanten plus nochmal 22:04.900 --> 22:09.340 der Logarithmus der Knotenzahl mal der Knotenzahl selbst. 22:10.060 --> 22:12.560 Dann müssen wir das nochmal mit V multiplizieren. 22:15.660 --> 22:21.000 Und das ist schlimmer als quadratisch. 22:24.720 --> 22:26.820 Nämlich V² mal Log V. 22:28.940 --> 22:32.040 Da sieht man schon, dass unsere, wir haben jetzt nur 22:32.040 --> 22:34.180 Optimierungsprobleme zu tun, man sieht schon deutlich, dass 22:34.180 --> 22:38.600 Optimierungsprobleme etwas typisch sind, die neigen alle dazu, einen 22:38.600 --> 22:43.180 Aufwand hochzutreiben, und wir werden auch feststellen, dass die, und 22:43.180 --> 22:45.900 Sie werden es auch später noch immer wieder antreffen, dass 22:45.900 --> 22:50.960 Optimierungsprobleme eine fatale Tendenz dazu haben, in den Bereich 22:50.960 --> 22:53.320 der NP-harten Probleme zu gehen. 22:53.440 --> 22:55.360 Also das ist noch harmlos, weil wir es nicht immer noch polynomiell 22:55.360 --> 22:55.680 kriegen. 22:57.380 --> 23:01.420 Generell, also Optimierungsprobleme sind ekelhaft, aber leider sehr 23:01.420 --> 23:06.600 verbreitet, und man muss dann eben, wenn der Aufwand für die 23:06.600 --> 23:09.340 systematische Lösung zu groß ist, dann geht man halt zu heuristischen 23:09.340 --> 23:12.480 Lösungen über und versucht Nährungslösungen zu finden, die nicht allzu 23:12.480 --> 23:14.220 weit vom Optimum entfernt sind. 23:15.260 --> 23:17.500 So, immerhin, das wäre eine Lösungsmöglichkeit. 23:18.960 --> 23:22.140 Aber als Algorithmiker wird man an der Stelle sagen, da bin ich nicht 23:22.140 --> 23:25.740 zufrieden, das muss doch eigentlich noch besser und schneller gehen, 23:26.200 --> 23:29.940 und jetzt ist ja der Algorithmiker eben gefordert, eine bessere Lösung 23:29.940 --> 23:32.060 zu finden und sich dazu einige Gedanken zu machen. 23:32.420 --> 23:33.340 Das werden wir auch mal tun. 23:35.920 --> 23:42.020 Nun, wir erinnern uns ja, dass wir eine Menge von Entwurfsmustern 23:42.020 --> 23:44.660 hatten, wie man so an eine Algorithmuskonstruktion herangeht. 23:44.760 --> 23:46.100 Die kann man also auch mal durchprobieren. 23:47.040 --> 23:50.000 Wir werden auch eine ganze Reihe noch im Verlauf dieser Vorlesung mal 23:50.000 --> 23:50.340 durchexerzieren. 23:51.580 --> 23:53.540 Zum Beispiel fällt einem ein, man könnte vielleicht dynamisches 23:53.540 --> 23:57.320 Programmieren treiben, da kann man da einiges vorberechnen. 23:57.320 --> 24:02.360 Aber ein Primitivverfahren, so etwas, das sehr leicht auch für 24:02.360 --> 24:05.320 heuristische Verfahren verwendet wird, also bei Nährungslösungen zu 24:05.320 --> 24:08.260 konstruieren, sind die gierigen Verfahren. 24:10.020 --> 24:17.960 Und die gierigen Verfahren sehen ja so aus, dass wir einfach zunächst 24:17.960 --> 24:20.820 einmal uns die Informationen und die Entscheidungen, die bisher 24:20.820 --> 24:25.720 getroffen worden sind, ansehen und dann eine neue Entscheidung treffen 24:25.720 --> 24:27.960 und diese Entscheidung nicht mehr revidieren. 24:28.840 --> 24:31.480 Gierig heißt also einfach, ich nehme mir ein großes Stück von Kuchen, 24:32.940 --> 24:35.560 aber wenn ich es gegessen habe, ist die Entscheidung natürlich nicht 24:35.560 --> 24:36.380 mehr rückgängig zu machen. 24:38.840 --> 24:41.000 So, und jetzt könnte man sich überlegen, ob wir hier mit dem gierigen 24:41.000 --> 24:45.200 Verfahren schon irgendwo an eine vernünftige Stelle kommen, ob wir zu 24:45.200 --> 24:48.000 einer Lösung kommen, ob wir eine Nährungslösung haben, die recht gut 24:48.000 --> 24:51.300 ist, oder ob wir vielleicht sogar trotzdem eine systematische Lösung 24:51.300 --> 24:51.680 finden. 24:52.540 --> 24:56.160 So, das Erste, was man sich dann sagt, ist, Moment, Moment, wir haben 24:56.160 --> 25:00.680 ja eigentlich schon gesehen, wenn wir nach kürzesten Pfaden suchen, 25:02.920 --> 25:04.540 dann revidieren wir ja Entscheidungen. 25:04.640 --> 25:08.260 Und zwar, wir revidieren immer die Entscheidung, dass wir etwas, was 25:08.260 --> 25:11.220 wir bisher im Knoten, den wir angetroffen haben, dem wir einen 25:11.220 --> 25:14.020 kürzmöglichen Pfad gegeben haben, die revidieren wir ja noch einmal. 25:14.320 --> 25:16.700 Wir sagen, nein, das ist doch noch nicht der kürzeste mögliche Pfad 25:16.700 --> 25:18.360 und wir ersetzen ihn durch einen neuen. 25:18.360 --> 25:21.440 Nein, wir haben auch gewisse Pfade, die wir durch Laufende haben, 25:21.520 --> 25:23.400 wieder weggeworfen, wenn wir uns erinnern. 25:23.740 --> 25:29.600 Also es sieht eigentlich so aus, dass die Berechnung mit dem kürzesten 25:29.600 --> 25:34.040 Pfaden, dass die Revisionszwänge enthält. 25:36.020 --> 25:38.920 Und jetzt kann man sich immer noch überlegen, vielleicht schaffe ich 25:38.920 --> 25:43.580 es, einen Algorithmus zu finden, der auf diese Revision verzichtet und 25:43.580 --> 25:46.040 trotzdem zum korrekten Ergebnis kommt. 25:46.040 --> 25:50.580 Also müsste ich eigentlich studieren, wie sind die Revisionen zustande 25:50.580 --> 25:53.620 gekommen, gibt es möglicherweise einen Schritt, der die Revision 25:53.620 --> 25:54.300 auffällt. 25:54.620 --> 25:58.080 Dazu müssten wir aber alle zusammen, sämtliche Knoten gleichzeitig 25:58.080 --> 25:58.560 betrachten. 26:00.480 --> 26:03.320 Also machen wir etwas ganz anderes, wir probieren es mal aus und 26:03.320 --> 26:06.720 sagen, wir versuchen erstmal eine Heuristik und versuchen hinterher 26:06.720 --> 26:09.920 festzustellen, ob das wirklich eine Heuristik ist oder doch eine 26:09.920 --> 26:10.820 systematische Lösung. 26:13.860 --> 26:17.620 So, ich behaupte von vornherein, was ich Ihnen jetzt vorführe, liefert 26:17.620 --> 26:18.920 sogar eine systematische Lösung. 26:21.320 --> 26:25.380 Den kennen Sie schon, der ist auch schon in der Informatik 1 Ihnen 26:25.380 --> 26:27.260 vorexerziert worden, das ist der Algorithmus in Kuskal. 26:28.280 --> 26:34.960 Und der sieht folgendermaßen aus, wir nehmen unsere Kanten und werden 26:34.960 --> 26:38.240 diese Kanten in aufsteigender Reihenfolge sortieren. 26:39.400 --> 26:42.840 Das ist ja immer der Trick bei den kuskalischen Algorithmen oder 26:42.840 --> 26:46.420 überhaupt bei allen gierigen Algorithmen, wenn ich sage, ich nehme 26:46.420 --> 26:49.040 immer das größte Stück vom Kuchen, dann muss ich mir erstmal die 26:49.040 --> 26:52.820 Kuchenstücke alle in der Reihe nach hinlegen und ordnen, damit ich 26:52.820 --> 26:54.140 weiß, welches davon der größte ist. 26:54.740 --> 26:56.640 Und wenn ich den gegessen habe, dann ist der nächste dran. 26:58.560 --> 27:04.240 So, wenn wir jetzt eine Kante aufgreifen, dann gilt folgendes, wenn 27:04.240 --> 27:09.200 wir einen vorhandenen Baum haben 27:12.860 --> 27:22.960 und wir fügen jetzt eine neue Kante hinzu, also das heißt, wir kommen 27:22.960 --> 27:26.220 zu einem Knoten, den wir noch nicht betrachtet haben, das wäre also 27:26.220 --> 27:27.500 eine Möglichkeit der Lösung. 27:27.500 --> 27:32.540 Die zweite ist, und wir greifen ja immer in aufsteigender Reihenfolge, 27:32.720 --> 27:36.320 wir wollen ja das Minimum, deshalb fangen wir mit der kleinsten Größe 27:36.320 --> 27:40.080 an, wir greifen uns also die kürzeste Kante, die wir augenblicklich 27:40.080 --> 27:44.100 noch haben, heraus, schauen nach, wo bringen wir die jetzt ein. 27:44.180 --> 27:48.600 Jetzt entdecken wir, die gehört zu einem Baum, der schon vorhanden 27:48.600 --> 27:51.700 ist, also der schon ein spannender Baum, ein minimaler spannender Baum 27:51.700 --> 27:56.040 ist, dann fügen wir sie hinzu, sofern sie nicht zu einem Knoten führt, 27:56.040 --> 27:59.680 den wir bereits besucht haben, der also auch schon zu dem Baum gehört, 28:00.320 --> 28:01.880 sonst hätten wir ja einen Kreis. 28:03.280 --> 28:07.760 Oder die zweite Möglichkeit ist, was wir gleich feststellen werden, 28:07.920 --> 28:12.320 entstehen zunächst mal eine Menge einzelner Bäume und dann kann diese 28:12.320 --> 28:15.500 Kante zum Beispiel zwei solche Bäume verbinden und macht aus zwei 28:15.500 --> 28:16.660 Bäumen einen Baum. 28:17.220 --> 28:21.140 Das wäre eine weitere Möglichkeit, wenn ich zwei Bäume verbinde, wird 28:21.140 --> 28:22.620 es auf jeden Fall immer noch ein Baum sein. 28:24.860 --> 28:26.200 Entsteht also ein neuer Baum. 28:27.520 --> 28:31.800 Oder die dritte Möglichkeit, Entschuldigung, ich habe die dritte jetzt 28:31.800 --> 28:34.800 genannt, dass wir zwei verschiedene Bäume verbinden. 28:35.340 --> 28:40.460 Oder die dritte Möglichkeit ist die, ich habe zwei Knoten, die also 28:40.460 --> 28:44.500 diese Kante bilden und diese beiden Knoten gehören überhaupt noch 28:44.500 --> 28:45.420 nicht einem Baum an. 28:47.240 --> 28:49.420 Na ja, da verbinde ich sie und dann kriege ich auf die Erde einen 28:49.420 --> 28:49.900 neuen Baum. 28:50.620 --> 28:54.680 Das sind die drei Möglichkeiten, die entstehen, wenn ich mir ein, die 28:54.680 --> 28:58.560 nächste Kante, die jetzt im Augenblick das Minimum darstellt, wenn ich 28:58.560 --> 29:00.060 die jetzt mit einbringen will. 29:02.040 --> 29:08.060 So, man kann auf die Art entscheiden, sofort, ob eine Kante zur Lösung 29:08.060 --> 29:08.960 gehört oder nicht. 29:09.100 --> 29:11.420 Und das natürlich heißt, ich muss nicht revidieren. 29:12.680 --> 29:15.360 Es ist also gar keine Notwendigkeit zur Revision da. 29:15.520 --> 29:21.460 Also können wir sagen, dieser Algorithmus muss sogar zwingend zu einer 29:21.460 --> 29:22.820 korrekten Lösung führen. 29:23.680 --> 29:26.020 Und es wird ja auch garantiert, dass kein Zyklus entsteht. 29:27.980 --> 29:30.060 So, also führe ich wieder ein Beispiel vor. 29:30.240 --> 29:34.400 Wir haben hier einen Graf, ganz zweifellos. 29:34.900 --> 29:38.300 Der hat eine Menge von Kanten, die sind auch schön regulär angeordnet. 29:38.580 --> 29:39.820 Und da stehen auch die Gewichte dran. 29:40.800 --> 29:44.300 Und wir können uns auch schnell überlegen, wie die Ordnung aussieht. 29:44.420 --> 29:47.320 Wir fangen natürlich mit dieser 1er Kante an, dann kommt die 2er 29:47.320 --> 29:51.080 Kante, dann kommt die 4er Kante, dann die 6er Kante und so weiter. 29:51.440 --> 29:53.680 Und ganz am Ende haben wir eine Kante der Länge 28. 29:57.840 --> 29:58.760 Also fangen wir an. 29:59.640 --> 30:04.960 Die erste Kante, die wir in jetzt sortierter Folge vorfinden, ist also 30:04.960 --> 30:05.940 die Kante 1. 30:06.160 --> 30:07.380 Wir greifen die heraus. 30:07.920 --> 30:11.820 Jetzt kommt unsere Regel zunächst einmal ins Spiel, die besagt, 30:11.980 --> 30:17.360 verbinde zwei bis jetzt noch nicht markierte Knoten zu einem neuen 30:17.360 --> 30:17.680 Baum. 30:18.580 --> 30:24.720 Diese rote Kante definiert jetzt einen Baum im Aufbau. 30:26.380 --> 30:28.620 Das nächste, was wir wissen, ist 2. 30:30.080 --> 30:34.860 Also die 2, wenn wir die hinzufügen, dann ist das immer noch ein Baum. 30:35.520 --> 30:38.100 Jetzt in dieser Phase kam die 1. 30:38.220 --> 30:43.180 Regel ins Spiel, die besagt, wenn du einen Baum hast und die neue 30:43.180 --> 30:47.240 Kante verlängert diesen Baum, dann füge es hinzu, es sei denn, der 30:47.240 --> 30:50.800 Endknoten der Kante ist bereits besucht worden. 30:51.020 --> 30:51.820 Ist aber hier nicht der Fall. 30:52.140 --> 30:53.400 Also kommen die Regeln ins Spiel. 30:55.020 --> 30:57.460 So, dritte ist die 4 hier. 31:00.000 --> 31:02.060 Können wir die jetzt hier hinzufügen, die 4? 31:06.050 --> 31:06.650 Wer ist dafür? 31:07.990 --> 31:10.410 Also fügen wir es hinzu, demokratisch. 31:13.130 --> 31:15.850 So, da galt nochmal die gleiche Regel, diese erste Regel. 31:15.850 --> 31:17.570 So, der nächste ist 6. 31:19.250 --> 31:20.890 Ja, dürfen wir die 6 hinzufügen? 31:22.870 --> 31:27.750 Nein, klar, das greift auch keine unserer 3 Regeln mehr, weil beide 31:27.750 --> 31:30.190 Knoten markiert sind, also ignorieren wir die. 31:30.710 --> 31:32.210 Und jetzt kommen wir als nächstes zur neuen. 31:32.530 --> 31:33.930 Jetzt fangen wir mit dem neuen Baum an. 31:35.490 --> 31:37.670 Dann haben wir als nächstes die 11. 31:38.950 --> 31:40.470 Ah, dürfen wir die 11 hinzufügen? 31:41.810 --> 31:43.550 Ja, also dazu. 31:44.650 --> 31:47.070 Jetzt haben wir die 12. 31:48.250 --> 31:49.050 Darf die dazu? 31:50.090 --> 31:52.170 Also, dann ist das nächste die 13. 31:53.010 --> 31:54.470 Die gibt wieder einen neuen Baum. 31:56.010 --> 31:57.590 Dann haben wir 17. 31:58.230 --> 31:59.970 Ah, die 17, dürfen wir die hinzufügen? 32:02.130 --> 32:03.430 Ja, also hinzu. 32:05.070 --> 32:06.990 So, jetzt haben wir 19. 32:07.750 --> 32:09.230 Darf offensichtlich nicht dazu. 32:10.850 --> 32:12.470 22, darf dazu. 32:13.950 --> 32:15.270 So, und jetzt sind wir fertig. 32:15.890 --> 32:17.830 Die 28 brauchen wir nicht mehr, gut, die betrachten wir auch. 32:18.190 --> 32:19.830 Stellen fest, bringt nichts Neues mehr. 32:22.770 --> 32:26.510 So, also Sie sehen, dieser Algorithmus liefert tatsächlich, man kann 32:26.510 --> 32:29.890 auch sehr schnell den Beweis führen, dass der tatsächlich zu einem 32:29.890 --> 32:31.410 minimalen Spannenbaum führt. 32:34.530 --> 32:39.990 So, man kann das tatsächlich, es gibt noch eine andere Sichtweise, und 32:39.990 --> 32:43.450 diese Sichtweise ist notwendig, damit wir den Beweis führen können. 32:44.950 --> 32:53.010 Wie wir sagen, zunächst einmal, zu jedem Zeitpunkt haben wir einen 32:53.010 --> 32:54.850 Wald minimal spannender Bäume. 32:55.170 --> 32:58.250 Wir sind noch nicht durch, aber alles, was wir bisher erzeugt haben, 32:58.310 --> 33:00.970 haben wir gesehen, das ist möglicherweise mehr als ein Baum, also ein 33:00.970 --> 33:01.170 Wald. 33:02.410 --> 33:07.570 Wir wissen aber auf jeden Fall, dass wir dort immer die, bis jetzt die 33:07.570 --> 33:10.850 kleinstmöglichen Kanten untergebracht haben, also sind auf jeden Fall, 33:11.310 --> 33:14.930 soweit wir das bisher haben, jeweils minimal spannende Bäume. 33:16.510 --> 33:18.990 So, jetzt müssen wir den Induktionsanfang definieren. 33:20.870 --> 33:23.610 Und der Induktionsanfang, der ist ganz einfach, wir sagen nämlich, 33:23.970 --> 33:28.390 jeder Knoten ist für sich bereits ein minimal spannender Baum. 33:29.710 --> 33:34.470 Auch trivial, denn jeder Knoten bildet selbst einen trivialen Baum. 33:35.390 --> 33:38.810 Und die Länge ist natürlich bis jetzt noch keine Kante im Spiel, also 33:38.810 --> 33:39.110 Null. 33:42.470 --> 33:47.770 So, und der Induktionsschritt besagt einfach, durch das Hinzufügen 33:47.770 --> 33:53.870 einer Kante erzeuge ich wiederum einen Wald minimal spannender Bäume, 33:54.470 --> 33:57.030 in dem Fall eben nur noch genau einen einzigen. 34:01.200 --> 34:03.920 So, und jetzt sehen Sie unten auch den Algorithmus, der übersetzt 34:03.920 --> 34:08.260 jetzt einfach diese Sichtweise hier in einen Algorithmus. 34:10.040 --> 34:14.800 Der besagt, wir sortieren erstmal unsere Kanten nach dem Schritt, das 34:14.800 --> 34:15.380 haben wir ja gesagt. 34:16.660 --> 34:20.500 Dann erzeugen wir zu jedem Knoten seinen minimalen Spannbaum. 34:20.740 --> 34:22.920 Das ist irgendeine Datenstruktur, die wir aufbauen. 34:23.440 --> 34:25.740 Und da verweist halt jetzt jeder Knoten zunächst mal auf einen 34:25.740 --> 34:26.700 trivialen Spannbaum. 34:28.160 --> 34:30.960 Und dann führen wir einfach per Induktion 34:34.760 --> 34:38.140 die kürzeste Kante, die noch nicht hinzugefügt worden ist, hinzu. 34:38.140 --> 34:41.520 Sofern eben kein Zyklus entsteht. 34:42.120 --> 34:43.920 Wir führen uns also jetzt sogar darauf zurück. 34:45.280 --> 34:48.680 Jetzt sehen Sie übrigens hier an dieser Stelle, dass ich sozusagen 34:48.680 --> 34:52.700 zwei Entwurfsmuster miteinander vermischt habe. 34:53.540 --> 34:58.140 Eingestiegen sind wir über einen gierigen Algorithmus und abschließen 34:58.140 --> 35:01.660 tun wir das Ganze, indem wir sagen, es ist ein Algorithmus, den wir 35:01.660 --> 35:03.180 über Induktion ableiten. 35:07.840 --> 35:10.280 So, und jetzt sollten wir noch beweisen, dass das korrekt ist. 35:10.280 --> 35:13.520 Das heißt, dass das Ergebnis tatsächlich, nicht nur wie wir intuitiv 35:13.520 --> 35:18.240 glauben, sondern wir beweisen wirklich, dass dieser Baum, der so 35:18.240 --> 35:20.640 entstanden ist, ein minimaler Baum ist. 35:22.040 --> 35:24.300 Und wir wissen, der Induktionsanfang ist trivial. 35:24.820 --> 35:26.140 Alles hat die Länge 0. 35:28.440 --> 35:29.560 Also die Gesamtlänge ist 0. 35:32.260 --> 35:36.440 Und wir wissen, dass jeder einzelne ein solcher minimaler Baum ist. 35:36.440 --> 35:40.020 So, und jetzt müssen wir uns ansehen, was passiert denn im 35:40.020 --> 35:40.940 Induktionsschritt. 35:41.200 --> 35:45.180 Da muss ja sichergestellt sein, dass wir, nachdem wir einen einzelnen 35:45.180 --> 35:49.580 Schritt durchgeführt haben, dass wir dann wiederum einen minimalen 35:49.580 --> 35:50.180 Baum haben. 35:50.380 --> 35:53.520 Oder einen Wald minimaler Bäume. 35:55.320 --> 35:59.640 So, wir wissen auf jeden Fall, nehmen wir folgendes an. 36:00.900 --> 36:01.880 Wenn wir... 36:04.160 --> 36:07.720 Wir verbinden ja jetzt, wie wir sehen, immer Bäume. 36:08.960 --> 36:13.300 Auch ein einzelner Knoten, den wir hinzufügen, ist immer das Verbinden 36:13.300 --> 36:14.020 zweier Bäume. 36:14.200 --> 36:17.540 Also können wir sagen, wenn wir eine Kante hinzufügen, dann haben wir 36:17.540 --> 36:21.540 einen minimalen Baum G und einen minimalen Baum H. 36:23.360 --> 36:25.860 Und jetzt verbinden wir den mit einer Kante E. 36:27.780 --> 36:32.160 So, wir wissen also, G ist ein minimaler Baum, H ist ein minimaler 36:32.160 --> 36:35.440 Spannbaum und wir wissen, E ist die kürzeste Kante. 36:37.080 --> 36:41.400 So, und wenn wir jetzt also mit E arbeiten, dann wissen wir, dass auch 36:41.400 --> 36:46.060 das Ergebnis selbst minimale Länge besitzen muss. 36:46.920 --> 36:51.000 Weil, wenn es noch eine zweite Kante F gäbe, dann käme F ja in der 36:51.000 --> 36:54.820 Sortierordnung nach dem E, wäre also mindestens gleich lang oder 36:54.820 --> 36:55.100 länger. 36:56.260 --> 37:00.940 Und kann infolgedessen auf keinen Fall ein kürzerer Spannbaum sein. 37:02.360 --> 37:07.460 Also kann man nur sagen, dass wir in jedem Fall nicht besser sein 37:07.460 --> 37:08.660 können als der E. 37:09.840 --> 37:13.240 So, und die andere Möglichkeit nämlich, dass wir noch eine weitere 37:13.240 --> 37:17.240 Kante finden, entfällt auch, weil wir Zyklen verbieten. 37:18.500 --> 37:22.160 Das heißt, wir können, wenn wir eine neue Kante hinzufügen, 37:22.660 --> 37:27.540 bestenfalls eine andere entfernen, was noch durch Umordnung erfolgen 37:27.540 --> 37:27.820 könnte. 37:28.240 --> 37:31.540 Da wir ja aber sortiert vorgegangen sind, ist eine solche Umordnung 37:31.540 --> 37:32.460 nicht mehr erforderlich. 37:36.720 --> 37:40.360 Also, das ist eigentlich ein sehr bequemer Algorithmus. 37:41.140 --> 37:44.600 Und jetzt muss man den Aufwand ansehen, und jetzt sehen wir, der 37:44.600 --> 37:49.940 Aufwand dieses Algorithmus ist merklich geringer. 37:50.360 --> 37:56.440 Der ist nämlich nur noch E mal Logarithmus von V und damit dramatisch. 37:57.460 --> 38:01.640 Also enorm viel kürzer, viel geringer als der, den wir für den ersten 38:01.640 --> 38:06.600 Algorithmus mit der minimalen Tatlänge haben. 38:09.800 --> 38:14.580 So, Sie sehen also, es lohnt sich zunächst einmal, wenn Sie auf 38:14.580 --> 38:18.220 Algorithmen mit relativ hohem Aufwand stoßen, es lohnt sich, sich 38:18.220 --> 38:20.560 wirklich Gedanken zu machen, mal mit verschiedenen Mustern zu 38:20.560 --> 38:24.840 arbeiten, möglicherweise auch noch mit der Datenstruktur 38:24.840 --> 38:29.020 herumzuspielen, um zu sehen, ob man nicht durchaus günstigere Aufwände 38:29.020 --> 38:29.800 erreichen kann. 38:30.080 --> 38:33.820 Und hier zumindest erreichen wir einen dramatisch besseren Aufwand. 38:33.900 --> 38:35.120 Er ist nämlich linear, wie wir sehen. 38:40.240 --> 38:43.160 So, hier ist noch ein weiteres Problem, das sogenannte Matching 38:43.160 --> 38:43.540 -Problem. 38:44.880 --> 38:54.260 Das Matching-Problem besteht darin, dass wir Paare matchen wollen. 38:54.400 --> 38:55.900 Nehmen wir mal so ein Beispiel an. 38:58.760 --> 38:59.360 Tanzkurs. 39:01.020 --> 39:08.140 Hier haben wir also männliche Teilnehmer und weibliche Teilnehmer und 39:08.140 --> 39:10.300 vielleicht haben Sie auch mal einen Tanzkurs durchgemacht. 39:13.560 --> 39:17.340 Dann wissen Sie halt, dass immer das Problem ist, wie kriegt man unter 39:17.340 --> 39:20.180 bestimmten Umständen jeweils gemischte Paare. 39:20.940 --> 39:24.460 Nehmen wir mal an, die Zahl der männlichen und weiblichen Teilnehmer 39:24.460 --> 39:25.140 ist gleich. 39:25.140 --> 39:28.320 Dann könnte ich das eigentlich folgendermaßen das Problem beschreiben. 39:46.630 --> 39:49.070 Ich versuche mal rauszukriegen, ob Sie etwas ruhiger werden. 40:08.380 --> 40:11.060 Sie sehen hier, das Graph-Problem ist folgendermaßen, da haben wir das 40:11.060 --> 40:15.420 jetzt angegangen, wir sagen also wieder, wir wollen die Teilnehmer 40:15.420 --> 40:18.120 irgendwie einen Graph einbringen, aber wir haben das folgendermaßen 40:18.120 --> 40:25.790 gemacht, Sie sehen immer hier ist ein männlicher und hier haben wir 40:25.790 --> 40:30.850 den weiblichen und die wechseln sich als Knoten in dem Graph immer ab. 40:34.030 --> 40:37.350 Das hängt natürlich von den bezweckenden, aber wenn wir bezwecken, 40:37.790 --> 40:42.790 immer Paare zu finden, dann ist es eigentlich ganz sinnvoll, eine 40:42.790 --> 40:45.230 solche Abwechslung zunächst mal in den Graph reinzubringen und zu 40:45.230 --> 40:47.830 sagen, wen können wir denn mit jemandem zusammenbringen. 40:48.450 --> 40:51.610 So, man nennt, gehen wir mal noch zurück, man nennt solche Graphen, 40:51.670 --> 40:55.250 bei denen die Knoten unterschiedlichen Typs sind, es gibt nur zwei 40:55.250 --> 40:59.290 Typen, in dem Fall männlich und weiblich, das nennen wir einen 40:59.290 --> 41:00.830 Bipartitengraph. 41:01.850 --> 41:06.030 Ein bipartiter Graph hat sozusagen zwei Knotenmengen, U und V, also 41:06.030 --> 41:09.230 männlich und weiblich und wiederum Kanten. 41:09.970 --> 41:17.710 Wir müssen noch voraussetzen, dass U und V disjunkt sind und dann gilt 41:17.710 --> 41:23.110 folgendes, wenn wir so eine Kante E betrachten, aus zwei Knoten V1 und 41:23.110 --> 41:28.130 V2, dann muss gelten, das V1 muss aus der einen Menge sein und das V2 41:28.130 --> 41:29.430 aus der anderen Menge. 41:29.590 --> 41:34.590 Also entweder V1 männlich und V2 weiblich oder umgekehrt. 41:38.390 --> 41:41.630 So, und Sie können sich sofort eine Menge Probleme vorstellen, wo 41:41.630 --> 41:42.350 sowas passiert. 41:43.050 --> 41:48.090 Beispielsweise, also den Tanzkurs haben wir gerade genommen, oder wenn 41:48.090 --> 41:51.850 ich eine Zuordnung von Personal zu gewissen Aufgaben vornehmen will, 41:51.950 --> 41:52.850 dann kann ich das auch machen. 41:53.590 --> 41:58.690 Dann kann man zum Beispiel sagen, ich nehme einen Knoten mit den 41:58.690 --> 42:02.870 Arbeitskräften und ich nehme eine weitere Menge von Knoten mit den 42:02.870 --> 42:07.770 Arbeiten und dann verbinde ich einfach jeden Mitarbeiter mit den 42:07.770 --> 42:09.170 Arbeiten, die er übernehmen kann. 42:10.430 --> 42:13.110 Und wenn ich das tue, dann kriege ich wieder ein Netz, weil das ist 42:13.110 --> 42:16.690 etwas komplizierter als das, was ich hier aufgeführt habe, bei dem wir 42:16.690 --> 42:19.930 zum Beispiel die Aufgabenknoten höchstwahrscheinlich sehr viele 42:19.930 --> 42:20.630 Eingänge haben. 42:23.130 --> 42:25.010 Oder Koffer und Schließfächer. 42:27.790 --> 42:32.690 Es kommt eine riesen Horde, eine Reisetruppe der Gruppe an und 42:32.690 --> 42:35.330 versucht, in die Schließfächer reinzukommen. 42:35.830 --> 42:38.570 Da kann man auch irgendeine Planung machen, beispielsweise, wie ich 42:38.570 --> 42:41.090 das nur noch am Band stelle und dann wird das alles automatisch den 42:41.090 --> 42:42.190 Schließfächern zugeordnet. 42:43.110 --> 42:47.850 Also man kann relativ viele Probleme zunächst einmal in solche 42:47.850 --> 42:51.850 bipartiten Lösungen zerlegen oder bipartiten Mengen und dann 42:51.850 --> 42:53.350 anschließend in Graff-Formen überführen. 42:54.430 --> 42:58.170 So, jetzt kommen wir wieder zurück zu unserem Beispiel hier. 42:59.730 --> 43:02.090 Was wir jetzt haben wollen, ist Folgendes. 43:03.010 --> 43:07.570 Wenn wir jetzt eine Zuordnung treffen, dann würden wir sagen, gut, 43:08.810 --> 43:11.010 beispielsweise, das funktioniert hier. 43:11.750 --> 43:13.330 Dann bringen wir mal die zwei zusammen. 43:14.130 --> 43:15.490 So, damit ist die Eva vergeben. 43:16.710 --> 43:20.110 Aber der Martin kann ja sich dann an die Pia. 43:20.530 --> 43:22.290 Die Pia können ja ein Paar bilden. 43:22.850 --> 43:24.110 Dann ist die Pia auch vergeben. 43:24.370 --> 43:25.450 Die Uwe und Maria. 43:28.950 --> 43:30.630 Das geht auch noch. 43:34.510 --> 43:36.330 Und das würde auch noch funktionieren. 43:36.510 --> 43:41.050 Also hier sehen Sie, so durch reines Ansehen kann ich schon so das 43:41.050 --> 43:45.490 hinkriegen, dass alle Paare, dass ich tatsächlich das Maximum der vier 43:45.490 --> 43:46.450 Paare bilden kann. 43:46.710 --> 43:48.530 Aber ich hätte mich auch etwas dümmer anstellen können. 43:50.670 --> 43:56.290 Wenn ich mich so losgelegt hätte, dann bringe ich beispielsweise einen 43:56.290 --> 43:58.870 der weiblichen und einen der männlichen Teilnehmer nicht mehr unter. 44:00.230 --> 44:03.050 So, und jetzt stellen Sie sich vor, Sie haben nicht einen Graph mit so 44:03.050 --> 44:06.290 ein paar Knoten und Kanten, sondern Sie haben einen riesen Graph. 44:06.790 --> 44:08.810 Dann werden Sie von Hand natürlich nicht mehr viel bewegen können. 44:09.710 --> 44:12.770 Also brauchen wir wieder einen Algorithmus, der möglichst viele 44:12.770 --> 44:14.090 Paarbildungen zulässt. 44:14.830 --> 44:17.850 Und das nennen wir das Matching Problem. 44:23.730 --> 44:27.690 Frage, wie kriegt man bei großen Graphen, bei denen ich das nicht mehr 44:27.690 --> 44:30.770 durch Anschauungen lösen kann, wie kriege ich eine optimale 44:30.770 --> 44:31.810 Paarbildung zustande? 44:32.350 --> 44:36.130 So, und es gibt in vielen Varianten dann dieses Problem, zum Beispiel 44:36.130 --> 44:40.950 auch Dozenten mit Hörsälen und Zeiten zu matchen usw. 44:41.890 --> 44:45.290 Und auch diese Probleme landen sehr schnell wieder im Bereich der NP 44:45.290 --> 44:46.050 -harten Probleme. 44:46.410 --> 44:48.810 Also das sind auch wieder, wenn man will, Optimierungsprobleme. 44:49.770 --> 44:52.210 Jetzt das Matching Problem ist noch etwas harmloser und wollen mal 44:52.210 --> 44:54.610 sehen, ob wir da eine brauchbare Lösung finden. 44:57.050 --> 45:05.110 So, das erste überhaupt ist zunächst einmal, es lohnt sich häufig 45:05.110 --> 45:08.790 zunächst mal Probleme in bipartite Graphen zu überführen. 45:09.530 --> 45:12.850 Häufig hat man erstmal einen ganz normalen Graph da und dann geht es 45:12.850 --> 45:16.830 darum, wie kann man die in bipartite Graphen überführen. 45:18.830 --> 45:22.710 Und das läuft im Allgemeinen darauf hinaus, dass man immer eine 45:22.710 --> 45:25.270 abwechselnde Markierung vornimmt. 45:25.570 --> 45:28.610 Zum Beispiel hier haben wir einen Algorithmus, der besagt folgendes, 45:29.050 --> 45:33.210 ich fange mal mit einem Knoten V an, markiere den mit 0, die andere 45:33.210 --> 45:37.050 Markierung soll dann 1 sein und dann kann ich sagen, wenn ich jetzt 45:37.050 --> 45:46.610 eine Kante x und y finde, die mit x markiert ist, jetzt frage ich mich 45:46.610 --> 45:48.570 gerade, wo das V eigentlich geblieben ist, 45:51.740 --> 45:56.900 weil x markiert ist und y nicht markiert ist, dann markieren wir das y 45:56.900 --> 46:06.140 mit 1, beziehungsweise wenn der 1 ist, dann mit 0. 46:06.700 --> 46:08.660 Das muss doch funktionieren, schauen wir mal gleich an. 46:09.240 --> 46:16.300 Nehmen wir mal an, wir nehmen ein ganz einfaches Rechteck und wir 46:16.300 --> 46:23.120 fangen hier ja mit 0 an, dann greifen wir diese Kante heraus, dann 46:23.120 --> 46:26.820 kommen wir auf die 1, jetzt haben wir sogar zwei Kanten zur Auswahl, 46:26.920 --> 46:29.780 bei denen bereits eine Anfangsmarkierung ist. 46:30.300 --> 46:35.660 Nehmen wir die hier, kommt 1 raus, nehmen wir die hier, kommt 0 46:35.660 --> 46:43.140 heraus, das heißt wir müssen also die hier durchlaufen und dann ist 46:43.140 --> 46:48.100 das Einzige, was noch interessiert, ist da unten tatsächlich dann, da 46:48.100 --> 46:50.900 liegt eine Markierung vor, die unterschiedlich ist, das Fazit der Fall 46:50.900 --> 46:51.600 0 und 1. 46:52.800 --> 46:59.360 Hier haben wir einen Würfel und wir könnten auch wieder hier beginnen, 47:00.180 --> 47:04.340 dann können wir hier hin oder hier hin, markieren die um, dann gehen 47:04.340 --> 47:08.800 wir in der Richtung, erhalten 0 und müssen dann halt noch untersuchen, 47:09.580 --> 47:12.280 ob da auch hier tatsächlich zwischen 1 und 0 gewechselt wird. 47:12.660 --> 47:14.020 Dann gehen wir da runter und so weiter. 47:16.020 --> 47:18.980 Und jetzt, in diesen beiden Fällen hat es funktioniert, das heißt, 47:19.260 --> 47:21.840 nachdem wir durch waren, haben wir ja noch keineswegs alle Kanten 47:21.840 --> 47:25.340 besucht gehabt, für die restlichen Kanten, die wir noch nicht besucht 47:25.340 --> 47:28.620 haben, muss natürlich auch gelten, dass die Markierungen der beiden 47:28.620 --> 47:29.780 Knoten unterschiedlich sind. 47:29.980 --> 47:34.700 Also fragt man sich, wie ist das, gilt das nun generell für Würfel 47:34.700 --> 47:36.180 oder für Hyperwürfel oder nicht? 47:36.800 --> 47:38.800 Und da brauchen wir halt irgendjemanden, der für uns den Beweis 47:38.800 --> 47:44.560 übernimmt, Gott sei Dank gibt es aber hier einen Satz, anhand dessen 47:44.560 --> 47:50.020 wir dann nachweisen können, dass alle Hyperwürfel bipartit sind. 47:52.020 --> 47:55.600 Und der Beweis erinnert so ein bisschen schon an das, was wir schon 47:55.600 --> 47:59.440 mal von dem Rückenproblem gehört haben. 48:00.460 --> 48:05.540 Jeder Graph ist bipartit, wenn keine ungeraden Zyklen entstehen. 48:09.700 --> 48:12.280 So, die nächste Frage ist bei Bäumen. 48:12.740 --> 48:14.200 Nehmen wir hier einen Baum an. 48:16.200 --> 48:17.040 Das ist eine Null. 48:19.280 --> 48:21.180 Wir laufen links ab oder rechts ab. 48:22.300 --> 48:25.800 Aber in beiden Fällen erreichen wir zunächst mal die Knoten, die wir 48:25.800 --> 48:26.680 erreichen, ist 1. 48:28.300 --> 48:32.320 Von diesem Knoten aus, oder nehmen wir erstmal den hier, laufen wir 48:32.320 --> 48:36.800 weiter und markieren jetzt wieder anschließend den folgenden Knoten 48:36.800 --> 48:37.160 mit 0. 48:37.300 --> 48:39.080 Und so weiter nach unten, wenn es noch weiter ginge. 48:40.380 --> 48:43.400 Von hier aus gibt es auch einen einzigen Nachfolger, der wird mit 0 48:43.400 --> 48:44.060 markiert. 48:44.800 --> 48:46.840 Von dem gibt es wieder einen Nachfolger, der wird mit 1 markiert. 48:47.760 --> 48:49.300 Und die werden wieder mit 0 markiert. 48:50.380 --> 48:52.380 So, weder Frage Zufall oder nicht. 48:52.380 --> 48:55.100 Beim Baum kann man sich das eigentlich schon ziemlich lebhaft 48:55.100 --> 49:00.800 vorstellen, dass es in jedem Fall, dass die Bäume bipartit sind, oder 49:00.800 --> 49:03.020 dass man sie bipartit jedenfalls markieren kann. 49:03.560 --> 49:05.300 Aber wir nehmen auch wieder unseren Satz. 49:05.980 --> 49:08.900 Und in einem Baum kommt gar kein Zyklus vor, also insbesondere sind 49:08.900 --> 49:10.280 die Zyklen deshalb ungerade. 49:10.380 --> 49:12.220 Es ist ja nicht ungerade, sondern gerade. 49:12.780 --> 49:16.100 Und damit ist auch wieder, haben wir den Nachweis, dass die Bäume 49:16.100 --> 49:16.900 bipartit sind. 49:16.900 --> 49:19.800 Aber bei beliebigen Grafen wird es nicht um Längen komplizierter. 49:24.610 --> 49:32.570 Jetzt wollen wir uns mal ansehen, wie wir im Allgemeinen zu solchen 49:32.570 --> 49:33.490 Matchings kommen. 49:35.290 --> 49:37.030 Jetzt müssen wir zunächst mal Folgendes sagen. 49:37.350 --> 49:40.110 Was uns immer interessiert ist, hängen die Kanten schon zusammen oder 49:40.110 --> 49:40.910 hängen sie nicht zusammen? 49:41.450 --> 49:44.430 Wir sprechen einfach mal davon, dass Kanten unabhängig sind, wenn sie 49:44.430 --> 49:45.450 überhaupt nichts gemein haben. 49:46.890 --> 49:51.150 Also wenn wir zwei Kanten UV und XY haben, dann müssen wir uns nur 49:51.150 --> 49:56.550 ansehen, ist das U mit dem X oder Y irgendwie identisch oder ist das V 49:56.550 --> 49:58.210 mit dem X oder Y identisch. 49:58.650 --> 50:01.450 Und wenn das nicht der Fall ist, dann gibt es also keinen gemeinsamen 50:01.450 --> 50:02.010 Knoten. 50:02.450 --> 50:07.310 Und infolgedessen sagen wir dann, diese beiden Kanten sind unabhängig. 50:08.570 --> 50:11.670 So, auf der anderen Seite, wenn Sie einen Knoten gemeinsam haben, das 50:11.670 --> 50:14.190 ist diese etwas umständliche Formulierung, die besagt nichts anderes 50:14.190 --> 50:20.590 als, einer der beiden Werte, also U und V und X und Y sind identisch, 50:21.230 --> 50:27.270 dann sprechen wir von benachbarten oder verbundenen oder adjacenten 50:27.270 --> 50:27.910 Knoten. 50:30.430 --> 50:36.250 So, und jetzt gehen wir einen Schritt weiter und sagen, wir wollen ja 50:36.250 --> 50:37.610 am Ende auf ein Matching kommen. 50:37.610 --> 50:39.750 Und bei einem Matching ist natürlich ganz klar, wir können jeden 50:39.750 --> 50:41.070 Knoten nur genau einmal verwenden. 50:43.450 --> 50:48.090 Also können wir eigentlich sagen, ein Matching liegt dann vor, wenn 50:48.090 --> 50:52.630 wir eine Kantenmenge vorliegen haben, die dieses Matching definiert 50:52.630 --> 50:55.530 und bei der alle Kanten voneinander unabhängig sind. 50:56.650 --> 51:00.450 Also eine Kantenmenge, Matching ist das, was wir anstreben, ist 51:00.450 --> 51:04.150 unabhängig, wenn die Elemente selbst an den Kanten paarweise 51:04.150 --> 51:04.970 unabhängig sind. 51:06.490 --> 51:09.530 So, und mit den paar Definitionen müssten wir dann in der Lage sein, 51:09.630 --> 51:11.210 jetzt schon mal sowas wie Matching zu entwickeln. 51:13.890 --> 51:19.930 Das sagt nämlich nichts anderes als, schau halt, dass du eine Menge 51:19.930 --> 51:21.770 unabhängiger Kanten konstruierst. 51:25.640 --> 51:28.620 Ja, jetzt kann man natürlich noch einige Eigenschaften damit 51:28.620 --> 51:31.240 verbinden, denn natürlich können wir zunächst einmal darauf 51:31.240 --> 51:37.600 losarbeiten, eine Menge unabhängiger Kanten bestimmen, aber wenn uns 51:37.600 --> 51:40.420 zu viele Kanten und zu viele Knoten übrig bleiben, dann ist das keine 51:40.420 --> 51:41.360 besonders gute Lösung. 51:41.780 --> 51:45.180 Also werden wir erst einmal versuchen, unsere Matchings, die wir da so 51:45.180 --> 51:47.700 erzeugen, zu charakterisieren. 51:48.820 --> 51:53.960 Also zu dick umrandet soll jetzt der gematchte Knoten sein, der also 51:53.960 --> 51:59.420 verbraucht ist, und die, die erstmal dünn umrandet sind, das sind die 51:59.420 --> 51:59.920 freien. 52:00.960 --> 52:02.500 So, hier haben wir zum Beispiel einen Fall. 52:04.840 --> 52:13.180 Dann können wir sagen, dass ein Knoten als frei gilt, wenn er keine 52:13.180 --> 52:16.580 Kante des Matchings hat, also wenn einfach keine dicke Kante von ihm 52:16.580 --> 52:19.680 ausgeht, und sonst heißt er gematcht. 52:19.780 --> 52:23.880 Und jetzt sehen wir schon hier, hier haben wir beispielsweise zwei 52:23.880 --> 52:26.760 Knoten, das ist nämlich unser schlechtes Beispiel von vorhin, von 52:26.760 --> 52:31.760 unserem Tanzbeispiel, die noch frei sind, aber leider auch nicht mehr 52:31.760 --> 52:33.360 irgendwie untergebracht werden können. 52:34.260 --> 52:37.440 Es gibt keine Möglichkeit mehr, zwischen denen noch eine Kante zu 52:37.440 --> 52:37.720 ziehen. 52:38.060 --> 52:39.160 Sie sind auch nicht mal benachbart. 52:39.940 --> 52:44.000 Und da sind unsere drei Paare, die wir gematcht haben. 52:46.640 --> 52:49.480 So, was wir anstreben, ist natürlich das Tunlichste. 52:49.800 --> 52:54.980 Gar keine freien Knoten mehr existieren, und das nennen wir, wie hier 52:54.980 --> 52:58.700 beispielsweise, das nennen wir jetzt ein perfektes Matching. 52:59.280 --> 53:03.860 Das war unser zweites Beispiel, bei dem es uns gelungen war, alle 53:03.860 --> 53:05.720 Knoten unterzubringen bei unserer Tanzschule. 53:06.840 --> 53:10.620 Und hier ist also jeder einzelne Knoten Teil eines Matchings. 53:11.680 --> 53:14.100 Wir sehen, die sind alle nicht verbunden, also die Kanten sind alle 53:14.100 --> 53:14.760 unabhängig. 53:16.020 --> 53:18.700 Und weil keiner übrig geblieben ist, sprechen wir davon, dass es 53:18.700 --> 53:19.480 perfekt ist. 53:21.140 --> 53:23.480 So, jetzt gibt es natürlich auch noch eine andere Variante. 53:24.480 --> 53:26.880 Wir können nämlich sagen, wir haben irgendeinen Matching, und wir 53:26.880 --> 53:32.220 fragen uns, ist da noch eine weitere Kante hinzufügbar oder nicht? 53:33.420 --> 53:37.980 Und wir sagen, das ist ein maximales Matching, wenn man keine Kante 53:37.980 --> 53:38.760 hinzufügen kann. 53:38.840 --> 53:39.640 Wie ist denn das mit da oben? 53:40.260 --> 53:43.840 Das erste, das oberste Beispiel, ist das ein maximales Matching oder 53:43.840 --> 53:44.160 nicht? 53:45.880 --> 53:47.040 Ist es maximal oder nicht? 53:52.320 --> 53:54.300 Können wir noch eine Kante hinzufügen oder nicht? 53:57.140 --> 53:58.220 Geht noch eine hinzu? 53:58.960 --> 53:59.300 Nein. 54:00.000 --> 54:00.900 Also das ist maximal. 54:01.100 --> 54:03.640 Es war nicht perfekt, aber maximal. 54:04.080 --> 54:08.100 Also maximal sagt eigentlich nur, wenn du nicht perfekt bist, weiter 54:08.100 --> 54:08.740 geht es nicht mehr. 54:09.060 --> 54:13.000 Man muss möglicherweise zurück und nochmal versuchen, zum Teil nochmal 54:13.000 --> 54:14.140 ein neues Matching zu entwickeln. 54:14.140 --> 54:19.420 Also das ist nicht, und da haben Sie auch genau dasselbe Beispiel. 54:21.020 --> 54:27.580 Maximum heißt, dass ich kein Matching finde, bei dem ich noch mehr 54:27.580 --> 54:28.820 Kanten einbringen kann. 54:30.080 --> 54:31.440 Zum Beispiel das da oben. 54:32.860 --> 54:38.220 Unser zweites Beispiel ist auch ein Maximum-Matching, weil wir auch 54:38.220 --> 54:42.120 keine weitere Kante, weil wir kein Matching mehr finden können, das 54:42.120 --> 54:43.300 mehr Kanten erfasst. 54:43.720 --> 54:47.060 Und zwar einfach deshalb, weil wir ja die Knotenzahl, die definiert ja 54:47.060 --> 54:51.620 die Zahl der Matchings, wenn wir diese Knoten alle untergebracht 54:51.620 --> 54:54.900 haben, dann sind damit auch alle Kanten verbraucht und es gibt 54:54.900 --> 54:58.120 offensichtlich kein Matching, das irgendwie mehr Kanten aufbringen 54:58.120 --> 54:58.420 kann. 54:58.780 --> 55:02.040 Denn die Kantenzahl ist immer die Hälfte der Knotenzahl. 55:02.540 --> 55:05.120 So und jetzt kann es ja noch ungerade sein, das kann sich auch mal 55:05.120 --> 55:07.980 passieren, wenn die Zahl der Knoten ungerade ist, dann haben wir Pech 55:07.980 --> 55:08.320 gehabt. 55:08.320 --> 55:12.140 Aber dann muss einer frei bleiben und dann sprechen wir eben von fast 55:12.140 --> 55:12.680 perfekt. 55:13.760 --> 55:17.820 Zum Beispiel hier haben wir ein fast perfektes Matching, da haben wir 55:17.820 --> 55:20.080 einen Knoten hier noch hinzugeschlagen. 55:22.640 --> 55:26.280 So, man muss immer sagen, das sieht ein bisschen nach Spielerei aus, 55:26.320 --> 55:29.300 wenn man solche Definitionen aufstellt, aber es ist nicht schlecht, 55:29.640 --> 55:32.380 wenn Sie an ein Problem rangehen und das erst mal abstrahiert haben, 55:32.440 --> 55:34.740 sich so eine Reihe von Definitionen vorzugeben und zu sehen, 55:35.760 --> 55:39.020 verschaffen wir dir irgendwelche Ideen, wie ein Algorithmus aussehen 55:39.020 --> 55:39.400 könnte. 55:46.140 --> 55:50.140 Hier sehen wir etwa, wenn wir so ein bisschen rumspielen, dass wenn 55:50.140 --> 55:58.400 wir einen Kreis haben mit einer geraden Zahl von Knoten, dann gibt es 55:58.400 --> 56:00.540 genau zwei perfekte Matchings. 56:02.840 --> 56:08.700 Entweder nehme ich die eine Folge von Kanten oder dann versetzt um 56:08.700 --> 56:11.860 einen Knoten die zweite Folge von Kanten. 56:12.300 --> 56:14.840 Das ist übrigens auch eine interessante Beobachtung. 56:15.240 --> 56:17.840 Man sieht nämlich, dass wir von einem Matching zu einem anderen 56:17.840 --> 56:20.260 kommen, indem wir einfach um einen Schritt weiter laufen. 56:21.700 --> 56:24.040 Da könnte man sich auch wieder überlegen, ob man mit der Erkenntnis 56:24.040 --> 56:25.860 nicht später mal was anfangen können. 56:25.860 --> 56:29.220 Dass wir nämlich, wenn wir ein Matching haben, auch noch ein 56:29.220 --> 56:32.100 korrespondierendes Matching dazu finden können, auf einem Pfad 56:32.100 --> 56:36.120 zumindest, bei dem wir um eine Kante alles versetzt haben. 56:37.680 --> 56:41.100 Und außerdem muss man auch sagen, nicht jeder Graph hat einen fast 56:41.100 --> 56:42.500 perfekten Effekt des Matchings. 56:43.800 --> 56:48.320 Wir haben hier, wie wir sehen, fünf Knoten. 56:48.420 --> 56:51.940 Aha, sagt man sich, fünf Knoten, da bleibt einer übrig und die 56:51.940 --> 56:54.980 restlichen vier, die kann ich für ein Matching verwenden. 56:54.980 --> 56:58.680 Aber leider sind unsere Kanten so, dass ich genau ein einziges 56:58.680 --> 56:59.840 Matching unterbringen kann. 57:00.220 --> 57:02.180 Beispielsweise das da, dann ist schon Schluss. 57:07.220 --> 57:10.160 Also nicht jedes Problem eignet sich für ein besonders gutes Matching. 57:12.780 --> 57:17.720 So, jetzt sind wir ja schon erfahren und sagen, mit gierigen 57:17.720 --> 57:21.000 Algorithmen komme ich ja offenbar ziemlich schnell zum Ziel. 57:21.500 --> 57:22.540 Probieren wir es doch gleich mal wieder. 57:22.540 --> 57:27.600 Machen wir wieder einen gierigen Algorithmus, der jetzt zu uns ein 57:27.600 --> 57:28.720 solches Matching liefert. 57:29.300 --> 57:33.920 Dann machen wir Folgendes, wir wissen ja, dass wir unsere Kanten 57:33.920 --> 57:35.200 möglichst aufbrauchen wollen. 57:37.220 --> 57:40.060 Und wir können auch, statt die Knoten zu betrachten, einfach nur die 57:40.060 --> 57:41.520 benachbarten Kanten ansehen. 57:41.920 --> 57:45.360 Und einfach ansehen, bei der benachbarten Kante, ist sie schon 57:45.360 --> 57:46.500 gematched oder ist sie nicht gematched. 57:46.500 --> 57:52.360 Also, solange wir noch eine unmarkierte Kante in unserem Graph haben, 57:52.920 --> 57:53.480 machen wir weiter. 57:55.160 --> 57:58.820 Wir greifen uns eine Kante heraus, eine unmarkierte Kante, markieren 57:58.820 --> 57:59.040 die. 58:01.560 --> 58:05.800 Wir markieren alle benachbarten Kanten, weil wir wissen, dass die gar 58:05.800 --> 58:07.800 nicht mehr in Frage kommen, die dürfen wir gar nicht mehr verwenden. 58:09.800 --> 58:14.200 Und in unsere Markierung übernehmen wir diesen Knoten UV, diese Kante 58:14.200 --> 58:14.480 UV. 58:15.940 --> 58:21.360 Die Überlegung ist einfach, schnappt ihr eine Kante, guckt nach, ob 58:21.360 --> 58:22.120 sie markiert ist. 58:22.200 --> 58:24.640 Wenn sie nicht markiert ist, dann kann ich sie verwenden, dann geht 58:24.640 --> 58:26.760 sie in meine Markierung, in mein Matching ein. 58:27.080 --> 58:30.360 Aber gleichzeitig muss ich gleich die benachbarten Kanten markieren, 58:30.720 --> 58:32.960 weil die nicht mehr in Frage kommen. 58:33.160 --> 58:34.680 Die darf ich ja nicht mehr verwenden beim Matching. 58:38.220 --> 58:43.180 Also nehmen wir wieder unseren Knoten und wir fangen zum Beispiel so 58:43.180 --> 58:43.640 an. 58:45.420 --> 58:53.140 Dann ist schon klar, dass wir diese blauen Kanten, die dürfen schon 58:53.140 --> 58:54.400 gleich nicht mehr verwendet werden. 58:55.540 --> 58:57.480 So, der Rest kann auch verwendet werden. 58:57.480 --> 59:03.920 Also, nehmen wir jetzt beispielsweise die zweite rote Kante links und 59:03.920 --> 59:07.960 wir sehen, wie der Blau markiert, was jetzt schon alles markiert ist, 59:08.020 --> 59:11.100 zusätzlich zu unseren beiden roten Kanten. 59:11.400 --> 59:14.240 Aber die roten Kanten sind Teil des Matching und der Rest nicht. 59:15.420 --> 59:17.720 Und jetzt bleibt auch nicht viel übrig, jetzt haben wir nämlich genau 59:17.720 --> 59:18.660 noch zwei Kanten. 59:18.660 --> 59:26.720 Eine davon müssen wir verwenden für das Matching. 59:30.080 --> 59:33.080 Und, gut, jetzt haben wir mal die da verwendet, jetzt wird die andere 59:33.080 --> 59:34.060 eben nicht verwendet. 59:35.260 --> 59:39.980 Und jetzt sehen wir auch deutlich, wir haben kein perfektes Matching, 59:45.930 --> 59:49.890 sondern das gierige Verfahren funktioniert irgendwie nicht besonders 59:49.890 --> 59:50.190 gut. 59:52.350 --> 59:55.770 Man müsste jetzt vielleicht größere Graphen nehmen und nachsehen, wie 59:55.770 --> 59:58.330 nah ist man denn am perfekten Matching. 59:58.710 --> 01:00:01.070 Aber zumindest an dem Beispiel sieht man mal, dass ein gieriger 01:00:01.070 --> 01:00:03.750 Algorithmus, der bringt an der Stelle nicht viel, aber ich muss sagen, 01:00:03.830 --> 01:00:06.590 das ist auch ein schlechter gieriger Algorithmus, weil wir ja kein 01:00:06.590 --> 01:00:09.110 Kriterium hatten, nach dem wir sagen konnten, was ist denn das größte 01:00:09.110 --> 01:00:10.590 Stück überhaupt, das wir rauspicken sollen. 01:00:11.570 --> 01:00:14.930 Es gab gar kein größtes Stück, alle waren gleich groß und ein gieriger 01:00:14.930 --> 01:00:18.050 Algorithmus wird auch vermutlich nicht sonderlich gut funktionieren, 01:00:18.490 --> 01:00:21.210 wenn ich dem nicht unterschiedlich große Tropfenstücke anbiete. 01:00:25.140 --> 01:00:28.240 Maximales Matching ist es, aber es ist auch alles, was wir sagen 01:00:28.240 --> 01:00:28.480 können. 01:00:31.040 --> 01:00:39.860 Jetzt kommen wir mal zurück zu unserer Erkenntnis, dass wir, ja, wenn 01:00:39.860 --> 01:00:43.700 wir bei unserem Kreis sahen, dass wir im Grunde genommen, wenn wir ein 01:00:43.700 --> 01:00:49.320 Matching haben, auch unseren Pfad um eins versetzen können, um einen 01:00:49.320 --> 01:00:53.340 Knoten, und dann auch wieder ein Matching erhalten müssten. 01:00:55.840 --> 01:01:00.640 Wir können zunächst mal Folgendes sagen, um mit der Idee anzufangen. 01:01:01.420 --> 01:01:05.600 Zunächst mal, was wir beobachten, ist ja, wenn wir ein Matching 01:01:05.600 --> 01:01:08.340 verfolgen, dann können wir gewisse Pfade wieder ausmachen. 01:01:08.340 --> 01:01:13.380 Zum Beispiel können wir sicherlich in unserem Vorgänger hier, 01:01:16.900 --> 01:01:21.680 können wir Pfade ausmachen, zum Beispiel können wir einen Pfad 01:01:21.680 --> 01:01:23.340 ausmachen, wie diesen hier. 01:01:25.320 --> 01:01:31.900 Dieser Pfad, von dem können wir sagen, der beginnt mit einer Kante, 01:01:32.060 --> 01:01:35.620 die zum Matching gehört, dann kommt eine Kante, die nur markiert ist, 01:01:35.700 --> 01:01:38.120 aber nicht zum Matching gehört, dann kommt wieder eine Kante, die 01:01:38.120 --> 01:01:39.120 gematcht wird. 01:01:41.200 --> 01:01:45.580 Wir wollen mal einen solchen Pfad, bei dem immer abwechselnd eine 01:01:45.580 --> 01:01:49.440 gematchte und eine nicht gematchte Kante auftritt, den nennen wir 01:01:49.440 --> 01:01:51.260 einen tieralternierenden Pfad. 01:01:54.840 --> 01:01:57.140 Jetzt könnten wir noch etwas weiter gehen, wir könnten nämlich 01:01:57.140 --> 01:02:04.560 folgendermaßen sagen, wenn wir noch einen Schritt weiter gehen, dann 01:02:04.560 --> 01:02:22.790 sind hier, und wir verlängern den Pfad mal so, dann haben wir immer 01:02:22.790 --> 01:02:25.270 noch einen alternierenden Pfad, aber dieser alternierende Pfad 01:02:25.270 --> 01:02:29.390 unterscheidet sich jetzt von dem vorhergehenden, dass die Endkonten 01:02:29.390 --> 01:02:32.470 nicht gematcht sind. 01:02:34.430 --> 01:02:36.670 Und jetzt könnte man ja die Überlegung anstellen, die ich gerade 01:02:36.670 --> 01:02:40.550 vorhin genannt habe, wenn ich jetzt das Matching einfach verschiebe, 01:02:41.870 --> 01:02:44.630 das heißt alles, was bisher gematcht ist, ist nicht mehr gematcht, und 01:02:44.630 --> 01:02:47.790 umgekehrt, das was nicht gematcht war, schlage ich jetzt das Matching 01:02:47.790 --> 01:02:51.590 hinzu, dann sieht man deutlich, dann beginne ich jetzt mit einer 01:02:51.590 --> 01:02:54.730 gematchten Kante, dann kommt eine nicht gematchte, eine gematchte, 01:02:54.810 --> 01:02:56.230 eine nicht gematchte, wieder eine gematchte. 01:02:56.230 --> 01:02:58.310 Und plötzlich habe ich mehr Knoten im Spiel. 01:02:59.910 --> 01:03:03.910 Also halten wir das nochmal fest, und wir nennen folgendes jetzt einen 01:03:03.910 --> 01:03:08.430 alternierenden Pfad vergrößernd alternierend, da kann ich was damit 01:03:08.430 --> 01:03:12.690 machen, den kann ich vergrößern, wenn der alternierende Pfad keine 01:03:12.690 --> 01:03:14.350 gematchten Endknoten aufweist. 01:03:14.710 --> 01:03:18.290 Und jetzt sieht man schon, wo die Grundidee steckt, wir matchen 01:03:18.290 --> 01:03:20.710 einfach mal, aber dann schauen wir uns an, entstehen damit so 01:03:20.710 --> 01:03:21.590 alternierende Pfade. 01:03:22.510 --> 01:03:25.510 Und wenn wir alternierende Pfade haben, wenn wir plötzlich 01:03:25.510 --> 01:03:30.390 feststellen, da gibt es Knoten, da gibt es sozusagen vergrößernde 01:03:30.390 --> 01:03:34.630 alternierende Pfade, das heißt solche, die enden mit einer nicht 01:03:34.630 --> 01:03:39.590 gematchten Kante, die in einem nicht gematchten Knoten endet, dann 01:03:39.590 --> 01:03:42.450 kann ich vergrößern, dann kann ich auf jeden Fall auf jeden Fall mehr 01:03:42.450 --> 01:03:43.310 Matchings unterbringen. 01:03:45.550 --> 01:03:46.830 Also schauen wir uns das mal hier an. 01:03:47.630 --> 01:03:52.390 Was wir jetzt hier sehen ist beispielsweise, nehmen wir mal die beiden 01:03:52.390 --> 01:03:53.390 Knoten V und W. 01:03:55.790 --> 01:04:00.750 Und wir sehen schon mal folgendes, um von V nach W zu kommen, haben 01:04:00.750 --> 01:04:04.490 wir einen besonders langen Pfad, nämlich einer, der von V erstmal da 01:04:04.490 --> 01:04:08.710 links nach oben führt, dann geht er da hier entlang und kommt 01:04:08.710 --> 01:04:09.410 schließlich hier runter. 01:04:12.110 --> 01:04:15.710 Und das ist offensichtlich ein vergrößernder alternierender Pfad, also 01:04:15.710 --> 01:04:19.130 ein Pfad, alternierender Pfad, den wir noch vergrößern können. 01:04:20.730 --> 01:04:22.570 So, das hier auch noch mal blau gezeigt. 01:04:23.630 --> 01:04:26.690 Und für den gilt halt jetzt, dann vertauschen wir doch einfach die 01:04:26.690 --> 01:04:27.130 Matchings. 01:04:28.950 --> 01:04:32.290 Das, was ich vorhin gesagt habe, wenn wir die vertauschen, 01:04:35.590 --> 01:04:40.150 dann erhalte ich einen neuen, in dem das Matching größer geworden ist. 01:04:41.030 --> 01:04:43.810 Und jetzt gibt es also einen Satz, der uns da noch ordentlich zu Hilfe 01:04:43.810 --> 01:04:47.930 kommt, nämlich man kann sagen, wenn ich so ein Matching vor mir habe, 01:04:49.070 --> 01:04:55.230 dann ist das Maximum, wenn ich in diesem Matching keinen vergrößernd 01:04:55.230 --> 01:04:59.530 alternativen Pfad finde. 01:05:04.000 --> 01:05:07.560 Achso, da gibt es auch noch einen Beweis, der Beweis sagt folgendes. 01:05:09.760 --> 01:05:12.760 Nehmen wir mal an, wir hätten M als ein Maximum Matching. 01:05:15.100 --> 01:05:18.300 Und jetzt nehmen wir mal an, jetzt kommt der Widerspruchsbeweis, der 01:05:18.300 --> 01:05:22.880 Widerspruchsbeweis sagt, ja nehmen wir doch mal an, dass wir trotzdem, 01:05:23.240 --> 01:05:27.020 trotz dem Satz, einen vergrößernder alternativen Pfad von V finden. 01:05:27.020 --> 01:05:36.340 Nochmal zurück übrigens, der Satz von Berge sagt ja, genau dann wenn, 01:05:36.460 --> 01:05:38.300 das heißt wir müssen Beweise in beiden Richtungen führen. 01:05:38.920 --> 01:05:42.940 Also jetzt führen wir mal in der einen Richtung und nehmen also mal 01:05:42.940 --> 01:05:48.040 an, wir hätten ein M, das wäre ein Maximum Matching, aber Widerspruch, 01:05:48.780 --> 01:05:52.520 wir finden trotzdem in unserem Graph einen vergrößernd alternativen 01:05:52.520 --> 01:05:52.920 Pfad. 01:05:52.920 --> 01:06:09.630 Also beispielsweise so etwas und dann muss man ja sagen, dann können 01:06:09.630 --> 01:06:17.070 wir ja tatsächlich vertauschen, nämlich wir können das Matching ja 01:06:17.070 --> 01:06:17.630 vergrößern. 01:06:18.010 --> 01:06:20.550 Nämlich ganz einfach, indem wir nur diese Vertauschung vornehmen. 01:06:21.470 --> 01:06:24.970 Ja, aber dann war M ja offenbar kein Maximum Matching. 01:06:27.910 --> 01:06:34.390 Also Widerspruch, solange wir also in einem Graph, solange wir also 01:06:34.390 --> 01:06:39.270 Maximum Matching vorfinden darf, in unserem Graph dürfen wir keinen 01:06:39.270 --> 01:06:44.070 vergrößernd alternativen Pfad vorfinden. 01:06:45.010 --> 01:06:47.370 Jetzt ist aber noch die umgekehrte Frage auch interessant, nämlich 01:06:47.370 --> 01:06:52.290 wenn ich keinen vorfinde, bin ich dann auch sicher, dass ich Maximum 01:06:52.290 --> 01:06:52.870 Matching habe. 01:06:53.550 --> 01:06:55.410 Nicht perfekt, nur Maximum. 01:06:57.850 --> 01:07:00.150 Das ist jetzt das Ergebnis, das haben wir schon gehabt. 01:07:05.080 --> 01:07:06.260 Wir drehen mal den Spieß um. 01:07:09.920 --> 01:07:14.340 Wir nehmen jetzt mal an, wir hätten ein Matching und dieses Matching, 01:07:14.380 --> 01:07:17.520 wenn wir in den Graph zurückgehen, stellt sich heraus, hat einen 01:07:17.520 --> 01:07:19.100 vergrößernd alternierenden Pfad. 01:07:21.480 --> 01:07:26.200 So, jetzt wollen wir wissen, ob dann, dann dürfte auch kein Matching 01:07:26.200 --> 01:07:26.680 vorliegen. 01:07:27.800 --> 01:07:29.860 Weil kein Maximum Matching vorliegen. 01:07:31.040 --> 01:07:36.080 Nun, wir wissen ja, dass wir zunächst einmal ein neues Matching 01:07:36.080 --> 01:07:38.660 erzeugen können, indem wir diesen Pfad vergrößern. 01:07:38.920 --> 01:07:41.440 Wir verlängern ihn, so wie wir das hier vorhin hatten. 01:07:43.200 --> 01:07:46.720 Und jetzt nehmen wir mal folgendes an, wir haben also hier, das ist 01:07:46.720 --> 01:07:54.320 unsere Ausgangssituation und durch Vertauschen erhalten wir diese neue 01:07:54.320 --> 01:07:54.780 Situation. 01:07:55.040 --> 01:07:59.380 Also blau ist das M-Strich jetzt und das Rot ist das ursprüngliche M. 01:08:01.600 --> 01:08:04.600 Und übrigens kann man auch nachweisen, dass ein Zyklus selbst, den wir 01:08:04.600 --> 01:08:07.600 ja auch noch betrachten müssen, kein vergrößernd alternativer Pfad 01:08:07.600 --> 01:08:08.180 sein kann. 01:08:10.140 --> 01:08:14.560 So, und dann wissen wir aber, da wir, das M-Strich ja größer ist, das 01:08:14.560 --> 01:08:19.040 ist ein größeres Matching, kann infolgedessen M nicht Maximum sein. 01:08:21.760 --> 01:08:24.320 Also haben wir jetzt so auch die umgekehrte Richtung bewiesen. 01:08:24.840 --> 01:08:27.240 Es gilt, also da hat sich der Satz, wir brauchen es nur noch 01:08:27.240 --> 01:08:30.700 anzusehen, wir entfernen jetzt aus, wenn wir ein Matching 01:08:30.700 --> 01:08:35.960 konstruieren, dann entfernen wir einfach oder ersetzen alle Pfade, die 01:08:35.960 --> 01:08:39.780 vergrößernd alternierend sind, durch eine Umkonstruktion, indem wir 01:08:39.780 --> 01:08:42.920 genau Matching und Nicht-Matching-Kanten vertauschen. 01:08:43.960 --> 01:08:46.300 Und es wird uns am Ende garantiert, dass wir ein Maximum-Matching 01:08:46.300 --> 01:08:46.740 erreichen. 01:08:46.920 --> 01:08:50.140 Aber, was uns nicht garantiert wird, ist, dass es ein perfektes 01:08:50.140 --> 01:08:50.660 Matching ist. 01:08:50.720 --> 01:08:53.500 Kann immer noch sein, dass wir uns leider am Anfang so ungeschickt 01:08:53.500 --> 01:08:57.920 angestellt haben, dass wir eben immer noch Knoten übrig haben, die 01:08:57.920 --> 01:08:58.820 frei sind. 01:09:01.640 --> 01:09:04.060 So, nehmen wir mal dieses Beispiel hier. 01:09:06.960 --> 01:09:10.580 Nehmen wir mal für einen Augenblick an, wir hätten diese roten Kanten 01:09:10.580 --> 01:09:12.140 schon gefunden. 01:09:13.960 --> 01:09:20.160 Dann kann ich insbesondere ja hier drinnen einen Kantenzug von V nach 01:09:20.160 --> 01:09:24.580 W konstruieren, von dem her zu sehen, der schließt die roten Kanten 01:09:24.580 --> 01:09:28.400 ein, aber ist ein vergrößernd alternierender Pfad. 01:09:30.040 --> 01:09:32.020 Also, da vertauschen wir das einfach. 01:09:34.560 --> 01:09:36.260 Es ist kein Maximum-Matching. 01:09:37.100 --> 01:09:41.180 Und wenn wir es vergrößern, dann erhalten wir eben jetzt dieses 01:09:41.180 --> 01:09:41.820 Matching hier. 01:09:42.720 --> 01:09:45.100 Und wir sehen übrigens auch, dass jeder Knoten jetzt gematcht ist, 01:09:45.200 --> 01:09:46.000 mehr kann man nicht mehr machen. 01:09:46.400 --> 01:09:48.040 Das ist also sogar ein perfektes Matching. 01:09:51.280 --> 01:09:53.100 Wir hätten auch anders vorgehen können. 01:09:55.120 --> 01:10:02.880 Wir hätten nämlich, auch das ist ein vergrößernd alternativer Pfad. 01:10:03.340 --> 01:10:07.320 Der ist zwar etwas komplizierter oder sieht komplizierter aus, der 01:10:07.320 --> 01:10:10.240 geht nämlich von V erstmal hier hin und läuft dann da rum. 01:10:13.040 --> 01:10:18.200 Nun, wir können wieder sagen, es gibt also offensichtlich einen 01:10:18.200 --> 01:10:20.480 vergrößernd alternierenden Pfad. 01:10:20.480 --> 01:10:22.220 Infolge dessen ist es kein Maximum-Matching. 01:10:22.600 --> 01:10:23.540 Und jetzt machen wir das Gleiche. 01:10:23.760 --> 01:10:28.860 Wir vertauschen wiederum die Matching-Kanten mit Nicht-Matching-Kanten 01:10:28.860 --> 01:10:29.720 und umgekehrt. 01:10:30.320 --> 01:10:33.240 Und das Ergebnis ist jetzt dieses hier. 01:10:35.920 --> 01:10:38.660 Und wiederum ist das ein perfektes Matching. 01:10:38.740 --> 01:10:43.060 Und wir sehen ja deutlich, dass jeder Knoten an einer Matching-Kante 01:10:43.060 --> 01:10:44.100 beteiligt ist. 01:10:46.720 --> 01:10:48.780 Aber es ist ein anderes Matching. 01:10:49.940 --> 01:10:54.560 Wir sehen insbesondere auch, dass ein perfektes Matching für einen 01:10:54.560 --> 01:10:56.260 gegebenen Graph nicht eindeutig sein muss. 01:10:57.400 --> 01:10:59.820 Und solange wir keine anderen Kriterien haben, wie zum Beispiel noch, 01:10:59.960 --> 01:11:04.660 dass die Gewichte minimal sein sollen, ist auch jedes dieser Matching 01:11:04.660 --> 01:11:04.950 akzeptabel. 01:11:06.180 --> 01:11:11.260 Also wir halten fest, auch zu einem Graph kann es durchaus mehr als 01:11:11.260 --> 01:11:12.420 ein perfektes Matching geben. 01:11:17.180 --> 01:11:20.220 Hier ist noch ein drittes, dritte Variante. 01:11:21.600 --> 01:11:30.320 Ist auch ein, zunächst einmal, ein vergrößernd alternierender Pfad. 01:11:31.080 --> 01:11:33.080 Und jetzt machen wir wieder das Gleiche, wir vertauschen. 01:11:36.140 --> 01:11:40.720 Und es kommt wieder eine Lösung raus, die auch wieder perfekt ist. 01:11:42.680 --> 01:11:46.320 Das liegt euch jetzt in einem einfachen Graph, dass wir so schnell bei 01:11:46.320 --> 01:11:47.920 einem perfekten Matching angelangt sind. 01:11:52.020 --> 01:11:55.740 So, jetzt können wir uns einen Algorithmus überlegen, der jetzt auf 01:11:55.740 --> 01:11:57.100 dieser Basis arbeitet. 01:11:59.120 --> 01:12:01.860 Und dieser einfache Algorithmus geht folgendermaßen. 01:12:06.600 --> 01:12:11.320 Wir machen sowas wie eine Abstraktion. 01:12:12.820 --> 01:12:14.320 Wir sagen, es gibt zwei Teilprobleme. 01:12:16.320 --> 01:12:20.440 Und das erste Teilproblem ist das, finde erst einmal überhaupt mit 01:12:20.440 --> 01:12:23.640 irgendeinem einfachen Algorithmus ein maximales Matching. 01:12:27.480 --> 01:12:31.020 Das ist häufig so, man mag mal so einen schnellen Einstieg und dann 01:12:31.020 --> 01:12:33.800 macht man sich eine Verbesserung des so erzielten Ergebnisses. 01:12:34.180 --> 01:12:38.460 Der zweite Schritt besteht jetzt darin, dass wir, wir haben hier offen 01:12:38.460 --> 01:12:40.720 gelassen, wie wir das Problem lösen. 01:12:40.720 --> 01:12:43.160 Man kann sagen, es sind auch die beiden Konker, aber mit einer 01:12:43.160 --> 01:12:44.020 gewissen Abstraktion. 01:12:45.340 --> 01:12:50.240 Jetzt sagen wir folgendes, wir untersuchen jetzt das Matching und den 01:12:50.240 --> 01:12:54.850 Graph auf vergrößernd alternative Pfade. 01:12:56.960 --> 01:13:02.160 Greifen den ersten heraus, wenden den an, vertauschen jetzt diese M 01:13:02.160 --> 01:13:03.160 -Zubehörigkeit. 01:13:04.020 --> 01:13:06.860 Und dann gehen wir zurück und schauen, gibt es noch, jetzt müssen wir 01:13:06.860 --> 01:13:10.400 natürlich neu berechnen, die Alternative, die vergrößernd 01:13:10.400 --> 01:13:11.340 alternierenden Pfade. 01:13:12.160 --> 01:13:15.740 Aber greifen aus denen halt wieder einen heraus, solange bis eben 01:13:15.740 --> 01:13:16.820 keiner mehr vorhanden ist. 01:13:18.340 --> 01:13:21.220 Also das ist jetzt sehr abstrakt, da wenn Sie ja die Details machen, 01:13:21.300 --> 01:13:23.260 ist das schon ganz schön tückisch, da müssen Sie überall Buchführung 01:13:23.260 --> 01:13:23.400 machen. 01:13:25.820 --> 01:13:30.240 So, wir können also sagen, dass der Algorithmus führt jetzt demnach in 01:13:30.240 --> 01:13:32.000 jedem Schritt eine Kante zu M hinzu. 01:13:32.000 --> 01:13:34.240 Ist ja ganz klar, wenn wir vorher drei hatten, haben wir vier jetzt 01:13:34.240 --> 01:13:34.700 und so weiter. 01:13:36.580 --> 01:13:41.120 Wir wissen weiterhin, er terminiert, weil es nur endlich viele Kanten 01:13:41.120 --> 01:13:41.460 gibt. 01:13:42.120 --> 01:13:45.200 Das heißt, wir haben immer eine Größe, indem wir einfach die Zahl der 01:13:45.200 --> 01:13:50.300 verbleibenden Kanten prüfen, haben wir eine Größe, die monoton 01:13:50.300 --> 01:13:50.920 abnimmt. 01:13:51.080 --> 01:13:53.700 Und das wissen wir ja, das ist das Kriterium, um Terminierung zu 01:13:53.700 --> 01:13:54.040 bestimmen. 01:13:57.240 --> 01:14:00.320 Wenn er terminiert, hat er ein Maximum Matching gefunden, das wissen 01:14:00.320 --> 01:14:01.820 wir auch aus dem Satz von Berge. 01:14:05.370 --> 01:14:08.110 Wir wissen nichts darüber, ob es auch perfekt ist. 01:14:08.570 --> 01:14:11.270 Das ist noch die Frage, ob das vielleicht von diesem einfachen 01:14:11.270 --> 01:14:13.170 Algorithmus abhängt, von dem Start. 01:14:13.730 --> 01:14:17.210 Es gibt nämlich bei der Optimierung, bei der wir erst eine 01:14:17.210 --> 01:14:21.390 Anfangslösung produzieren und dann uns an die Optimierung machen, 01:14:21.490 --> 01:14:25.570 leider die ekelhafte Eigenschaft, dass es sehr stark davon abhängt, 01:14:26.210 --> 01:14:31.350 wie die Anfangslösung aussieht, um zu einer optimalen Lösung oder zu 01:14:31.350 --> 01:14:32.770 einer suboptimalen Lösung zu kommen. 01:14:32.770 --> 01:14:37.870 Das ist also der Verdacht, dass durchaus diese erste Lösung einen 01:14:37.870 --> 01:14:39.490 Einfluss hat. 01:14:40.250 --> 01:14:43.150 So, und jetzt wollen wir wissen, wie kommen wir überhaupt zu der 01:14:43.150 --> 01:14:43.970 Anfangslösung. 01:14:45.070 --> 01:14:46.270 Die müssen wir auch konstruieren. 01:14:49.190 --> 01:14:52.490 Das geht eigentlich sehr einfach. 01:14:54.950 --> 01:15:00.570 Und zwar folgendermaßen, wir erinnern uns, dass wir bei jedem 01:15:00.570 --> 01:15:01.870 bipartiten Graph vorliegen haben. 01:15:01.870 --> 01:15:07.690 Und ein bipartiter Graph, den können wir folgendermaßen organisieren, 01:15:08.250 --> 01:15:14.290 wir zeichnen zunächst einmal alle Knoten der einen Art auf und wir 01:15:14.290 --> 01:15:16.930 legen darunter einfach alle Knoten der zweiten Art. 01:15:19.150 --> 01:15:26.790 Und jetzt ziehen wir einfach zwischen Knoten A und Knoten B Kanten. 01:15:28.390 --> 01:15:35.010 Und zwar einfach, wir bilden ein einfaches Matching und wir haben 01:15:35.010 --> 01:15:37.590 natürlich die Kanten noch zwischen diesen Knoten gegeben, also in 01:15:37.590 --> 01:15:39.710 diesem Fall die hier gegeben und jetzt versuchen wir erstmal ein ganz 01:15:39.710 --> 01:15:40.970 einfaches Matching zu erzeugen. 01:15:41.090 --> 01:15:46.750 Wir fangen beispielsweise hier an, dann kommt die in Frage, dann 01:15:46.750 --> 01:15:50.930 wissen wir, dass hier dieser Knoten in Frage kommt, wir können zum 01:15:50.930 --> 01:15:52.850 Beispiel die hier nehmen oder die hier. 01:15:53.790 --> 01:15:57.190 Das ist eine gewisse willkürliche Auswahl, aber nach irgendeinem 01:15:57.190 --> 01:16:01.910 Verfahren bilden wir immer Paare zwischen den Knoten A und Knoten B. 01:16:07.650 --> 01:16:11.650 Jetzt gehen wir einen Schritt weiter, wir müssen jetzt natürlich auch 01:16:11.650 --> 01:16:15.230 die Nicht-Matching-Knoten einführen, wir wollen ja alternierende Pfade 01:16:15.230 --> 01:16:16.310 konstruieren. 01:16:17.150 --> 01:16:21.210 Also haben wir hier folgendes, wir haben jetzt nach oben gerichtet 01:16:21.210 --> 01:16:28.260 oder nach unten gerichtet zunächst mal die blauen Pfade, also die, die 01:16:28.260 --> 01:16:31.800 wir für das Matching verwendet haben und nach oben gerichtet die 01:16:31.800 --> 01:16:37.100 schwarzen Pfade, die nun zu den Nicht-Matching-Knoten gehören. 01:16:39.340 --> 01:16:47.700 Und jetzt versuchen wir einfach eine Suche, indem wir versuchen jetzt 01:16:47.700 --> 01:16:52.160 zum Beispiel per Tiefensuche in den ungematchten Knoten solche zu 01:16:52.160 --> 01:16:58.140 finden, die immer zwischen dem M-Strich und der Restmenge wechseln. 01:16:58.980 --> 01:17:02.460 Und wir hören auf, sobald ein ungematchter Knoten erreicht wird. 01:17:03.540 --> 01:17:05.220 Also schauen wir das mal gleich an. 01:17:07.920 --> 01:17:12.520 Wir gehen beispielsweise hoch, die erste Kante, stellen fest, da 01:17:12.520 --> 01:17:13.200 kommen wir nicht weiter. 01:17:14.880 --> 01:17:17.240 Die zweite können wir natürlich nicht durchlaufen, weil sie im 01:17:17.240 --> 01:17:18.820 Urzeigersinn ist. 01:17:20.460 --> 01:17:23.480 Dann die dritte können wir ziehen, der dritten folgen wir auch. 01:17:25.560 --> 01:17:30.480 Das heißt, wir laufen zunächst mal hier rüber, folgen dann... 01:17:32.740 --> 01:17:35.360 Halt, wir haben das V hier gewählt. 01:17:37.220 --> 01:17:38.860 Wir haben hier einen ungematchten Knoten. 01:17:39.180 --> 01:17:45.240 Wir gehen also hier hoch, laufen hier runter, laufen hier hoch, laufen 01:17:45.240 --> 01:17:47.460 wieder runter, laufen hier hoch, laufen hier runter 01:17:50.920 --> 01:17:52.460 und kommen dann... 01:17:54.180 --> 01:17:56.380 Wir können nicht hier hoch, weil der nicht gematched ist. 01:17:56.580 --> 01:17:58.500 Ja, man muss es noch genauer ansehen. 01:17:58.920 --> 01:18:00.840 Wir haben die drei Kanten gematched. 01:18:06.880 --> 01:18:07.740 Nee, die zwei. 01:18:13.180 --> 01:18:14.780 Wir können also hier Pfade konstruieren. 01:18:20.260 --> 01:18:22.500 Und Sie sehen, was wir hier jetzt haben. 01:18:22.500 --> 01:18:24.620 Vielleicht sollte man das nochmal genauer ansehen. 01:18:31.860 --> 01:18:33.740 Jetzt schauen wir das doch nochmal genauer an. 01:18:46.300 --> 01:18:47.920 Wir gehen nochmal hier los. 01:18:48.120 --> 01:18:50.280 Wir haben jetzt hier die Kanten gewählt. 01:18:50.600 --> 01:18:55.160 Wir wählen jetzt irgendwie willkürlich einen Knoten V, das ist in 01:18:55.160 --> 01:18:58.200 diesem Fall dieser Knoten hier. 01:18:59.640 --> 01:19:05.340 Und wir konstruieren jetzt von da an gehend einen ersten gematchten 01:19:05.340 --> 01:19:09.040 Pfad, alternierenden Pfad. 01:19:09.600 --> 01:19:13.220 Und dieser alternierende Pfad läuft also jetzt hier los. 01:19:13.940 --> 01:19:16.540 So, so, so, so. 01:19:22.380 --> 01:19:24.820 So, da enden wir an einem nicht gematchten. 01:19:25.120 --> 01:19:28.560 Jetzt wollen wir einen Schritt weiter gehen und sagen, aha, jetzt 01:19:28.560 --> 01:19:29.240 machen wir es alternierend. 01:19:31.100 --> 01:19:35.480 Wenn wir jetzt vergrößern, dann bedeutet die Vergrößerung folgendes. 01:19:35.560 --> 01:19:39.320 Jetzt wird das da ein gematchter Knoten. 01:19:40.020 --> 01:19:41.040 Das da wird einer. 01:19:44.020 --> 01:19:45.200 Und das da wird einer. 01:19:47.280 --> 01:19:49.300 So, und jetzt müssen wir halt noch durchgehen und sehen, finden wir 01:19:49.300 --> 01:19:50.780 noch weitere Knoten dieser Art. 01:19:52.940 --> 01:19:54.200 Und zwar, wir können jetzt weitergehen. 01:19:54.280 --> 01:19:56.740 Wir stellen nämlich jetzt fest, wir können wieder erweitern. 01:19:56.740 --> 01:20:03.120 Wir finden beispielsweise jetzt als nächstes das da und das da. 01:20:04.360 --> 01:20:05.620 Vertauschen also wieder. 01:20:07.920 --> 01:20:13.380 Und haben dann als nächstes die Situation, die sieht jetzt so aus, so. 01:20:17.800 --> 01:20:20.760 Das Dick ist der gematchte, der ist dünn. 01:20:20.760 --> 01:20:24.760 Dann haben wir wieder... 01:20:29.420 --> 01:20:30.640 Ne, umgekehrt. 01:20:31.340 --> 01:20:34.080 Umgekehrt, wir gelaufen ja in der Richtung durch. 01:20:47.260 --> 01:20:48.680 Den da müssen wir erst nehmen. 01:20:56.490 --> 01:20:58.850 Wir laufen erstmal den da ab, erwischen den hier. 01:20:59.330 --> 01:21:06.830 Ich überlege gerade noch, dass wir an der Stelle kein Maximum Matching 01:21:06.830 --> 01:21:07.290 erreichen. 01:21:10.330 --> 01:21:13.230 Und das bedrückt mich etwas, muss ich ehrlich zugeben. 01:21:14.810 --> 01:21:16.170 Das müssen wir doch nochmal durchspielen. 01:21:16.710 --> 01:21:18.990 Wie kriegen wir hier ein Maximum Matching? 01:21:23.480 --> 01:21:26.520 Ah, jetzt wird es... Sie sehen, ich kann mich auch selber aufs Kreuz 01:21:26.520 --> 01:21:27.700 legen, das habe ich auch gerade getan. 01:21:40.660 --> 01:21:45.320 Die Frage ist, wenn ich jetzt zunächst mal diese Markierung habe, an 01:21:45.320 --> 01:21:45.840 dieser Stelle. 01:21:47.520 --> 01:21:49.180 Meine Ausgangsmarkierung war die folgende. 01:21:50.500 --> 01:21:55.380 Das hier ist ein Pfad, der ist vergrößernd alternierend. 01:21:56.080 --> 01:21:57.580 Das sind hier die gematchten Kanten. 01:21:59.220 --> 01:22:01.640 Dann kann ich es erstmal vertauschen und dann kriege ich natürlich 01:22:01.640 --> 01:22:04.780 einen längeren alternierenden Pfad. 01:22:05.260 --> 01:22:06.780 Nur dummerweise, hier hänge ich fest. 01:22:07.740 --> 01:22:08.560 Hier komme ich nicht weiter. 01:22:10.260 --> 01:22:11.300 Hierüber komme ich noch. 01:22:12.640 --> 01:22:14.420 Wie kriege ich diese Knoten hier noch? 01:22:19.640 --> 01:22:21.360 Ah, aber ich habe noch einen zweiten. 01:22:22.260 --> 01:22:23.420 Den habe ich auch noch. 01:22:24.440 --> 01:22:26.100 Den kann ich auch noch konstruieren. 01:22:29.580 --> 01:22:34.420 Dann kriege ich den hier, kann den wieder vertauschen und kriege das 01:22:34.420 --> 01:22:34.620 hin. 01:22:35.400 --> 01:22:36.100 Doch, es funktioniert. 01:22:37.480 --> 01:22:44.640 Aber an der Stelle muss ich sicher sein, dass ich alle alternierenden 01:22:44.640 --> 01:22:45.500 Pfade konstruiere. 01:22:45.940 --> 01:22:55.900 Sie müssen nicht verkomplett sein, aber ich muss zumindest versuchen, 01:22:55.980 --> 01:22:57.400 so viele Knoten als möglich zu erwischen. 01:22:58.120 --> 01:22:58.900 Das ist hier nicht der Fall. 01:22:59.640 --> 01:23:01.140 Also dem Algorithmus muss noch etwas dazu. 01:23:03.160 --> 01:23:06.500 So, Sie sehen, man kann also schon dieses einfache Problem, wenn es 01:23:06.500 --> 01:23:08.920 nicht richtig durchdacht worden ist, wie von mir ganz offenbar nicht, 01:23:10.080 --> 01:23:12.800 dann erkennt man sofort, dass es doch etwas komplizierter ist. 01:23:12.800 --> 01:23:18.720 Und dass man sich noch genau überlegen kann, dass wir also das hätten 01:23:18.720 --> 01:23:19.900 einbeziehen müssen. 01:23:20.840 --> 01:23:22.040 Wenn wir das einbeziehen, dann haben wir gewonnen. 01:23:26.330 --> 01:23:30.910 So, also das, diese Anfangslösung brauchen wir unbedingt. 01:23:35.270 --> 01:23:38.990 Und wir haben infolgedessen hier einmal diese Seite und diese Seite zu 01:23:38.990 --> 01:23:39.410 betrachten. 01:23:39.410 --> 01:23:40.050 So. 01:23:44.910 --> 01:23:48.430 Ja, und damit bin ich jetzt mit dem Graph-Algorithmen auch schon 01:23:48.430 --> 01:23:48.690 durch. 01:23:49.410 --> 01:23:51.910 Wir können mal gleich schauen, was uns jetzt ins Haus steht. 01:23:53.190 --> 01:23:59.450 Nämlich, ja, ja, ja, ja, das... mal schauen... 01:24:01.010 --> 01:24:03.030 Schrittweise verfeinern, was das sein könnte. 01:24:06.610 --> 01:24:07.650 Ah, Algorithmenentwurf. 01:24:10.050 --> 01:24:10.770 Ha! 01:24:12.070 --> 01:24:14.690 Also eigentlich haben wir ja schon ein bisschen exerziert. 01:24:14.890 --> 01:24:18.930 Nicht gerade bei dieser letzten Lösung, bei der wir gesagt haben, zwei 01:24:18.930 --> 01:24:19.890 Teilprobleme. 01:24:20.670 --> 01:24:25.250 Nämlich einmal haben wir das mit der Anfangsmarkierung zu finden. 01:24:25.770 --> 01:24:32.310 Und anschließend müssen wir noch dann eine Maximumlösung finden. 01:24:32.310 --> 01:24:37.190 Da kann man ja sagen, das ist ja eigentlich, jedes der Teilprobleme 01:24:37.190 --> 01:24:39.310 haben wir auf eigene Weise gelöst. 01:24:42.310 --> 01:24:46.910 Und das schrittweise verfeinern, das sieht folgendermaßen aus. 01:24:50.480 --> 01:24:54.280 Wir zerlegen unser gesamtes Problem in Teilaufgaben. 01:24:56.240 --> 01:25:01.440 Wir entwickeln die Teilaufgaben auf wechselnden Stufen der 01:25:01.440 --> 01:25:02.160 Detaillierung. 01:25:04.920 --> 01:25:10.120 Und am Ende setzen wir nach irgendeinem Entwurfsmuster oder dem 01:25:10.120 --> 01:25:15.500 entsprechenden Entwurfsmuster die Einzellösungen zu den Gesamtlösungen 01:25:15.500 --> 01:25:15.920 zusammen. 01:25:17.020 --> 01:25:22.260 Das ist eigentlich das Entwurfsprinzip, das auch bei größerer Software 01:25:22.260 --> 01:25:24.080 angewendet werden muss. 01:25:24.960 --> 01:25:27.440 Und hier führe ich mal noch schnell vor, wie man das ja so 01:25:27.440 --> 01:25:28.320 vorzustellen hat. 01:25:30.300 --> 01:25:32.420 Da kann man auf verschiedene Weise vorgehen. 01:25:33.680 --> 01:25:38.860 Erste Möglichkeit, ich gebe mir ein Ziel vor und dann versuche ich von 01:25:38.860 --> 01:25:39.520 diesem Ziel auszugehen. 01:25:41.120 --> 01:25:45.260 Das heißt, wir haben eine Anforderungsanalyse, die wird immer durch 01:25:45.260 --> 01:25:46.740 das Pflichtenheft festgelegt. 01:25:47.240 --> 01:25:49.500 Dann nehmen wir unser Pflichtenheft und sagen, wir wollen mal das 01:25:49.500 --> 01:25:50.340 Problem lösen. 01:25:50.340 --> 01:25:58.000 Wir lösen das Problem, indem wir einfach Teillösungen fabrizieren und 01:25:58.000 --> 01:26:03.640 dann am Ende diese Teillösungen zusammensetzen zur Gesamtlösung. 01:26:05.120 --> 01:26:08.440 Leider funktioniert die Welt meistens nicht so. 01:26:09.980 --> 01:26:12.620 Sondern Sie müssen immer bedenken, Sie sitzen in einem Unternehmen 01:26:12.620 --> 01:26:17.760 oder Sie sind Softwareanbieter und jedes Mal neue Software zu 01:26:17.760 --> 01:26:18.820 entwickeln ist teuer. 01:26:20.180 --> 01:26:22.100 Besonders in der heutigen Zeit ist das sehr teuer. 01:26:22.700 --> 01:26:25.380 Sie schauen also um und sagen, ich habe doch schon eigentlich das 01:26:25.380 --> 01:26:27.820 Problem, kommt mir doch schon bekannt vor, das habe ich doch mal schon 01:26:27.820 --> 01:26:28.740 früher gelöst. 01:26:29.240 --> 01:26:31.600 Außerdem habe ich noch eine große Bibliothek von Lösungen. 01:26:32.140 --> 01:26:34.280 Also ist das Vorgehen eigentlich, man will ein bisschen anders 01:26:34.280 --> 01:26:34.920 vorgehen. 01:26:36.300 --> 01:26:40.680 Und zwar indem man sagt, ich will gerne schon vorhandene Lösungen 01:26:40.680 --> 01:26:40.980 nehmen. 01:26:41.200 --> 01:26:43.700 Also macht man folgendes, man kommt zu einer Anforderungsanalyse an 01:26:43.700 --> 01:26:49.280 und sagt, gucken wir mal, ob wir Teilprobleme identifizieren können, 01:26:49.520 --> 01:26:52.040 die wir schon mal irgendwann gelöst haben. 01:26:52.520 --> 01:26:56.580 Das heißt, wir zerlegen eigentlich ein Teilaufgaben, wir zerlegen so, 01:26:56.740 --> 01:27:01.260 dass wir Teilaufgaben identifizieren, für die wir schon Lösungen parat 01:27:01.260 --> 01:27:01.540 haben. 01:27:03.220 --> 01:27:06.180 Also nehmen wir, vermuten wir eigentlich eher, so was Teilaufgaben 01:27:06.180 --> 01:27:10.960 sind, setzen das zusammen, überprüfen auf Erfüllung, gucken nach und 01:27:10.960 --> 01:27:12.160 sehen, nicht alles erfüllt. 01:27:12.920 --> 01:27:17.340 Dann gehen wir wieder zurück und häufig bleiben natürlich noch 01:27:17.340 --> 01:27:20.460 Teilprobleme übrig, die noch nicht gelöst worden sind. 01:27:20.580 --> 01:27:23.640 Für die müssen wir dann noch eine jungfräuliche Lösung bestimmen. 01:27:25.500 --> 01:27:29.140 So, ich glaube an der Stelle, damit haben Sie erstmal einen Geschmack 01:27:29.140 --> 01:27:32.200 gekriegt, was uns am nächsten Montag bevorsteht, da machen wir dann 01:27:32.200 --> 01:27:32.500 weiter. 01:27:57.800 --> 01:28:03.480 Da vielleicht noch eine Bemerkung, wir geben jetzt gleich noch 01:28:03.480 --> 01:28:08.420 Bewertungsblätter aus, Sie haben ja anschließend noch Übung und in der 01:28:08.420 --> 01:28:11.520 Zeit dürfen Sie außerdem noch nebenher die Bewertungsbogen ausfüllen. 01:28:12.760 --> 01:28:13.840 Vielen Dank fürs Ausfüllen.