WEBVTT NOTE PGD027 – automatic transcript (Whisper large-v3, wav2vec2 alignment, Sortformer + speaker embeddings). Generated by tools/transcribe/pi3tx.py, may contain errors. 00:00:00.700 --> 00:00:01.632 Hallo zusammen, 00:00:01.682 --> 00:00:03.956 hier ist Pi ist genau 3 mit Folge 00:00:04.447 --> 00:00:06.852 27 und wieder über 00:00:06.852 --> 00:00:10.719 das Internet zugeschaltet sind meine Wenigkeit Thomas Kahle und am anderen Ende 00:00:10.719 --> 00:00:11.770 der Leitung. 00:00:12.566 --> 00:00:14.400 Petra Schwer, hallo. Hallo Petra. 00:00:15.302 --> 00:00:18.839 Hi Thomas. Ja, ist ja inzwischen schon Routine hier alles 00:00:19.811 --> 00:00:22.366 remote übers Internet zu steuern. 00:00:22.677 --> 00:00:23.400 Ich habe ein Thema mitgebracht. 00:00:23.400 --> 00:00:23.542 Ja, 00:00:23.542 --> 00:00:25.368 ich bin schon ganz gespannt. 00:00:25.901 --> 00:00:27.475 Habt ihr Schuhe geputzt am Samstag? 00:00:27.726 --> 00:00:31.136 Ja, sogar recht fleißig und es war auch erfolgreich. 00:00:31.136 --> 00:00:32.730 War was drin am nächsten Morgen. 00:00:33.042 --> 00:00:37.061 Ja, sehr gut. Wir auch. Der Nikolaus war da, ne? 00:00:38.435 --> 00:00:40.682 Du kennst doch sicher das Haus vom Nikolaus. 00:00:40.682 --> 00:00:44.884 Das Haus vom Nikolaus, das ist so ein Grafentheorie-Problem, oder? 00:00:45.015 --> 00:00:46.520 Man muss irgendwie so ein Haus malen … 00:00:46.520 --> 00:00:47.396 Ja, das ist erstmal so ein Häuschen, ne? 00:00:47.396 --> 00:00:48.050 Genau. 00:00:48.265 --> 00:00:50.650 Und man darf nicht absetzen. 00:00:51.400 --> 00:00:52.521 Genau, das ist so ein Häuschen, 00:00:52.521 --> 00:00:55.063 das ist im Prinzip unten ein Viereck mit einem X drin 00:00:55.063 --> 00:00:57.255 und dann hat das noch so ein Dach oben drauf. 00:00:57.826 --> 00:01:03.031 Und man muss das eben zeichnen, indem man jede Kante halt malt natürlich. 00:01:03.031 --> 00:01:07.805 Es ist ein Graf, wo man jede Kante einmal, genau einmal durchlaufen darf. 00:01:07.975 --> 00:01:10.227 Und man muss eben diese Hausfigur zeichnen. 00:01:11.278 --> 00:01:12.479 Genau, wieso funktioniert das denn? 00:01:12.479 --> 00:01:13.280 Wieso geht das denn? Ähm... 00:01:15.020 --> 00:01:21.155 Geht das? Ja, es geht. Ich versuche gerade mir zu überlegen, wie es geht. 00:01:21.225 --> 00:01:25.809 Also das ist ja, also wenn mich das jetzt mal meine mathematischen Kenntnisse... 00:01:25.809 --> 00:01:27.711 Ja, ich habe ja nicht gesehen, wie du es gemalt hast. 00:01:27.711 --> 00:01:30.333 Also das weiß ich ja nicht, ob du dich an die Regel gehalten hast. 00:01:30.333 --> 00:01:30.813 Er soll ich eins malen. 00:01:30.813 --> 00:01:32.565 Also ich halte gerade hier über Skype 00:01:33.416 --> 00:01:36.198 Thomas ein gemaltes Haus vom Nikolaus in die Kamera. 00:01:36.198 --> 00:01:37.739 Jeder weiß, wie das Haus vom Nikolaus aussieht. 00:01:37.739 --> 00:01:38.741 Jeder weiß, wie das Haus aussieht. 00:01:38.741 --> 00:01:41.597 Wie so ein Kind ein Haus malt, nur mit einem Kreuz statt einem kleinen Fenster. 00:01:41.597 --> 00:01:43.149 Ich muss hier spiegelverkehrt malen. 00:01:43.149 --> 00:01:44.798 Also ich fange hier links unten an. 00:01:44.798 --> 00:01:45.298 Ja. 00:01:46.146 --> 00:01:47.596 Dann gehe ich hier die Diagonale hoch. 00:01:47.596 --> 00:01:48.096 Ja. 00:01:49.121 --> 00:01:51.763 Dann gehe ich an der rechten Seite runter. 00:01:51.834 --> 00:01:52.377 Ja. Oh, 00:01:52.377 --> 00:01:54.232 ich sehe den Bus. Dann gehe ich die andere Diagonale hoch. 00:01:54.232 --> 00:01:55.428 Ja. Jetzt das Dach. 00:01:56.023 --> 00:01:58.010 Dann mache ich das Dach, dann gehe ich oben quer, 00:01:58.010 --> 00:02:00.378 dann gehe ich rechts runter und dann muss ich nur unten den Boden zerrecken. 00:02:00.378 --> 00:02:02.033 Okay, also Petra hat es gelöst. 00:02:02.404 --> 00:02:04.477 Ich bin Zeuge. Und 00:02:05.068 --> 00:02:07.292 also wenn ich jetzt mal mathematisch darüber nachdenke, 00:02:07.292 --> 00:02:11.970 dann ist das ein Graph, also so ein Bild, was aus Ecken und Kanten besteht. 00:02:13.001 --> 00:02:16.691 Ecken, wir nennen die Punkte, nennen wir Ecken, wo sich so Kanten, 00:02:16.691 --> 00:02:17.654 und die Striche nennen wir Kanten. 00:02:17.654 --> 00:02:18.035 Genau. 00:02:18.035 --> 00:02:19.781 Und die Verbindungsstriche sind Kanten, genau. 00:02:19.781 --> 00:02:24.979 Und die, was Petra gemacht hat, ist, sie ist jede Kante einmal abgelaufen, 00:02:25.711 --> 00:02:30.629 ohne eine Kante zweimal zu benutzen und war am Ende wieder bei dem … 00:02:31.382 --> 00:02:32.698 Nee, warst du bei dem gleichen Punkt? 00:02:32.931 --> 00:02:34.101 Nee. Nee, muss nicht. 00:02:34.101 --> 00:02:35.344 Ich war nicht bei dem gleichen Punkt. 00:02:35.344 --> 00:02:36.686 Kann man das gleiche … Muss man nicht. 00:02:36.686 --> 00:02:38.069 Ich hab nur das Haus gezeichnet, ne? 00:02:38.069 --> 00:02:39.802 Also ich hab das Haus fertig gezeichnet. 00:02:40.194 --> 00:02:42.047 Genau, ich war nicht beim gleichen Punkt. 00:02:42.378 --> 00:02:43.109 Könnte ich denn? 00:02:44.521 --> 00:02:47.235 Du stellst Fragen. Nee, das geht nicht, weil … 00:02:47.265 --> 00:02:50.159 weil das geht nicht, weil das ist ja dieses … 00:02:50.370 --> 00:02:51.491 das kennt ja jeder, dieses Argument. 00:02:51.491 --> 00:02:54.756 Nee, nicht jeder, aber das ist bekannt, weil an dem jeden die Werte … 00:02:54.756 --> 00:02:57.930 es gibt ja so Vertizes mit drei, wo drei Kanten rausgehen. 00:02:58.622 --> 00:03:02.282 Und wenn du da rausgehst und wieder reinkommst und nochmal rausgehst … 00:03:03.056 --> 00:03:04.522 Kann ich nicht mehr reinkommen, ne? 00:03:04.522 --> 00:03:05.445 Kannst du nicht mehr reinkommen. 00:03:05.445 --> 00:03:08.293 Aber es gibt ja oben, das Dach hat nur zwei Nachbarn. 00:03:08.293 --> 00:03:11.070 Also eigentlich könntest du es vielleicht doch schaffen oder nicht? 00:03:11.121 --> 00:03:13.967 Nee, könnte ich nicht schaffen, weil ich müsste ja tatsächlich, 00:03:13.967 --> 00:03:17.723 wenn ich in derselben Ecke starte und ende, 00:03:18.495 --> 00:03:21.330 dann gehe ich da gleich oft raus wie rein. 00:03:21.388 --> 00:03:22.510 Ja, das stimmt. 00:03:22.861 --> 00:03:25.809 Bei der Start- und Endecke, bei jeder anderen Ecke aber auch. 00:03:25.809 --> 00:03:27.794 Ja, wenn ich ankomme, ich darf da ja nicht enden, 00:03:27.794 --> 00:03:30.024 weil ich ja wieder bei meiner Startecke enden muss. 00:03:30.024 --> 00:03:31.456 Reinkommen, rausgehen, erstmal jede Ecke, natürlich. 00:03:31.456 --> 00:03:31.821 Also muss ich da 00:03:31.821 --> 00:03:32.702 ja auch wieder raus. 00:03:32.702 --> 00:03:36.307 Ja, also ist jede Ecke muss gerade viele Kanten dran haben, 00:03:36.307 --> 00:03:38.559 also man nennt das geraden Eckengrad haben. 00:03:39.130 --> 00:03:43.145 Und ich kann nur dann in derselben Ecke anfangen und enden, 00:03:43.496 --> 00:03:46.950 wenn alle Ecken geraden Eckengrad haben. 00:03:47.167 --> 00:03:49.661 Ja, also … Man müsste sich jetzt … 00:03:49.661 --> 00:03:49.881 Genau, 00:03:49.881 --> 00:03:53.083 zusätzlich will ich ja noch, dass ich jede Kante nur einmal benutze, ne? 00:03:53.083 --> 00:03:55.786 Also das, das ist aber eine Bedingung, die sozusagen egal ist. 00:03:55.786 --> 00:03:59.329 Da gibt es diesen eulerschen Satz, der, der eben gesagt, 00:03:59.329 --> 00:04:02.181 wenn jede Ecke gerade viele Kanten, 00:04:03.072 --> 00:04:07.845 an jede Ecke gerade viele Kanten angrenzen, dann gibt es genau so einen Weg, 00:04:08.076 --> 00:04:13.630 der im selben Punkt startet und endet und jede Kante genau einmal benutzt. 00:04:13.720 --> 00:04:15.862 Okay, also ich, das ist, bringe ich immer durcheinander. 00:04:15.862 --> 00:04:17.704 Also wir können ja mal die Fachbegriffe sagen. 00:04:17.704 --> 00:04:20.026 Also es gibt, das nennt man dann Eulerschen Kreis. 00:04:20.026 --> 00:04:24.150 Genau. Und Eulerscher Kreis, das ist, gibt es ein einfaches Kriterium, das, 00:04:24.150 --> 00:04:26.542 was du gerade gesagt hast, ob das geht. 00:04:26.732 --> 00:04:27.433 Und aber. 00:04:27.433 --> 00:04:30.205 Genau, das ist dieser Satz, den ich gerade gesagt habe. 00:04:31.277 --> 00:04:35.110 Das, was wir hier suchen, ist ein sogenannter offener Euler Zug. 00:04:36.020 --> 00:04:36.441 Ah ja. 00:04:36.441 --> 00:04:37.723 Er hat eben die Bedingung, 00:04:37.723 --> 00:04:42.240 dass er irgendwo startet und potenziell woanders endet, 00:04:42.551 --> 00:04:47.742 aber auch jede Kante genau einmal benutzt und die komplette Figur zeichnet. 00:04:47.742 --> 00:04:51.721 Genau, weil ein Euler Kreis hat nach deinem Satz das Haus vom Nikolaus ja nicht. 00:04:52.012 --> 00:04:54.438 Weil es hat ja diese, am Boden diese Dreiervertizes. 00:04:54.438 --> 00:04:55.420 Genau, nach meinem Satz gibt's die nicht, ne? 00:04:55.420 --> 00:04:59.663 Die Vertizes, wo drei Kanten die Kantengrad, die Grad 3 haben. 00:05:00.416 --> 00:05:02.270 Genau, das kann's hier nicht geben. 00:05:02.842 --> 00:05:05.775 Das ist entstanden im Rahmen von diesem Königsberger Brückenproblem, ne? 00:05:05.775 --> 00:05:06.884 Das sagt sicher was. 00:05:06.884 --> 00:05:09.510 Ja. Die ganze Grafentheorie, meinst du? 00:05:09.862 --> 00:05:11.537 Nein, dieser Euler-Satz. 00:05:12.150 --> 00:05:13.374 Die Grafentheorie weiß ich nicht, 00:05:13.374 --> 00:05:14.859 ob die aus dem Euler-Königsberger Brückenproblem entstanden ist. 00:05:14.859 --> 00:05:15.744 Sagt man das nicht immer so? 00:05:15.744 --> 00:05:19.213 Ich glaube doch, das ist das erste grafentheoretische Problem. 00:05:19.213 --> 00:05:22.170 Ob man im Königsberg, Königsberg hat sieben Brücken. 00:05:22.501 --> 00:05:23.965 Ob man da so einen Spaziergang machen kann, 00:05:23.965 --> 00:05:29.498 der jede Brücke einmal beschreitet und dann wieder, das ist mal wieder da, 00:05:29.498 --> 00:05:30.463 wo man angefangen hat. 00:05:30.463 --> 00:05:33.917 Und es geht eben nicht, weil es da so einen Vertex gibt, oder? 00:05:33.917 --> 00:05:34.729 Wie war die Lösung? 00:05:34.781 --> 00:05:36.826 Ich glaube, es ging nicht oder es ging nicht, 00:05:36.826 --> 00:05:39.652 bevor irgendwelche Brücken zerstört wurden oder so. 00:05:39.652 --> 00:05:40.715 Inzwischen geht es vielleicht. 00:05:40.715 --> 00:05:42.298 Oder andersrum. Irgendwie gab es da jedenfalls. 00:05:42.298 --> 00:05:42.950 Nee, 00:05:42.950 --> 00:05:43.505 sowas. 00:05:44.481 --> 00:05:46.527 früher mehr oder weniger Brücken als heute, 00:05:46.527 --> 00:05:49.174 deshalb ist es glaube ich nicht eindeutig. 00:05:49.174 --> 00:05:50.842 Man muss eine Jahreszahl festlegen. 00:05:50.842 --> 00:05:55.009 Man muss diese alte Karte von Königsberg nehmen, die 00:05:57.020 --> 00:05:59.923 auf Wikipedia zu sehen ist, wo die so gemalt ist. 00:05:59.923 --> 00:06:00.923 Und da sind sieben Brücken. 00:06:00.923 --> 00:06:04.286 Genau, da gibt es so eine alte Karte, wir können die verlinken, 00:06:04.286 --> 00:06:07.988 von Königsberg und Euler ist da eben rumspaziert und hat sich das gefragt. 00:06:07.988 --> 00:06:14.983 Das war so 18. Jahrhundert, hat sich tatsächlich mit diesem Problem beschäftigt. 00:06:15.013 --> 00:06:20.557 Genau. Was auch lustig ist, ich habe das mal nachgeguckt, 00:06:20.557 --> 00:06:21.098 was schätzt du, 00:06:21.098 --> 00:06:24.730 wie viele Möglichkeiten es gibt, dieses Haus vom Nikolaus zu zeichnen? 00:06:25.541 --> 00:06:26.966 Also eine habe ich dir ja vorgemacht, 00:06:26.966 --> 00:06:31.230 das hat jetzt natürlich niemand gesehen, höchstens mitgehört und mitgezeichnet. 00:06:31.342 --> 00:06:35.350 Das ist ja ein interessantes Zählproblem. 00:06:35.350 --> 00:06:37.374 Also diese Zählprobleme in der Grafentheorie, 00:06:37.374 --> 00:06:40.322 die können halt manchmal ganz schwer und manchmal ganz einfach sein. 00:06:40.322 --> 00:06:44.830 Und ich soll jetzt raten, wie viele es bei genau diesem Haus vom Nikolaus gibt. 00:06:44.830 --> 00:06:48.908 Das gibt sieben Vertizes, ich zähle mal die Anzahl der Kanten, 1, 2, 3, 4, 5, 6. 00:06:50.721 --> 00:06:53.087 Sieben Kanten auch, habe ich richtig gezählt? 00:06:53.087 --> 00:06:56.606 Ne, acht Kanten. 1, 2, 3, 4, 5, 6, 7, 8 Kanten. 00:06:58.542 --> 00:07:00.568 Also die würden wir jetzt in irgendeine Ordnung bringen. 00:07:00.568 --> 00:07:02.354 Also ist irgendwie eine obere Schranke für die Zahl, 00:07:02.354 --> 00:07:04.670 die ich raten will, ist acht Fakultät. 00:07:05.200 --> 00:07:07.102 Und acht Fakultät ist natürlich eine ziemlich große Zahl, 00:07:07.102 --> 00:07:09.073 von der ich jetzt gar nicht weiß, wie groß die ist. 00:07:09.163 --> 00:07:10.544 Deswegen rate ich jetzt… Eine sehr grobe Schätzung, 00:07:10.544 --> 00:07:12.606 ne? Weil du musst ja die Kanten hintern… 00:07:12.606 --> 00:07:13.266 Also du brauchst 00:07:13.266 --> 00:07:17.330 ja eine Sequenz von acht… Ja, ja, es muss halt viel, viel weniger sein, 00:07:17.330 --> 00:07:23.124 also als acht Fakultät. Deswegen rate ich mal hundertfünfzehn. 00:07:24.575 --> 00:07:26.477 Ist gar nicht so weit weg tatsächlich. 00:07:26.477 --> 00:07:29.629 Ja. Es sind achtenachtzig. 00:07:30.079 --> 00:07:31.150 Achtentachtzig. 00:07:31.180 --> 00:07:33.622 Genau. Also man kann die, eine Möglichkeit, 00:07:33.622 --> 00:07:37.385 wie man sich das überlegen kann, ist einfach auflisten. 00:07:37.385 --> 00:07:39.296 Ja, also wir hatten ja ganz am Anfang schon gesagt, 00:07:39.547 --> 00:07:40.657 die müssen alle links, 00:07:40.687 --> 00:07:44.730 die müssen alle in einer der Ecken starten mit dem ungeraden Eckengrad, 00:07:44.730 --> 00:07:46.602 also links unten oder rechts unten. 00:07:47.012 --> 00:07:48.403 Ja, weil das die sind, 00:07:48.613 --> 00:07:52.626 wo man, einer davon muss man loslaufen und einer davon endet man. 00:07:52.937 --> 00:07:53.637 Weil alle anderen. 00:07:53.637 --> 00:07:54.247 Ach echt? Nein. 00:07:54.498 --> 00:07:54.998 Doch. 00:07:54.998 --> 00:07:57.840 Die müssen links unten oder rechts unten starten. 00:07:57.840 --> 00:08:01.194 Ja, wenn du woanders startest, hast du eine Ecke mit geradem Eckengrad 00:08:01.705 --> 00:08:04.227 und dann hast du schon verloren, 00:08:04.227 --> 00:08:08.902 weil da musst du raus, rein, raus und wieder rein und das kann nicht gehen. 00:08:09.974 --> 00:08:10.735 Ja, weil du kannst, 00:08:10.735 --> 00:08:11.656 also wir hatten uns ja überlegt, 00:08:11.656 --> 00:08:13.918 du kannst nicht in derselben Ecke starten wie aufhören, 00:08:13.918 --> 00:08:15.870 weil es gibt keinen Eulerkreis. 00:08:16.882 --> 00:08:18.371 Aha, sonst gäbe es einen Eulerkreis? 00:08:18.371 --> 00:08:19.685 Hm, ja, stimmt, du hast recht. 00:08:19.685 --> 00:08:20.655 Sonst gäbe es einen Eulerkreis? 00:08:20.655 --> 00:08:21.503 Das ist ja ein guter, 00:08:21.503 --> 00:08:23.519 das ist schon mal ein guter Tipp für alle, die dieses, 00:08:23.670 --> 00:08:27.242 vor diesem Problem stehen, immer links unten oder rechts unten anfangen. 00:08:27.242 --> 00:08:29.829 Genau, also immer in links unten oder rechts unten anfangen, 00:08:29.829 --> 00:08:31.133 sonst geht's schon mal schief. 00:08:31.133 --> 00:08:34.030 Also wenn man oben am Dach anfangen will, wird nicht klappen. 00:08:34.160 --> 00:08:36.182 Und es hat ja so eine Spiegelsymmetrie quer durch 00:08:36.182 --> 00:08:37.893 das Haus einmal von oben nach unten. 00:08:37.983 --> 00:08:39.304 Das heißt, es ist eigentlich auch egal, 00:08:39.304 --> 00:08:40.244 ob links unten oder rechts unten. 00:08:40.244 --> 00:08:42.826 Genau, also eigentlich sind es nicht 88, sondern nur 44 Möglichkeiten, 00:08:42.826 --> 00:08:45.978 wenn man sozusagen Modulo Spiegelung das betrachtet. 00:08:46.809 --> 00:08:49.831 Ja, weil, also wenn du links unten anfängst und eine Möglichkeit malst, 00:08:49.831 --> 00:08:54.084 kannst du ja die gespiegelte Variante malen, die kriegst du geschenkt. 00:08:54.435 --> 00:08:54.945 Ja. 00:08:55.776 --> 00:08:56.886 Und dann hast du nur noch, 00:08:56.937 --> 00:08:59.278 wenn du die als sozusagen eine Lösung betrachtest, 00:08:59.278 --> 00:09:01.000 dann sind es nur noch 44 Möglichkeiten. 00:09:01.000 --> 00:09:03.611 Möglichkeiten. Genau. 00:09:03.661 --> 00:09:05.082 Aber die könnte man einfach auflisten, 00:09:05.082 --> 00:09:07.494 indem man die Ecken alle nummeriert von 1 bis 5 00:09:07.504 --> 00:09:09.146 und dann einfach so Sequenzen hinschreibt. 00:09:09.146 --> 00:09:11.057 Sagen wir mal 1 ist ganz links unten, 00:09:11.087 --> 00:09:16.792 die 5 ist rechts unten und die anderen Ecken sind halt irgendwie 2, 3, 4 nummeriert. 00:09:16.792 --> 00:09:19.915 Vielleicht einfach so im Kreis. 00:09:19.915 --> 00:09:20.995 Dann kannst du die einfach aufschreiben. 00:09:20.995 --> 00:09:22.517 Das sind irgendwelche Zahlenfolgen, 00:09:22.517 --> 00:09:26.690 die mit 1 anfangen und mit 5 aufhören und die kannst du einfach enumerieren. 00:09:26.821 --> 00:09:27.833 Und dann gibt es eben 00:09:28.886 --> 00:09:32.456 88 Möglichkeiten, wo es klappt und. 00:09:32.456 --> 00:09:34.210 Ich würde immer die Kanten nehmen. 00:09:35.384 --> 00:09:37.816 Du kannst halt die Eckennummern einfach aufschreiben der Reihe nach, 00:09:37.816 --> 00:09:38.361 in welcher Kante es läuft. 00:09:38.361 --> 00:09:41.648 Aber wenn ich von links unten zur Spitze vom Dach, ist ja keine Kante. 00:09:41.648 --> 00:09:44.194 Also dann gibt es noch irgendwie zusätzliche kombinatorische Regeln, 00:09:44.194 --> 00:09:46.829 welche ich gar nicht beschreiten darf, weil da keine Kante ist. 00:09:46.972 --> 00:09:48.583 Genau. Die fliegen auch noch raus. 00:09:48.583 --> 00:09:49.305 Okay, aber das. 00:09:49.305 --> 00:09:51.470 Ja, das muss man halt einmal überprüfen, sozusagen, 00:09:51.470 --> 00:09:55.221 ob das eine legale Reihenfolge ist. 00:09:55.221 --> 00:09:57.736 Also man würde das Problem sozusagen brute force 00:09:58.368 --> 00:10:01.034 leicht mit einem kleinen Computerprogramm lösen können, 00:10:01.034 --> 00:10:03.621 indem man diese Folgen abzählt. 00:10:03.621 --> 00:10:04.002 Genau. 00:10:04.002 --> 00:10:06.529 Aber ist das, gibt es da einen Satz? 00:10:06.529 --> 00:10:07.772 Skaliert das irgendwie schön? 00:10:07.772 --> 00:10:10.438 Also wenn ich jetzt zum Beispiel so ein großes Haus vom Nikolaus nehme, 00:10:10.438 --> 00:10:11.229 wo da irgendwie 00:10:11.841 --> 00:10:12.603 mehrere Etagen oder so. 00:10:12.603 --> 00:10:16.302 Gibt es da nicht auch mehrere Etagen oder wenn da noch ein Fenster wäre oder so? 00:10:16.392 --> 00:10:18.959 Oder gibt es nicht dieses, wenn da so zwei nebeneinander stehen oder so? 00:10:18.959 --> 00:10:19.182 Genau, 00:10:19.182 --> 00:10:22.138 kommen wir gleich mit dem Weihnachtsmann, der nebenan wohnt, ne? 00:10:22.369 --> 00:10:24.563 Kennst du auch? Und nebenan der Weihnachtsmann. 00:10:24.614 --> 00:10:27.570 Dann will man noch so ein zweites, identisches daneben malen. 00:10:28.180 --> 00:10:28.751 Okay. 00:10:29.522 --> 00:10:31.503 Eine Sache wollte ich noch sagen zu den Möglichkeiten. 00:10:31.503 --> 00:10:33.025 Ich habe es nicht selber nachgeprüft, 00:10:33.025 --> 00:10:34.847 aber auf irgendeiner Webseite habe ich gefunden, 00:10:34.847 --> 00:10:37.109 es gibt anscheinend nur zehn Möglichkeiten zu scheitern, 00:10:37.109 --> 00:10:43.084 wenn man links unten anfängt. Also die sozusagen in vier von fünf Fällen. 00:10:43.154 --> 00:10:45.897 Ist gut für Leute, die einfach erst mal gern probieren wollen. 00:10:45.897 --> 00:10:47.098 Genau, muss man nicht nachdenken, 00:10:47.098 --> 00:10:49.290 sondern einfach probieren, dann wird es schon klappen. 00:10:49.701 --> 00:10:51.802 Genau, aber jetzt zu dem Weihnachtsmann, der nebenan wohnt. 00:10:51.802 --> 00:10:52.543 Also wenn man sozusagen 00:10:52.543 --> 00:10:56.547 das identische Häuschen mit geteilter Wand so als Doppelhaushälfte 00:10:56.547 --> 00:10:58.198 nochmal nebendran setzt. 00:10:58.428 --> 00:11:01.011 Ja, gibt's ja diesen, den Spruch geht dann irgendwie weiter, 00:11:01.011 --> 00:11:02.422 dass nebenan der Weihnachtsmann wohnt. 00:11:02.932 --> 00:11:05.845 Da könnte man sich ja genauso fragen, gibt's da einen Euler, 00:11:06.115 --> 00:11:08.317 einen offenen Eulerzug, der das abmalt? 00:11:08.317 --> 00:11:11.530 Also gibt's eine Möglichkeit, diese beiden Häuser 00:11:14.482 --> 00:11:17.373 mit einem Strich zu zeichnen, ohne dass man absetzen muss. 00:11:17.373 --> 00:11:18.948 Es gibt immer noch Ecken von Grad 3. 00:11:19.763 --> 00:11:20.846 Genau, es gibt wieder links, 00:11:20.846 --> 00:11:24.589 unten und ganz rechts sozusagen jetzt zwei Ecken von Grad 3. 00:11:25.943 --> 00:11:29.214 Aber wir haben jetzt noch zwei Ecken mit ungeradem Eckengrad, 00:11:29.214 --> 00:11:31.230 nämlich die an der geteilten Hauswand. 00:11:32.529 --> 00:11:33.406 Die haben Grad 5. 00:11:35.001 --> 00:11:39.354 Eins, zwei, drei, vier, fünf, sechs, sieben hat sogar eine und die untere hat fünf. 00:11:39.354 --> 00:11:40.056 Sieben, die Dächer, 00:11:40.056 --> 00:11:41.119 genau, und die untere hat fünf. 00:11:41.119 --> 00:11:45.177 Die Dächerverbindung hat sieben und die untere hat fünf. 00:11:45.177 --> 00:11:46.190 Ist das schlecht? 00:11:47.825 --> 00:11:48.168 Ja. 00:11:48.168 --> 00:11:50.090 Vorher hatten wir zwei, jetzt haben wir vier. 00:11:51.580 --> 00:11:52.642 Das ist sehr schlecht, 00:11:52.642 --> 00:11:58.291 weil so ein Eulerzug, da gibt's auch einen Satz, den kann es nur geben, 00:11:58.291 --> 00:12:00.235 wenn es höchstens zwei, 00:12:00.235 --> 00:12:03.364 also wenn es zwei Ecken von ungeradem Eckengrad nur höchstens gibt. 00:12:03.364 --> 00:12:06.090 Eine ist die Startecke und das andere ist die Endecke. 00:12:06.542 --> 00:12:10.461 Genau, weil jede andere Ecke musst du ja sozusagen besuchen und wieder gehen 00:12:10.873 --> 00:12:13.923 und dann brauchst du aber geraden Eckengrad. 00:12:13.923 --> 00:12:17.496 Wir haben hier vier Ecken mit ungeradem Eckengrad. 00:12:17.496 --> 00:12:22.439 Wenn wir jetzt aber eine davon als Startecke nehmen und eine als Endecke nehmen, 00:12:22.630 --> 00:12:24.295 die dürfen ungeraden Eckengrad haben. 00:12:24.295 --> 00:12:26.350 Ja, die anderen unterwegs nicht. 00:12:26.642 --> 00:12:27.836 Genau, die nicht. 00:12:27.887 --> 00:12:29.171 Das wird dann nicht funktionieren, 00:12:29.171 --> 00:12:31.523 weil du musst ja jede Ecke besuchen und wieder verlassen. 00:12:31.523 --> 00:12:34.190 In jede rein, aus jeder raus. Gleich oft. 00:12:34.382 --> 00:12:35.926 Gleich, ja nicht gleich oft. 00:12:35.926 --> 00:12:38.193 Eine kannst du vielleicht zweimal besuchen, die andere dreimal, 00:12:38.193 --> 00:12:40.100 aber du musst jedenfalls eine gerade Anzahl. 00:12:40.100 --> 00:12:40.582 Ne, 00:12:40.582 --> 00:12:43.332 ich meine an einer Ecke sozusagen musst du genauso oft rausgehen 00:12:43.332 --> 00:12:45.930 wie da rein gegangen bist, sonst bist du ja da geblieben. 00:12:46.040 --> 00:12:49.854 Genau, das, ja. Genau, also das gibt's nicht, ja. 00:12:49.964 --> 00:12:53.797 Da gibt's auch einen Satz zu, dass wenn man so einen planaren Grafen hat, 00:12:54.008 --> 00:13:00.163 dass der dann so einen offenen Eulerzug hat, wenn er höchstens zwei Ecken hat, 00:13:00.454 --> 00:13:02.946 die ungeraden Eckengrad haben. 00:13:03.517 --> 00:13:06.280 Sonst kann das nicht funktionieren. 00:13:06.280 --> 00:13:07.671 Okay. Okay. Prima. 00:13:07.841 --> 00:13:11.146 Also kann man eigentlich mit diesen Sätzen immer genau für jedes Haus 00:13:11.146 --> 00:13:13.078 vom irgendwelchen 00:13:14.351 --> 00:13:17.715 real existierenden Weihnachtskarakter entscheiden, 00:13:17.715 --> 00:13:21.250 ob die mit einem Strich zeichenbar sind. 00:13:21.782 --> 00:13:24.197 Genau. Es gibt noch eine Variante mit Einbahnstraßen, 00:13:24.288 --> 00:13:25.792 also für gerichtete Graphen, 00:13:25.792 --> 00:13:29.243 wenn man nicht jede Kante in beliebige Richtung durchlaufen darf. 00:13:29.243 --> 00:13:32.810 Oh ja. Das ist vielleicht sogar echt praktisch relevant. 00:13:33.282 --> 00:13:36.162 Für den Stadtplan, ne? Da gibt's ja tatsächlich so Einbahnstraßen. 00:13:36.162 --> 00:13:38.587 Aber wenn man jetzt zum Beispiel irgendwie so viele Einbahnstraßen machen 00:13:38.587 --> 00:13:40.631 will, um den Verkehr neu zu steuern, dann muss man ja aufpassen, 00:13:40.631 --> 00:13:42.916 dass man überall noch hinkommen kann oder so. 00:13:42.916 --> 00:13:45.230 Aber, na gut, das ist vielleicht einfacher. 00:13:45.821 --> 00:13:49.558 Genau. Oder ich weiß nicht. Ist jedenfalls auch ein graphentheoretisches Problem. 00:13:49.889 --> 00:13:52.323 Wenn ich jede Straße in meiner Stadt zu einer Einbahnstraße machen kann, 00:13:52.554 --> 00:13:55.630 kann ich dann immer noch von überall zu überall hinkommen. 00:13:56.040 --> 00:13:58.242 Das ist auch ein graphentheoretisches Problem, ja. 00:13:58.242 --> 00:14:02.486 Das gibt doch so, wie heißen die denn, das sind so Transportprobleme, ne? 00:14:02.486 --> 00:14:03.907 Wo man irgendwie eine Quelle hat 00:14:03.907 --> 00:14:07.471 und bis zu einer Senke irgendwas transportieren will und sich dann fragt, 00:14:07.471 --> 00:14:09.713 erstens geht das überhaupt und dann was kann ich da, 00:14:09.713 --> 00:14:11.014 wenn die noch gewichtet sind, 00:14:11.014 --> 00:14:14.757 also so eine Größe haben, sozusagen eine Durchlässigkeit, 00:14:14.757 --> 00:14:16.559 kann man sich ja auch noch fragen, wie viel kriegt man dann da. 00:14:16.559 --> 00:14:17.730 Wie viel kommt da durch und so, ja. 00:14:18.680 --> 00:14:23.264 Wenn dann eine gesperrt wird, ist es immer noch und ja, 00:14:23.264 --> 00:14:26.136 da kann man irgendwie die Dualität verwenden. 00:14:26.146 --> 00:14:28.527 Naja, aber das ist vielleicht ein anderes Thema. 00:14:28.527 --> 00:14:29.378 Verkehrsplanung. 00:14:29.768 --> 00:14:31.900 Verkehrsplanung, ja. Oder wolltest du jetzt Verkehrsplanung? 00:14:31.950 --> 00:14:33.611 Nö, wollte ich jetzt eigentlich gar nicht. 00:14:33.611 --> 00:14:35.903 Ich wollte eigentlich wirklich nur über die Häuser vom Nikolaus reden. 00:14:37.314 --> 00:14:40.646 Aber jetzt gibt es ja noch diese Hamilton-Kreise und das ist ja viel schwieriger. 00:14:41.077 --> 00:14:46.030 Da ist doch die Frage, jede Ecke einmal zu besuchen. 00:14:46.602 --> 00:14:48.390 Genau, das ist unverwahrt. Und keine zweimal. 00:14:49.386 --> 00:14:52.021 Genau, da, richtig. Völlig richtig. 00:14:52.021 --> 00:14:52.861 Das ist auch eine Frage, 00:14:52.861 --> 00:14:55.384 die sich Euler schon gestellt hat, damals in Königsberg, 00:14:55.384 --> 00:14:56.955 als er über die Brücken gewandert ist. 00:14:58.046 --> 00:14:59.847 Da wollte er eben diesen Spaziergang finden, 00:14:59.847 --> 00:15:02.469 der sozusagen alle Brücken einmal abläuft, 00:15:02.469 --> 00:15:08.134 aber auch Spaziergänge finden, die eine bestimmte Anzahl von Lokalitäten aufsucht. 00:15:08.134 --> 00:15:13.218 Ja, also Beispiel Besuch kommt, wenn man mal wieder reisen darf. 00:15:13.218 --> 00:15:15.121 Wir wollen den Magdeburg zeigen und wir wollen. 00:15:15.121 --> 00:15:18.796 Am Pinken Haus vorbei, am Dom, über die Hubbrücke, in den Stadtpark. 00:15:18.796 --> 00:15:21.254 Wo muss man noch hin? In irgendeinen Kneipe. 00:15:21.254 --> 00:15:23.878 In den Elbauenpark vielleicht, in irgendeine Kneipe, genau. 00:15:24.250 --> 00:15:27.750 Wenn die noch da sind bis dahin, hoffen wir, dass die nicht alles schließen. 00:15:29.342 --> 00:15:31.877 Genau und dann noch das beste Eis der Stadt und so. 00:15:32.810 --> 00:15:34.916 Und dann will man sich aber einen Spaziergang aussuchen, 00:15:34.916 --> 00:15:36.890 wo man keinen Weg zweimal geht. 00:15:38.481 --> 00:15:39.744 Das ist die eine Variante. 00:15:39.744 --> 00:15:41.908 Und die andere Variante ist, man braucht einen Spaziergang, 00:15:41.908 --> 00:15:45.404 der überhaupt jeden dieser Punkte genau einmal anläuft, 00:15:45.475 --> 00:15:48.381 ohne dass man nochmal am Dom vorbeikommt. 00:15:48.381 --> 00:15:50.426 Genau. Ja, nicht nochmal am Dom vorbeikommen. 00:15:50.426 --> 00:15:52.430 Da darf man, und das ist viel schwieriger. 00:15:52.430 --> 00:15:54.655 Das ist ja eigentlich kurios, weil das so dual ist. 00:15:54.655 --> 00:15:57.430 Bei einem will man jede Kante, jeden Weg einmal gehen. 00:15:58.480 --> 00:16:03.576 Ja. Und bei dem anderen will man jeden Vertex, also jeden Ort einmal besuchen. 00:16:03.806 --> 00:16:05.348 Und das eine hat eine einfache Lösung. 00:16:05.348 --> 00:16:08.351 Wenn man, kann man jeden Weg einmal gehen, ohne einen Weg zweimal zu gehen, 00:16:08.351 --> 00:16:09.513 hat einfach eine einfache Lösung. 00:16:09.513 --> 00:16:11.525 Guckt man einfach diese Gerade an. 00:16:11.995 --> 00:16:14.218 Und das andere Problem, kann man jeden Ort einmal besuchen, 00:16:14.218 --> 00:16:15.999 das ist ja ziemlich schwer. Ja. 00:16:16.640 --> 00:16:19.546 Das ist ziemlich schwer und es gibt keine, 00:16:19.546 --> 00:16:22.533 es gibt kein gutes Kriterium und es gibt auch tatsächlich, 00:16:22.533 --> 00:16:25.740 ich habe das extra nochmal nachgeguckt, keine gute algorithmische Lösung. 00:16:25.740 --> 00:16:31.210 Ja. Also außer so Brutforce-Sachen, ja, also alles ausprobieren, 00:16:31.210 --> 00:16:32.893 was geht und dann hoffen, 00:16:32.893 --> 00:16:33.534 dass es klappt. 00:16:33.534 --> 00:16:37.230 Ist das NP, ist das hier eines von den NP-vollständigen Problemen oder so? 00:16:37.422 --> 00:16:42.137 Das habe ich nicht nachgeguckt jetzt, ob das NP vollständig ist oder nicht. 00:16:42.137 --> 00:16:43.550 Klingt fast so, hm. 00:16:44.022 --> 00:16:47.741 Also, ja. Ja, ja, doch. 00:16:47.741 --> 00:16:49.752 Wenn man die Kanten noch gewichtet, 00:16:50.102 --> 00:16:54.796 dann ist das das Traveling Salesman Problem, der, 00:16:54.866 --> 00:16:56.688 also wenn man Kanten gewichtet, heißt, 00:16:56.688 --> 00:16:58.630 wenn die, wenn man noch berücksichtigt, 00:16:58.630 --> 00:17:00.191 dass zwischen den verschiedenen Punkten, 00:17:00.191 --> 00:17:02.603 die man besuchen will und keinen zweimal anlaufen, 00:17:02.793 --> 00:17:04.644 dass die Strecke unterschiedlich lang ist. 00:17:05.175 --> 00:17:06.246 Und dann will man 00:17:07.917 --> 00:17:11.330 nicht nur sozusagen von A nach B kommen, sondern auch bestmöglich. 00:17:12.581 --> 00:17:17.273 Also mit dem kürzesten Verbindungsweg diese Punkte der Reihe nach ablaufen. 00:17:17.273 --> 00:17:20.369 Nicht nur eine Lösung finden, sondern auch noch die kürzeste. 00:17:20.942 --> 00:17:21.904 Es ist ja generell so, 00:17:21.904 --> 00:17:25.252 wenn man irgendwie so ein kombinatorisches Problem hat und das ist gelöst, 00:17:25.252 --> 00:17:26.476 dann kann man es immer noch schwieriger machen, 00:17:26.476 --> 00:17:28.490 indem man Optimierungsprobleme macht. 00:17:28.741 --> 00:17:29.483 Meistens ist es so, 00:17:29.483 --> 00:17:34.295 dass man einfach nur irgendwelche Zahlen an die Lösung schreibt und dann die mit 00:17:34.295 --> 00:17:36.469