Die Haken auf der Rückseite eines Bilderrahmens... ja wofür könnten die gut sein?
Die Haken auf der Rückseite eines Bilderrahmens... ja wofür könnten die gut sein?
Bestimmt nicht zum Aufhängen des Bildes. Dafür müsste man ja einen Nagel in die Wand hauen und überhaupt
Zitat von Ghaldak
Die wunderbare Welt des Mongke K. ist zur Zeit leider überhaupt nicht aufregend, weil es außer Lernen wenig zu tun gibt. Ich will trotzdem mal versuchen, davon hier zu berichten.
Wie manche wissen studiere ich u.a. Mathematik. Ich habe häufig den Eindruck, dass Nicht-Mathematiker (bzw. Nicht-MINTler) keine wirkliche Vorstellung davon haben, was man da macht - was man an Mathe in der Schule macht, ist eher Rechnen. Man kennt vielleicht so grandiose Witze wie "Sei Epsilon kleiner 0" () oder weiß, was ein Axiom ist. Meistens weiß man auch, dass Mathematiker immer alles beweisen wollen. Daran will ich ansetzen, anstatt zu erklären, was Mathematik meinem Verständnis nach ist. Manche Beweise sind zwar zäh und langweilig, aber ein schöner und kreativer Beweis ist wohl das unterhaltsamste an der Mathematik.
Der Meinung bin übrigens nicht nur ich. Der ungarische Mathematiker Paul Erdős hat ein Konzept von einem Buch entworfen, in dem Gott die elegantesten Beweise aller Zeiten bewahrt (Zitat Erdős: "You don't have to believe in God, but you should believe in The Book."). In dem Buch "Proofs from THE BOOK" sammeln Martin Aigner und Günter Beweise, die wegen ihrer Eleganz gute Kandidaten wären.
Genug des Vorgeplänkels, kommen wir zum Beweis. Ich werde versuchen, den möglichst anschaulich zu halten; wenn man den Umgang mit mathematischer Notation geübt ist, kann das glaube ich recht verwirrend und abschreckend wirken (ganz im Gegensatz zu einer Textwand).
Ich hab mich für den Beweis, dass planare Graphen fünffärbbar sind, entschieden.
Eine Anmerkung: es gibt eine prominentere (und stärkere) Variante dieses Satzes, nach der auch 4 Farben reichen. Der Beweis ist aber seeehr viel komplizierter und hin und wieder umstritten.
In der Mathematik würde man die Formulierung des Satzes nicht so stehen lassen. Stattdessen postuliert man ein Theorem: Sei G ein planarer Graph. Dann ist die chromatische Zahl chi(G) höchstens 5.
Was heißt das? Das bringt mich schon zu einer Schwierigkeit, wenn ich anderen Leuten versuche, zu erklären, warum Mathematik interessant sind: sie ist sehr präzise. Um der Präzision gerecht zu werden, kommt man kaum drum rum, bestimmte Axiome, Definitionen, ... zu kennen. Der Satz hat aber eine sehr anschauliche Anwendung, deshalb versuch ich es unpräzise.
Also, was ein Graph ist, kann man sich wohl noch am einfachsten vorstellen. Das sind eine Menge von Knoten, die über Kanten miteinander verbunden sind. Zum Beispiel so:
Graphen kann man oft benutzen, um Sachverhalte zu modellieren. Zum Beispiel könnten die Knoten Menschen sein und eine Kante, ob diese Menschen einander kennen. Der Graphen oben könnte also eine Clique von 5 Leuten darstellen, weil sich jeder kennt (solche Graphen nennt man tatsächlich auch Cliquen).
Ein solcher Graph heißt planar, wenn man ihn so aufmalen kann, dass sich keine zwei Kanten schneiden. Üblicherweise zeichnet man die Kanten als Geraden (wie im Bild), die Definition schreibt das aber nicht vor. Der Satz von Fáry (noch so ein ungarischer Mathematiker) sagt aber, dass das keinen Unterschied macht, deshalb gehe ich da nicht weiter drauf ein. Das ist aber eine dieser Stellen, an der man aus mathematischer Sicht nicht so einfach um Präzision rumkommt.
Der obige Graph ist nicht planar. Am besten versucht man das, wenn man es nicht schon sieht, selbst klarzumachen - ansonsten hab ich hier mal alle relevanten Möglichkeiten, den Graph aufzumalen, dargestellt:
Achtung Spoiler:
Die chromatische Zahl ist eine fancy Art und Weise zu sagen, dass man höchstens so viele (laut Theorem 5) Farben braucht, um die Knoten anzumalen, so dass keine zwei über eine Kante verbundene (benachbarte) Knoten die gleiche Farbe haben.
Auch dazu ein Beispiel: man kann die deutschen Bundesländer als Knoten eines Graphen auffassen und eine Kante für je zwei benachbarte Länder zeichnen.
Der so entstandene Graph ist offenbar planar. Das war zwar bei der Version der Karte etwas fummelig, weil es so aussieht, als ob Brandenburg, Sachsen-Anhalt, Niedersachsen und MeckPom einen gemeinsamen Grenzpunkt haben. Jetzt soll es möglich sein, diese mit höchstens 5 Farben anzumalen, dass keine zwei benachbarten Länder die gleiche Farbe haben. Und das geht:
Bewiesen wurde bislang - nichts. Zu verstehen, was ein Satz aussagt ist aber mindestens genauso wichtig beim Prozess. Außerdem muss man ja auch irgendwie darauf kommen, was man vielleicht mal beweisen will. In der Uni-Mathematik läuft es meist anders, da muss man nur zeigen, was andere schon gezeigt haben. Im Allgemeinen macht es durchaus Sinn, sich vorher mit dem Problem zu befassen, um einen guten Kandidaten für ein Theorem zu finden - einfach mal ins Blaue eine Behauptung aufstellen und gucken, ob das geht, klappt in der Praxis selten
[...]
Aber wieso denn 5?
https://de.wikipedia.org/wiki/Vier-Farben-Satz
Die Macht des Verstandes ... sie wird auch im Fluge dich tragen - Otto Lilienthal
Schweinepriester: Ihr habt euch alle eine Fazialpalmierung verdient.
Weil die endgültige Lösung noch nicht überall anerkannt wird. Und weil der Beweis viel zu kompliziert für Mongke ist, um ihn hier in der Story darstellen zu können
"La majestueuse égalité des lois, qui interdit au riche comme au pauvre de coucher sous les ponts, de mendier dans les rues et de voler du pain." - Anatole France
Aah, da steht ja sogar ein Satz dazu.
Die Macht des Verstandes ... sie wird auch im Fluge dich tragen - Otto Lilienthal
Schweinepriester: Ihr habt euch alle eine Fazialpalmierung verdient.
[...]
Jetzt zum eigentlichen Spaß: wie zeigt man das? Wie zeigt man, dass alle planaren Graphen fünffärbbar sind?
Eine Möglichkeit ist es, methodisch alle denkbaren planaren Graphen auszuprobieren. Dazu kann man erstmal schauen, ob das Theorem für einfache Beispiele funktioniert. Dann tut man so, dass es für einen fixen Graphen mit n Knoten an und versucht es, für einen Graphen mit einem weiteren (also n+1) Knoten zu zeigen. Wäre n z.B. 5 und wir wüssten, dass es für solche Graphen geht, könnten wir versuchen es für n+1 = 6 zu zeigen und es dann im nächsten Schritt mit n = 6 für n+1 = 7 zeigen usw. Ein klassischer sog. Induktionsbeweis. Die sieht man in der Mathematik so oft, insbesondere in der Graphentheorie, dass es ein vielversprechendes Vorgehen sein könnte.
Für kleine planare Graphen (mit höchstens 5 Knoten) gilt die Aussage offenbar. Jeder Knoten kann eine eigene Farbe erhalten und wir sind fertig. Nehmen wir also mal an, dass es für einen Graphen mit n Knoten gilt.
Wir schauen uns also einen allgemeinen planaren Graphen mit n+1 Knoten an. Dann machen wir beim Nachdenken vielleicht folgende Beobachtung: wenn man einen Knoten und alle Kanten zu diesem Knoten löscht, hat man einen Graphen mit n Knoten. Der ist immer noch planar! Also könnte man den schonmal irgendwie mit 5 Farben "richtig" einfärben. Das Problem, das sich ergibt, ist, dass man jetzt ein bisschen wie ein Ochse vorm Berg steht: wie weiter?
Hier hilft es z.B. manchmal, das Problem schwerer zu machen, um gewisse Strukturen zu erzwingen. Man könnte beispielsweise annehmen, dass der Graph so planar wie nur irgend möglich ist, man also keine Kante zwischen zwei Knoten einfügen kann, ohne, dass die sich mit einer anderen schneidet. Das führt zwangsläufig auf eine Triangulation (je drei Kanten bilden ein Dreieck). Auch sowas müsste man an der Stelle als Mathematiker beweisen oder schon bewiesen haben. Ich tue mal so, als ob, weil auch das Resultat anschaulich genug ist. Der Deutschland-Graph sähe z.B. so aus (wenn ich nichts vergessen habe):
Unser Problem wird dadurch wirklich schwieriger: angenommen wir könnten den Graphen jetzt mit 5 Farben einfärben. Dann wäre das immer noch eine valide Färbung, wenn wir einzelne Kanten und damit Einschränkungen weglassen.
Warum das hilfreich ist sieht man leider nicht ohne eine weitere Kenntnisse über (planare) Graphen, was dem Beispiel hier ein bisschen abträglich ist. Es ist nämlich so, dass es in einem maximal planaren Graphen immer einen Knoten gibt, der höchstens 5 ausgehende Kanten hat. Begründung, für wen es interessiert, im Spoiler:
Achtung Spoiler:
Man kann sich also einen solchen Knoten raussuchen als Kandidaten, den man löscht. Dann hätten wir einen Graphen, von dem wir wissen, dass er fünffärbbar ist und müssen nur noch wenige Fälle abdecken.
Der einzige problematische Fall sieht also so aus:
Wenn unter den 5 Nachbarn, die ich hier ObdA* V1 ... V5 genannt habe, min. zwei die gleiche Farbe haben, könnte ich einfach die für den in der Mitte nehmen. Also gehe ich davon aus, dass alle verschiedene Farben haben. Ich gehe auch davon aus, dass ich z.B. nicht den hellblauen Knoten gelb färben kann, ohne, dass ich dann den gelben ändern muss. Wenn der hellblaue nur dunkelblaue Nachbarn hätte, würde das ja gehen - dann könnte ich den in der Mitte hellblau färben und hätte gewonnen.
Diese Art vorzugehen hat sich auch oft bewährt: man nimmt einfach mal das Gegenteil von dem an, was man zeigen will, und führt es auf einen Widerspruch.
Der Widerspruch ist hier - zugegeben - nicht ganz offensichtlich. Das ist so eine Stelle, für die man dann etwas Kreativität oder logisches Nachdenken braucht. Bis dahin würde ich aus Sicht eines Mathematikers sagen, ist alles Standard: Induktion ansetzen, Problemfall einschränken, ein paar Sätze, die man kennt benutzen.
Jetzt sehe ich: wenn ich also gelb und hellblau nicht tauschen kann, muss es Knoten wie im Bild geben, die abwechselnd blau/ gelb sind und zwischen den beiden liegen. Das gleiche gilt für z.B. rot und grün:
Diese beiden Pfade müssten sich entweder einen Knoten teilen, der zwei Farben haben müsste (das geht nicht), oder sie müssten sich kreuzen: im Prinzip versteckt sich nämlich unter der Voraussetzung, dass es solche Blau-Gelb und Rot-Grün Pfade gibt eine 5-Clique in unserem Graphen mit n+1 Knoten.
Von der wissen wir, dass sie nicht planar ist (das war das Beispiel am Anfang), unser Graph war aber nach Voraussetzung planar (das, in präziser und allgemeiner fomuliert, ist der Satz von Kuratowski - zur Abwechslung mal ein polnischer Mathematiker).
Summa summarum muss es zwei Knoten geben, deren Farben man wechseln kann und macht so eine für die Mitte frei. Damit ist der Beweis auch "schon" fertig; QED.
* * *
Uff, das wurde jetzt ausführlicher, als ich gedacht hätte und nur halb so sauber, wie ich es mir gewünscht hätte. Ich hoffe, die Nicht-MINTler können dem trotzdem folgen, wenn es sie interessiert. Ich hab den Beweis als recht eingängig und anschaulich abgespeichert (Induktion, zeige dass es einen Knoten mit Maximalgrad 5 gibt, Widerspruch mit Kuratowski), mir ist aber jetzt beim nicht-mathematischen Aufschreiben erst bewusst geworden, wie viel da aus dem Mathematik-"Werkzeugkasten" drin steckt: ein paar Definitionen, Induktion, Problem schwerer machen, Handshake Lemma, Polyederformel von Euler, Satz von Kuratowski und das Widerspruchsprinzip - un in den Beweisen von Euler und Kuratowski gehen noch mehr Sachen ein. Für etwas, bei dem man nach ein paar Beispielen sagen würde "ja, wir schon stimmen."
_____________________________________
*Ohne Beschränkung der Allgemeinheit, soll hier heißen: wie ich die Dinger benenne und färbe, ist egal, solange ich 5 verschiedene Bezeichner und Farben benutze; ich fühl mich nur immer richtig schön mathematisch, wenn ich ObdA schreiben kann
Fixed itUnd weil der Beweis viel zu kompliziertfür Mongke ist, um ihn hier in der Story darstellen zu können
Der Beweis geht über mehrere hundert Seiten mit zig Fallunterscheidungen, da hätte ich noch wesentlich länger dran gesessen
Ich weiß, ich wollte das nur darstellen. Aber ich bezweiflte eben, dass du dich da so sehr einarbeiten wollen würdest, um das dann hier interessierten Laien präsentieren zu können.
"La majestueuse égalité des lois, qui interdit au riche comme au pauvre de coucher sous les ponts, de mendier dans les rues et de voler du pain." - Anatole France
Ich bezog mich auch nur auf das Entfernen des Strikes - ich gehe davon aus, dass das zu kompliziert für mich ist. Da ziehe ich selbst die Grenze zwischen "Muss ich erst beweisen, bevor ichs glaube" und "nehme ich so hin, weil ich den anderen glaube/ es praktisch noch irrelevanter ist".
Und wie ist das mit Ex-/Enklaven? Bremerhaven hast du ja schön ausgespart....
Schon klar
"La majestueuse égalité des lois, qui interdit au riche comme au pauvre de coucher sous les ponts, de mendier dans les rues et de voler du pain." - Anatole France
Die Bemerkung hätte ich antizipieren müssen.
Wenn man die als eigene Knoten auffasst, lässt sich das Theorem nach wie vor anwenden. Wenn ich erzwingen will, dass die gleich gefärbt sind, geht das im Allgemeinen nicht mehr vermute ich.
Dann würde der Beweis (und wohl das ganze Theorem) nicht mehr gelten, da du so eine Fläche nicht als planaren Graph darstellen kannst. Du kannst dir ja eine Fläche auf der Karte ausdenken, die n Exklaven hat, eine pro Land (wobei n der Anzahl aller Länder entspricht) .
"La majestueuse égalité des lois, qui interdit au riche comme au pauvre de coucher sous les ponts, de mendier dans les rues et de voler du pain." - Anatole France
Cool! Auf dem Kopf gestellt, hätten wir ein Pentagramm!Blablabla
Blablabla
Berechtigungen
Zitieren
