Karten-Färbeproblem Induktion |
| 15.03.2019, 17:44 | Ugnius | Auf diesen Beitrag antworten » |
| Karten-Färbeproblem Induktion Ich hab das berühmte Kartenfärbeproblem mal anders im Internet gefunden und habe überlegt, ob man das nicht auch irgendwie beweisen könnte. Das Problem ist: Wir haben eine Karte m mit unendlich vielen Ländern. Wir wissen (bzw die Aufgabe legt den Fakt fest), dass es eine Zahl k gibt, für die jedes endliche Teilfragment t von m k-färbbar* ist. Kann man anhand dieser Informationen überprüfen, dass dann auch die gesamte, unendlich große Karte k-färbbar ist? Ich habe noch keine Idee, aber ich hatte den Eindruck, man könnte das vielleicht mit Induktion angehen? Also der Fakt, dass es mindestens ein Fragment gibt, das k färbbar ist, ist eine Art Induktionsanfang. Faktisch gibt es ja unendlich viele endlich Teilfragmente die k-färbbar sind, die gesamte Potenzmenge der Landkarte (insofern man bei unendlich Elementen großen Mengen von Potenzmenge reden darf). Als Induktionsschritt könnte man so einem endlichen Fragment ein weiteres Land hinzufügen, sodass die Bedingung weiter erfüllt ist, da ein solches Fragment aus Fragment f1 und einem weiteren Land ja auch ein endliches Fragment ist, das laut Ausgangsbedingung k-färbbar ist. Aber irgendwie kommt mir das alles schwammig formuliert vor. Ist das überhaupt sinnvoll, was ich hier mache? Oder hab ich mich schon in eine Falle manövriert, als ich dachte, das mit Induktion lösen zu können. (*also für die, die das berühmte Problem nicht kennen: k-färbbar meint, dass man eine Karte mit nur k Farben so färben kann, dass benachbarte Länder unterschiedliche Farben haben) |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
