You'd have a hard time finding Königsberg on any modern maps,
but one particular quirk in its geography
has made it one of the most famous cities in mathematics.
The medieval German city lay on both sides of the Pregel River.
At the center were two large islands.
The two islands were connected to each other and to the river banks
by seven bridges.
Carl Gottlieb Ehler, a mathematician who later became the mayor of a nearby town,
grew obsessed with these islands and bridges.
He kept coming back to a single question:
Which route would allow someone to cross all seven bridges
without crossing any of them more than once?
Think about it for a moment.
7
6
5
4
3
2
1
Give up?
You should.
It's not possible.
But attempting to explain why led famous mathematician Leonhard Euler
to invent a new field of mathematics.
Carl wrote to Euler for help with the problem.
Euler first dismissed the question as having nothing to do with math.
But the more he wrestled with it,
the more it seemed there might be something there after all.
The answer he came up with had to do with a type of geometry
that did not quite exist yet, what he called the Geometry of Position,
now known as Graph Theory.
Euler's first insight
was that the route taken between entering an island or a riverbank and leaving it
didn't actually matter.
Thus, the map could be simplified with each of the four landmasses
represented as a single point,
what we now call a node,
with lines, or edges, between them to represent the bridges.
And this simplified graph allows us to easily count the degrees of each node.
That's the number of bridges each land mass touches.
Why do the degrees matter?
Well, according to the rules of the challenge,
once travelers arrive onto a landmass by one bridge,
they would have to leave it via a different bridge.
In other words, the bridges leading to and from each node on any route
must occur in distinct pairs,
meaning that the number of bridges touching each landmass visited
must be even.
The only possible exceptions would be the locations of the beginning
and end of the walk.
Looking at the graph, it becomes apparent that all four nodes have an odd degree.
So no matter which path is chosen,
at some point, a bridge will have to be crossed twice.
Euler used this proof to formulate a general theory
that applies to all graphs with two or more nodes.
A Eulerian path that visits each edge only once
is only possible in one of two scenarios.
The first is when there are exactly two nodes of odd degree,
meaning all the rest are even.
There, the starting point is one of the odd nodes,
and the end point is the other.
The second is when all the nodes are of even degree.
Then, the Eulerian path will start and stop in the same location,
which also makes it something called a Eulerian circuit.
So how might you create a Eulerian path in Königsberg?
It's simple.
Just remove any one bridge.
And it turns out, history created a Eulerian path of its own.
During World War II, the Soviet Air Force destroyed two of the city's bridges,
making a Eulerian path easily possible.
Though, to be fair, that probably wasn't their intention.
These bombings pretty much wiped Königsberg off the map,
and it was later rebuilt as the Russian city of Kaliningrad.
So while Königsberg and her seven bridges may not be around anymore,
they will be remembered throughout history by the seemingly trivial riddle
which led to the emergence of a whole new field of mathematics.
ستواجه صعوبة في إيجاد مدينة كونيغسبيرغ على أي خرائط حديثة.
ولكن خاصية معينة في جغرافيتها
جعلتها واحدة من أشهر المدن في الرياضيات.
تقع المدينة الألمانية العائدة للقرون الوسطى على جانبي نهر بريجل.
كانت تتواجد في مركزها جزيرتان كبيرتان.
كانت الجزيرتان مرتبطتين ببعضهما وبضفاف النهر
بواسطة سبعة جسور.
كارل غوتليب إيلر، عالم الرياضيات الذي أصبح لاحقا رئيس بلدية بلدة مجاورة،
كان مهووسا بهذه الجزر والجسور.
وظل يفكر في سؤال واحد:
أي الطرق يمكنها السماح لشخص بعبور كل الجسور السبعة
دون عبور أي منها أكثر من مرة؟
فكر للحظة .
7
6
5
4
3
2
1
هل تعلن استسلامك؟
يجب عليك ذلك.
إنه أمر غير ممكن.
ولكن محاولة شرح السبب قادت عالم الرياضيات الشهير ليونهارت أويلر
لابتكار حقل جديد من الرياضيات.
كتب كارل لأويلر طالبا مساعدته في هذه المشكلة.
رفض أويلر في البداية كون المسألة لها علاقة بالرياضيات.
ولكن كلما تصارع معها،
كلما بدا أنه ربما هناك علاقة ما .
الجواب الذي جاء به كان مرتبطا بفرع من الهندسة
لم يكن موجودا بعد، وهو ما أسماه بهندسة الأماكن،
يعرف الآن باسم نظرية المخططات.
أول ما فطن له أويلر
هو أن الطريق المسلوكة لدخول جزيرة أو ضفة نهر ومغادرتها
لا تهم في الواقع.
وهكذا، يمكن تبسيط الخريطة بتمثيل كل من المناطق الأربع لليابسة
بنقطة واحدة،
ما نسميه الآن بعقدة،
مع خطوط أو أقواس، بينها لتمثيل الجسور.
وهذا المخطط المبسط يسمح لنا بحساب درجات كل عقدة بسهولة.
هذا هو عدد الجسور المتصلة بكل منطقة يابسة.
ما أهمية الدرجات؟
حسنا، وفقا لقواعد التحدي،
بمجرد وصول المسافرين إلى اليابسة عبر جسر معين ،
يجب عليهم المغادرة عبر جسر مختلف.
بعبارة أخرى، فإن الجسور المؤدية من وإلى كل عقدة على أي طريق
يجب أن تكون ذات أزواج مختلفة،
وهذا يعني أن عدد الجسور المتصلة بكل منطقة يابسة تمت زيارتها
يجب أن يكون زوجيا.
إن الاستثناءات الوحيدة الممكنة هي مواقع بداية
ونهاية المسيرة.
عند النظر إلى المخطط، يتضح أن كافة العقد الأربع لديها درجة فردية.
إذن وبغض النظر عن المسار المختار ،
فإنه سيتعيَّن عند نقطة ما، عبور أحد الجسور مرتين.
استخذم أويلر هذا البرهان لصياغة نظرية عامة
تنطبق على جميع المخططات التي تظم عقدتين أو أكثر .
مسار أويلر الذي يجتاز كل قوس مرة واحدة فقط
ممكن في حالة واحدة من أصل اثنتين.
الأولى هي عندما تكون هناك بالضبط عقدتين من درجة فردية،
مما يعني أن ما تبقى زوجي.
في هذه الحالة، نقطة البداية هي أحد العقد الفردية،
والأخرى هي نقطة النهاية .
والحالة الثانية هي عندما تكون كافة العقد ذات درجة زوجية.
حينها سيبدأ مسار أولير وينتهي في نفس الموقع،
وهذا ما يجعل منه ما يسمى أيضا بدارة أويلر.
إذن كيف يمكن لك إنشاء مسار أويلر في كنيغسبرغ؟
هذا بسيط.
فقط أزل أحد الجسور.
ويتضح أن التاريخ خلق مسار أويلر من تلقاء نفسه.
خلال الحرب العالمية الثانية، دمرت قوات الجو السوفياتية اثنين من جسور المدينة،
ممهِّدة الطريق لمسار أويلر .
لكن ، ولكي نكون عادلين، لم تكن هذه هي نيتهم على الأرجح.
محت هذه التفجيرات إلى حد كبير كنيغسبرغ من الخريطة،
وأعيد بناؤها لاحقا لتصبح المدينة الروسية "كالينينغراد".
إذن ورغم أن كنيغسبرغ وجسورها السبعة لم تعد متواجدة الآن ،
فسيتم تذكرها على مدار التاريخ عبر اللغز الذي يبدو تافها
والذي أدى إلى ظهور حقل جديد كليا من الرياضيات.
Heute findet man die Stadt Königsberg nicht mehr auf der Karte,
aber eine besondere Eigenheit in ihrer geografischen Struktur
machte sie zu einer der bekanntesten Städte in der Mathematik.
Die mittelalterliche deutsche Stadt lag auf beiden Seiten des Pregel.
Im Stadtzentrum gab es zwei große Inseln.
Diese zwei Inseln waren miteinander und mit den Flussufern
durch sieben Brücken verbunden.
Der Mathematiker Carl Gottlieb Ehler,
der später Bürgermeister einer benachbarten Stadt wurde,
war von diesen Inseln und Brücken fasziniert.
Er stellte sich immer wieder eine einzige Frage:
Welche Strecke muss man gehen, um alle 7 Brücken zu überqueren,
ohne auch nur eine davon mehr als einmal zu überqueren?
Denke einen Moment darüber nach.
7
6
5
4
3
2
1
Du gibst auf?
Das solltest du auch.
Denn es ist nicht möglich.
Aber mit den Erklärungsversuchen entdeckte der berühmte Mathematiker Leonhard Euler
ein neues Gebiet der Mathematik.
Ehler schrieb an Euler und bat ihn um Hilfe.
Euler lehnte die Frage zunächst ab, da sie nichts mit Mathematik zu tun hatte.
Aber umso mehr er mit der Frage rang,
umso mehr schien es, dass da doch ein Zusammenhang bestand.
Die Antwort, die er fand, hatte nichts mit der existierenden Geometrie zu tun;
es war die Geometrie der Lage,
die heute als Graphentheorie bekannt ist.
Euler erstes Erkenntnis:
Die Strecke zwischen dem Betreten einer Insel oder einem Flussufer
und dem Verlassen derer, tat nichts zur Sache.
Also konnte die Karte vereinfacht werden:
Jede der vier Landmassen wird als ein einziger Punkt dargestellt,
was wir heute "Knoten" nennen,
mit Linien, oder Kanten, zwischen ihnen, um die Brücken darzustellen.
Dieser vereinfachte Graph erlaubt es uns,
die Grade eines jeden Knotens ganz leicht zu zählen.
Das ist die Anzahl der Brücken, die jede Landmasse berührt.
Warum sind die Grade wichtig?
Den Regeln der Herausforderung zufolge
müssen Personen, die über eine Brücke an einer Landmasse ankommen,
diese über eine andere Brücke wieder verlassen.
Die Brücken, die auf einer Strecke zu und von jedem Knoten hin- und wegführen,
müssen in verschiedenen Paaren auftreten,
d. h. die Anzahl der Brücken, die jede besuchte Landmasse berühren,
muss eine gerade Zahl sein.
Die einzig möglichen Ausnahmen
sind der Anfang und das Ende des Wegs.
Sieht man sich den Graph an, wird offensichtlich:
Alle vier Knoten haben einen ungeraden Grad.
Ganz gleich, welcher Weg gewählt wird,
an irgendeinem Punkt muss eine Brücke zweimal überquert werden.
Euler nutzte diesen Beweis, um eine allgemeine Theorie zu formulieren,
die für alle Graphen mit zwei oder mehr Knoten gilt.
Ein Eulerischer Weg, der jede Kante nur einmal betritt,
ist nur in einem von 2 Szenarios möglich.
Erstens, wenn es genau zwei Knoten mit ungeraden Grad gibt,
was bedeutet, die anderen sind alle gerade.
Dann ist der Ausgangspunkt einer der ungeraden Knoten
und der Endpunkt der andere.
Zweitens, wenn alle Knoten einen geraden Grad haben.
Dann beginnt und endet der Eulerische Weg am selben Ort,
wodurch ein sogenannter Eulerischer Rundgang entsteht.
Wie könntest du also einen Eulerischen Weg in Königsberg entstehen lassen?
Ganz einfach:
Entferne einfach eine Brücke.
Sogar die Geschichte schaffte sich ihren eigenen Eulerischen Weg.
Im Zweiten Weltkrieg zerstörte die sowjetische Luftwaffe zwei der Brücken
und ermöglichte somit einen Eulerischen Weg.
Aber zugegeben, das war bestimmt nicht ihre Absicht.
Diese Bombardierungen radierten Königsberg fast von der Karte aus.
Später wurde sie als die russische Stadt Kaliningrad wieder aufgebaut.
Obgleich die Stadt Königsberg und ihre 7 Brücken nicht mehr existieren,
wird man sich wegen eines scheinbar trivialen Rätsels immer an sie erinnern,
das zu einem neuen Gebiet der Mathematik geführt hat.
Θα δυσκολευτείτε να βρείτε το Κένινγκσμπεργκ στους σύγχρονους χάρτες,
αλλά μια ιδιαιτερότητα της γεωγραφίας του
το έκανε μία από τις πιο διάσημες πόλεις στα Μαθηματικά.
Η μεσαιωνική γερμανική πόλη εκτεινόταν και στις δύο όχθες του ποταμού Πρέγκελ.
Στο κέντρο του βρίσκονταν δύο μεγάλα νησιά.
Τα δύο νησιά συνδέονταν μεταξύ τους και με τις όχθες του ποταμού
με επτά γέφυρες.
Ο Καρλ Γκότλιμπ Έλερ, ένας μαθηματικός,
που αργότερα έγινε ο δήμαρχος μιας γειτονικής πόλης,
απέκτησε εμμονή με αυτά τα νησιά και τις γέφυρες.
Συνεχώς κατέληγε σε ένα απλό ερώτημα·
ποια διαδρομή θα επέτρεπε σε κάποιον να διασχίσει και τις επτά γέφυρες
χωρίς να περάσει από καμία περισσότερες από μία φορές;
Σκεφτείτε το για λίγο.
Να το πάρει το ποτάμι;
Καλύτερα να το πάρει.
Είναι αδύνατο.
Προσπαθώντας να εξηγήσει γιατί, ο διάσημος μαθηματικός Λέοναρντ Όιλερ οδηγήθηκε
στην εφεύρεση ενός νέου κλάδου των Μαθηματικών.
Ο Καρλ έγραψε στον Όιλερ ζητώντας βοήθεια για το πρόβλημα.
Ο Όιλερ αρχικά απέρριψε την ερώτηση ως άσχετης με τα Μαθηματικά.
Αλλά όσο την πάλευε,
τόσο φαινόταν ότι τελικά ίσως υπήρχε κάτι.
Η απάντηση που βρήκε είχε να κάνει με ένα είδος γεωμετρίας,
που δεν υπήρχε ακόμα· κάτι που ονόμασε Γεωμετρία της Θέσης,
που τώρα είναι γνωστή ως Θεωρία Γράφων.
Η πρώτη ενόραση του Όιλερ
ήταν ότι η διαδρομή ανάμεσα στην είσοδο και την έξοδο σε ένα νησί ή όχθη
δεν είχε σημασία.
Έτσι, ο χάρτης μπορούσε να απλοποιηθεί με καθεμία από τις τέσσερις χερσαίες εκτάσεις
να αναπαρίστανται από ένα σημείο,
αυτό που σήμερα ονομάζουμε κόμβο,
και γραμμές, ή ακμές, ανάμεσά τους να αναπαριστούν τις γέφυρες.
Αυτό το απλοποιημένο γράφημα μάς επιτρέπει
να μετρήσουμε εύκολα τον βαθμό κάθε κόμβου,
δηλαδή τον αριθμό των γεφυρών που αγγίζει κάθε χερσαία έκταση.
Γιατί έχουν σημασία οι βαθμοί;
Σύμφωνα με τους κανόνες του προβλήματος,
από τη στιγμή που ο ταξιδιώτης έφτασε σε μια χερσαία έκταση από μια γέφυρα,
θα πρέπει να φύγει από μια διαφορετική γέφυρα.
Με άλλα λόγια, οι γέφυρες, που οδηγούν προς και από κάθε κόμβο σε κάθε διαδρομή,
πρέπει να σχηματίζουν διακριτά ζευγάρια,
που σημαίνει ότι το πλήθος των γεφυρών που ακουμπούν σε κάθε χερσαία έκταση
πρέπει να είναι άρτιο.
Οι μόνες δυνατές εξαιρέσεις θα μπορούσαν να είναι οι τοποθεσίες της εκκίνησης
και τερματισμού της διαδρομής.
Αν δούμε το γράφημα, είναι φανερό ότι και οι τέσσερις κόμβοι έχουν περιττό βαθμό.
Έτσι, ανεξάρτητα από το ποια διαδρομή επιλεγόταν,
κάποια στιγμή, μια γέφυρα θα έπρεπε να διασχιστεί δύο φορές.
Ο Όιλερ χρησιμοποίησε αυτήν την απόδειξη για να διατυπώσει μια γενική θεωρία,
που εφαρμόζεται σε όλα τα γραφήματα με δύο ή περισσότερους κόμβους.
Ένα μονοπάτι Όιλερ, που περνά από κάθε ακμή ακριβώς μία φορά
είναι δυνατό σε μία από τις δύο περιπτώσεις.
Η πρώτη είναι όταν υπάρχουν ακριβώς δύο κόμβοι με περιττό βαθμό,
δηλαδή όλοι οι υπόλοιποι είναι άρτιοι.
Εκεί, το σημείο εκκίνησης είναι ένας από τους περιττούς κόμβους
και το τερματικό σημείο είναι το άλλο.
Η δεύτερη περίπτωση είναι όταν όλοι οι κόμβοι έχουν άρτιο βαθμό.
Τότε το μονοπάτι Όιλερ ξεκινά και σταματά στην ίδια τοποθεσία,
που το κάνει κάτι που ονομάζεται κύκλωμα Όιλερ.
Πώς, λοιπόν, θα δημιουργούσατε ένα μονοπάτι Όιλερ στο Κένινγκσμπεργκ;
Είναι απλό.
Απλά αφαιρέστε μια από τις γέφυρες.
Τελικά, η Ιστορία δημιούργησε ένα μονοπάτι Όιλερ από μόνη της.
Κατά τη διάρκεια του Β' Παγκοσμίου Πολέμου,
η Σοβιετική Αεροπορία κατέστρεψε δύο από τις γέφυρες της πόλης,
καθιστώντας το μονοπάτι Όιλερ δυνατό.
Αν και, για να είμαστε δίκαιοι, μάλλον δεν ήταν αυτή η πρόθεσή της.
Αυτοί οι βομβαρδισμοί λίγο-πολύ έσβησαν το Κένινγκσμπεργκ από τον χάρτη
και ξαναχτίστηκε αργότερα ως η ρωσική πόλη Καλίνινγκραντ.
Έτσι, ενώ το Κένινγκσμπεργκ και οι επτά γέφυρές του δεν υπάρχουν πια,
θα μείνουν για πάντα στην Ιστορία χάρη στον φαινομενικά τετριμμένο γρίφο
που οδήγησε στην εμφάνιση ενός νέου κλάδου των Μαθηματικών.
Lo pasarás mal si buscas Köningsberg en un mapa moderno.
Pero un rasgo particular de su geografía
la hizo una de las ciudades más famosas en matemáticas.
Esta ciudad alemana medieval descansaba en ambos lados del río Pregel.
En el centro tenía dos grandes islas.
Ambas estaban conectadas entre sí y hacia las orillas del río
por siete puentes.
Carl Gottlieb Ehler, matemático devenido en alcalde de un pueblo cercano,
se obsesionó con esas islas y puentes.
Seguía repitiéndose una sola pregunta:
¿Qué ruta le permitiría a alguien cruzar los siete puentes
atravesando cada uno una sola vez?
Piénsalo por un momento.
7
6
5
4
3
2
1
¿Te rindes?
Deberías.
Es imposible.
Al intentar explicar por qué el célebre matemático Leonhard Euler
creó un nuevo campo en las matemáticas.
Carl le escribió a Euler pidiendo ayuda con el problema.
Euler primero ignoró la pregunta al no tener nada que ver con las matemáticas.
Pero entre más enfrentaba el problema
más le parecía que podría haber algo allí después de todo.
La respuesta con la que lo resolvió tenía que ver con un tipo de geometría
que no existía aún, la llamó la Geometría de la Posición,
ahora conocida como Teoría de Grafos.
La primera percepción de Euler
fue que el camino que se tomaba para entrar a una isla y salir de ella
no importaba realmente.
Así, el mapa podía ser simplificado con cada una de las 4 masas de tierra
representadas con un punto,
es lo que ahora llamamos nodo,
y líneas, o arcos, entre ellos para representar los puentes.
Este grafo simplificado nos permite fácilmente contar el grado de cada nodo.
O sea la cantidad de puentes que toca cada masa de tierra.
¿Por qué importan los grados?
Bien, según las reglas del desafío,
una vez que los viajeros lleguen a tierra por un puente,
tendrán que salir de la misma por otro puente.
O sea, los puentes que conducen desde y hacia cada nodo en cualquier ruta
deben pasar en distintos pares,
es decir que la cantidad de puentes que toca cada masa de tierra visitada
debe ser par.
Las únicas posibles excepciones podrían ser al principio
y al final del paseo.
Viendo el grafo, se observa que los cuatro nodos tienen grados impares.
Así que en cualquier camino que se tome,
en un punto, habrá que cruzar un puente dos veces.
Euler usó esta prueba para formular una teoría general
que se aplica a todos los grafos que dos o más nodos.
Un camino euleriano que visita cada arco solo una vez
solo es posible en uno de dos escenarios.
El primero es cuando hay exactamente dos nodos de grado impar
lo que significa que los demás son pares.
Así, el punto de partida es uno de los nodos impares,
y el punto de llegada es el otro.
El segundo escenario es cuando todos los nodos son de grado par.
Entonces, el camino euleriano empezará y terminará en el mismo lugar,
lo que crea algo conocido como ciclo euleriano.
Entonces ¿cómo crearías un camino euleriano en Königsberg?
Es muy simple.
Solo quitamos cualquier puente.
Resulta que la historia creó un camino euleriano por sí misma.
En la 2da Guerra Mundial, los soviéticos destruyeron dos puentes de la ciudad,
haciendo posible un camino euleriano.
Aunque, para ser justos, esa no era probablemente su intención.
Estos bombardeos casi borraron Königsberg del mapa,
y luego fue reconstruida como la ciudad rusa de Kaliningrado.
Aunque Königsberg y sus siete puentes ya no estén con nosotros,
serán recordados en la historia por el acertijo aparentemente trivial
que llevo a la creación de un campo totalmente nuevo en las matemáticas.
Vous aurez beaucoup de mal à trouver Königsberg sur une carte moderne
mais une particularité géographique
a fait d'elle l'une des villes les plus célèbres des mathématiques.
Cette ville médiévale allemande était traversée par la rivière Pregel.
En son centre, il y avait deux grandes îles.
Ces deux îles étaient reliées entre elles et aux berges
par sept ponts.
Carl Gottlieb Ehler, un mathématicien devenu ensuite maire d'une ville proche,
en fit son idée fixe.
Il en revenait toujours à la même question :
quel trajet permettrait à quelqu'un de traverser l'ensemble des sept ponts
en ne les franchissant chacun qu'une seule fois ?
Réfléchissez-y un instant.
7
6
5
4
3
2
1
Vous jetez l'éponge ?
Vous devriez.
C'est impossible.
En tentant d'expliquer pourquoi, le célèbre mathématicien Leonhard Euler
inventa une nouvelle branche des mathématiques.
Carl écrivit à Euler pour lui demander son aide.
Dans un premier temps,
Euler écarta le problème, qui ne concernait pas les maths.
Mais plus il s'interrogeait,
plus il lui semblait que finalement, il y avait là quelquechose.
Il trouva la réponse grâce à une branche de la géométrie
qui n'existait pas encore et qu'il nomma Géométrie de position,
désormais connue comme la Théorie des graphes.
La première idée d'Euler
était que le trajet emprunté pour entrer sur une île ou une berge et la quitter
n'avait pas vraiment d'importance.
Donc, la carte pouvait être simplifiée en représentant les quatre zones de terre
par un simple point,
que nous appellerons nœud,
reliés par des lignes ou des arcs représentant les ponts.
Ce graphe simplifié nous permet de compter facilement les degrés de chaque nœud.
C'est-à-dire le nombre de ponts partant de chaque rive.
Pourquoi les degrés sont-ils importants ?
Selon les règles du défi,
une fois arrivé sur la terre par un pont,
le voyageur doit en repartir par un autre pont.
Autrement dit, les ponts menant d'un nœud à un autre
doivent, pour chaque parcours, aller par paire,
ce qui signifie que le nombre de ponts menant aux différentes berges visitées
doit être pair.
Les seules exceptions possibles seraient le point de départ
et d'arrivée du trajet.
Sur le graphe, on voit que les quatre nœuds ont un degré impair.
Du coup, peu importe le trajet choisi,
à un moment ou à un autre, l'un des ponts devra être traversé deux fois.
Euler mit cette preuve à profit pour formuler une théorie générale
s'appliquant à tous les graphes comportant au moins deux nœuds.
Un chemin eulérien ne passant qu'une fois par chaque sommet
n'est possible que dans un cas sur deux.
Dans le premier, il y a exactement deux nœuds de degré impair,
tous les autres étant donc pairs.
Dans ce cas là, le point de départ est l'un des nœuds impairs
et l'autre, le point d'arrivée.
Dans le deuxième cas, tous les nœuds sont de degré pair.
Le chemin eulérien commence et s'achève alors au même point ;
de fait, on le nomme également cycle eulérien.
Du coup, comment créer un chemin eulérien à Königsberg ?
C'est simple.
Il suffit de supprimer l'un des ponts.
Et il s'avère que l'Histoire en a elle-même créé un.
Pendant la seconde guerre mondiale, les forces aériennes soviétiques
ont détruit deux des ponts de la ville, ouvrant la voie à un chemin eulérien.
Mais, pour être honnête, ce n'était sans doute pas intentionnel.
Ces bombardement ont pratiquement rayé Königsberg de la carte.
Elle fut ensuite reconstruite pour devenir la ville russe de Kaliningrad.
Königsberg et ses sept ponts ne sont peut-être plus aujourd'hui,
mais ils resteront dans l'Histoire comme l'énigme en apparence triviale
à l'origine d'une branche complètement nouvelle des mathématiques.
יהיה לכם קשה למצוא את קניגסברג בכל מפה מודרנית בה תעיינו,
אבל מאפיין אחד מוזר בגיאוגרפיה שלה
הפך אותה לאחת הערים המפורסמות ביותר בתחום המתמטיקה.
העיר הגרמנית מימי הביניים שוכנת על שתי גדות נהר פרגל.
במרכזו היו שני איים גדולים.
שני האיים היו מחוברים ביניהם וכן מחוברים לגדות הנהר
על ידי שבעה גשרים.
קארל גוטליב אהלר, מתמטיקאי שהפך מאוחר יותר לראש העיר של עיירה סמוכה,
היה אובססיבי לגבי האיים והגשרים הללו.
הוא תמיד חזר להתחבט באותה שאלה:
איזה מסלול יאפשר חצייה של כל שבעת הגשרים
מבלי לחצות אף אחד מהם פעמיים?
חישבו על כך לרגע.
7
6
5
4
3
2
1
ויתרתם?
כדאי שתוותרו.
זה בלתי אפשרי.
אבל הניסיון להוכיח זאת הוביל את המתמטיקאי המפורסם לאונרד אוילר
לגילוי תחום חדש במתמטיקה.
קארל פנה בכתב לאוילר בבקשת עזרה עם הבעיה.
אוילר טען בתחילה שלבעיה אין בכלל קשר למתמטיקה,
אבל ככל שהוסיף להתחבט בבעיה,
כך הלך והתבהר לו שאולי קשר שכזה אכן קיים.
הפתרון שהגיע אליו התבסס על תחום בגיאומטריה
שלא היה קיים אז, תחום שהוא כינה בשם גיאומטריה של מיקום,
או בשמו הנוכחי תאוריית הגרפים.
האבחנה הראשונה אליה הגיע אוילר
היא שהמסלול המסויים שבו נבחר להכנס ולצאת מאי או מגדה
הינו חסר כל חשיבות.
לכן, ניתן לפשט את המפה לכזו שבה כל אחת מארבע היבשות
מיוצגת על ידי נקודה בודדה,
לה אנו קוראים כיום בשם צומת,
עם קווים או קשתות המקשרות בינהם ומייצגות את הגשרים.
וגרף פשוט זה, מאפשר לנו לספור בקלות את הדרגה של כל צומת,
שמשמעה מספר הגשרים המחוברים לכל יבשה.
למה הדרגה חשובה?
ובכן, לפי חוקי המשחק,
ברגע שנוסע מגיע ליבשה דרך אחד הגשרים,
הוא יאלץ לעזוב אותה דרך גשר אחר.
במילים אחרות, הגשרים הנכנסים ויוצאים מכל צומת בכל מסלול שהוא
חייבים להתקיים בזוגות,
כלומר, מספר הגשרים המחוברים לכל יבשה בה מבקרים
חייב להיות זוגי.
החריגה היחידה מתנאי זה קשורה במיקום צומת ההתחלה
וצומת הסיום של המסלול.
במבט על הגרף, ניתן לראות שלכל הצמתים יש דרגה אי זוגית.
אז לא חשוב באיזה מסלול בוחרים,
בשלב כלשהו, נאלץ לחצות את אותו גשר פעמיים.
אוילר השתמש בהוכחה זו לניסוח תורה שלמה
שתקפה עבור כל גרף שהוא בעל שני צמתים או יותר.
מסלול אוילר שמבקר בכל קשת של גרף פעם אחת בדיוק
קיים עבור שני מצבים בלבד.
במצב הראשון ישנם בדיוק שני צמתים מדרגה אי זוגית,
וכל שאר הצמתים הם זוגיים.
במצב זה, נקודת ההתחלה היא באחד הצמתים האי זוגיים,
ונקודת הסוף היא בשנייה.
במצב השני כל הצמתים הם בעלי דרגה זוגית.
במצב זה, מסלול אוילר יתחיל ויסתיים באותה נקודה,
לכן הוא קרוי לעיתים בשם מעגל אוילר.
אז איך ניתן ליצור מסלול אוילר בקניגסברג?
פשוט.
הסירו גשר אקראי אחד בלבד.
והסתבר, שההיסטוריה יצרה מסלול אוילר משלה.
בזמן מלחמת העולם השנייה, חיל האויר הסובייטי הרס שניים מגשרי העיר,
ובעשותו כך סלל את הדרך לקיום מסלול אוילר.
אולם אם להיות כנים, זה ודאי לא נעשה בכוונה תחילה.
ההפצצות האלו למעשה, מחקו את קניגסברג מהמפה,
וזאת נבנתה לאחר מכן כעיר הרוסייה קלינינגרד.
אז למרות שקניגסברג ושבעת גשריה כבר אינם קיימים
הם יחרטו בדפי ההיסטוריה בשל החידה הפשוטה למראה
שהובילה לגילוי תחום חדש לגמרי במתמטיקה.
Königsberg ćete teško pronaći na današnjoj zemljopisnoj karti,
ali jedna dosjetka vezana za njegov tlocrt
učinila ga je jednim od najslavnijih gradova vezanih uz matematiku.
Srednjovjekovni njemački grad ležao je na obje strane rijeke Pregel.
U središtu su bila dva velika otoka.
Dva otoka bila su povezana međusobno i s obalama rijeke
pomoću sedam mostova.
Carl Gottlieb Ehler, matematičar koji je postao gradonačelnik obližnjeg grada,
postao je opsjednut ovim otocima i mostovima.
Stalno se vraćao na isto pitanje:
na koji način netko može prijeći svih sedan mostova
tako da svaki most prijeđe samo jednom?
Razmislite o tome na trenutak.
7
6
5
4
3
2
1
Odustajete?
Trebali biste.
To nije moguće učiniti.
Ali pokušaj objašnjavanja zašto je tako vodio je matematičara Leonharda Eulera
do stvaranja novog područja matematike.
Carl je pisao Euleru moleći ga za pomoć.
Euler je najprije odbacio problem jer je vjerovao da nema veze s matematikom.
Ali što je više razmišljao o njemu,
činilo se više mogućim da se u njemu nešto krije.
Odgovor do kojeg je došao imao je veze s vrstom geometrije
koja još nije postojala, a koju je on nazvao Geometrija položaja,
a danas je poznata kao Teorija grafova.
Eulerova prva spoznaja
bila je da ruta između stupanja na otok ili obalu rijeke i napuštanja istog
zapravo nije važna.
Prema tome, karta se može pojednostavniti tako da se svaki od četiri kopnena čvora
prikaže pomoću točke,
koju ćemo zvati vrh,
a linije koje prikazuju mostove, zvat ćemo bridovi.
Na ovom jednostavnom grafu lako možemo odrediti stupanj svakog vrha.
To je broj mostova kojim je svaki kopneni čvor povezan.
Zašto je stupanj važan?
Prema pravilima izazova,
kad putnik stigne na kopneni čvor pomoću jednog mosta,
mora ga napustiti prelazeći preko drugog.
Drugim riječima, mostovi koji vode do vrha i s njega na bilo kojoj ruti
moraju se pojavljivati u parovima,
što znači da broj mostova koji dodiruju svaki prijeđeni čvor
mora biti paran.
Jedine moguće iznimke bile bi
početak i kraj šetnje.
Gledajući graf, postaje očito da sva četiri vrha imaju neparan stupanj.
Pa koji god put odaberemo,
u jednom trenutku, jedan od mostova moramo prijeći dvaput.
Euler je pomoću ovog dokaza oblikovao opću teoriju
koja se odnosi na sve grafove s dva i više vrha.
Eulerova staza kod koje se svaki vrh prelazi jednom
moguća je jedino u dva slučaja.
Prvi je kad postoje točno dva vrha neparnog stupnja,
pa su svi ostali parni.
Tada je početna točka jedan od dva neparna vrha,
a kraj šetnje je drugi.
Drugi slučaj je kada su svi vrhovi parnog stupnja.
Tad će Eulerova staza započeti i završiti u istom vrhu,
što se u teoriji grafova zove Eulerova tura.
Dakle, kako kreirati Eulerovu stazu u Königsbergu?
Jednostavno je.
Samo treba ukloniti jedan most.
Dogodilo se da je povijest sama stvorila Eulerovu stazu.
U II. svjetskom ratu Sovjetske zračne sile uništile su jedan od dva gradska mosta,
pa je Eulerova staza postala moguća.
Doduše, to vjerojatno nije bila njihova namjera.
Bombardiranje je gotovo izbrisalo Königsberg s karte,
te je poslije ponovo izgrađen kao ruski grad Kaliningrad.
Iako Königsberg i njegovih sedam mostova više ne postoje,
bit će zapamćeni u povijesti zbog naizgled trivijalne zagonetke
koja je vodila do stvaranja potpuno nove grane matematike.
Hiába is keresnénk Königsberget egy mai térképen,
különös földrajzi helyzete folytán
mégis az egyik leghíresebb várossá vált a matematikában.
A középkori német város a Pregel folyó két partján terült el.
Közepén volt két nagy sziget.
A két szigetet egymással és a partokkal
hét híd kötötte össze.
Carl Gottlieb Ehler matematikus, egy közeli város későbbi polgármestere
e szigeteknek és hidaknak megszállottjává vált.
Folyton ugyanahhoz a kérdéshez kanyarodott vissza:
Melyik az az út, amely mentén átmehetünk minden hídon,
de mindegyiken csak egyszer?
Gondolkodjunk csak egy pillanatig.
7
6
5
4
3
2
1
Feladják?
Fel kéne.
Nincs ilyen.
Leonhard Euler, a neves matematikus, amikor megpróbálta ezt megmagyarázni,
a matematika egy új területét hozta létre.
Carl írt Eulernek, hogy segítsen megoldani a problémát.
Euler először elhessentette a kérdést, mint aminek semmi köze a matematikához.
de minél többet nyűglődött rajta,
annál inkább úgy tűnt, hogy talán mégis lenne valami köze.
A válasz, amit talált, a geometriának olyan ágához köthető,
ami ekkor még nem igazán létezett, és amit ő a helyek geometriájának hívott,
ma pedig gráfelmélet néven ismert.
Euler első meglátása az volt,
hogy nem számít, hogy a szigeteken és a partokon
milyen úton megyünk.
Így a térkép leegyszerűsíthető oly módon, hogy a négy földdarabot
egy-egy pont reprezentálja –
ezeket csúcsoknak nevezzük –,
a hidakat pedig vonalaknak vagy éleknek, amelyek összekötik a pontokat.
E leegyszerűsített ábra lehetővé teszi, hogy megszámoljuk minden csúcs fokszámát.
Ez a szám az adott szárazföldet érintő hidak száma.
Miért érdekes a fokszám?
A séta szabályai szerint
ha egyszer az utazó megérkezik a szárazföldre az egyik hídon,
akkor egy másikon keresztül kell onnan távoznia.
Vagyis az egy csúcsba be- és onnan kifutó hidak
egyértelműen megfeleltethetők egymásnak,
ami azt jelenti, hogy minden földdarabot
páros számú hídnak kell érintenie.
Kivétel ez alól csak
a séta kezdő- és végpontja lehet.
Ha ránézünk a gráfra, rögtön látszik, hogy mind a négy csúcs fokszáma páratlan.
Bármelyik utat is választjuk tehát,
valamelyik pontnál az egyik hidat kétszer kell használjuk.
Euler ezt a bizonyítást használta egy általános tétel megfogalmazására,
amely igaz minden olyan gráfra, amelynek legalább két csúcsa van.
Az Euler-vonal, amely minden élt csak egyszer használ,
csupán az alábbi két eset valamelyikében lehetséges:
Az első, amikor pontosan két olyan csúcs van, melyeknek a fokszáma páratlan,
azaz az összes többié páros.
Ilyenkor a kezdőpont az egyik páratlan fokszámú csúcs,
a végpont pedig a másik.
A másik eset, amikor minden csúcs fokszáma páros.
Ilyenkor az Euler-vonal kezdő- és végpontja megegyezik,
ezt Euler-körnek is nevezik.
Tehát hogyan tudnánk létrehozni egy Euler-vonalat Königsbergben?
Egyszerűen.
Hagyjunk el egy hidat.
A történelem megcsinálta a maga Euler-vonalát.
A 2. világháború alatt a szovjet légierő a város két hídját megsemmisítette,
ezzel az Euler-vonalat könnyen megrajzolhatóvá tette.
Az igazsághoz tartozik, hogy valószínűleg nem ez volt a céljuk.
Ezek a bombák jócskán letörölték Königsberget a térképről.
hogy azután orosz városként épüljön újjá, Kalinyingrád néven.
Így, bár Königsberget és hét hídját már nem lehet körbejárni,
mindenkorra emlékezetes marad e látszólag egyszerű rejtvény révén,
amely a matematika egy új ágának felbukkanásához vezetett.
Ti sarà difficile trovare Königsberg in qualsiasi cartina moderna
ma una particolare stranezza nella sua geografia
l'ha resa una delle città più famose nella matematica.
La città medievale tedesca si estende su entrambe le sponde del fiume Pregel.
Al centro c'erano due grandi isole.
Le due isole erano collegate tra di loro e agli argini del fiume
da sette ponti.
Carl Gottlieb Ehler, un matematico che poi divenne sindaco di una città vicina,
si ossessionò con queste isole e i loro ponti.
Continuava a pensare a una domanda:
Quale percorso avrebbe permesso di attraversare tutti e sette i ponti
senza attraversarne nessuno più di una volta?
Pensaci un momento.
7
6
5
4
3
2
1
Ti arrendi?
Dovresti.
Non è possibile.
Ma provando a spiegarne il perché il famoso matematico Leonhard Euler
inventò un nuovo campo della matematica.
Carl scrisse a Euler chiedendo aiuto per il problema.
Euler inizialmente respinse il problema dicendo che non concerneva la matematica.
Ma più si sforzava,
più sembrava che ci potesse essere qualcosa dopotutto.
La risposta che gli venne in mente aveva a che fare con un tipo di geometria
che non esisteva ancora, che chiamò la Geometria Topologica,
ora conosciuta come Teoria dei Grafi.
La prima intuizione di Euler
fu che il percorso da intraprendere entrando nell'isola o sulla riva e uscirne
non importava davvero.
Così, la mappa poteva essere semplificata in modo che ognuno delle quattro terre
rappresentasse un punto singolo,
che ora chiamiamo un Nodo,
con linee, o collegamenti, tra di loro per rappresentare i ponti.
Questo grafico semplificato ci permette di contare facilmente i gradi di ogni nodo.
Quello è il numero di ponti che ciascuna terra tocca.
Perché i gradi sono importanti?
Beh, stando alle regole della sfida,
una volta che i viaggiatori arrivano su una terra da un ponte,
dovranno lasciarla attraverso un altro ponte.
In altre parole, i ponti tra ogni nodo o tragitto
devono presentarsi in coppie distinte,
cioè il numero di ponti che toccano ogni terra visitata
deve essere pari.
L'unica possibile eccezione possono essere i punti di inizio
e fine del tragitto.
Guardando il grafico, è chiaro che tutti e quattro i nodi hanno un grado dispari.
Perciò, non importa che percorso scegli,
ad un certo punto, un ponte dovrà essere attraversato due volte.
Euler usò questa dimostrazione per formulare una teoria generale
da applicare a tutti i grafici con due o più nodi.
Un cammino Euleriano, che attraversa ogni margine solo una volta
è possibile solo in due modi.
Il primo è quando ci sono esattamente due nodi di grado dispari,
e quindi i restanti sono pari.
Quindi, il punto di inizio è uno dei nodi dispari,
e il punto di fine è l'altro.
Il secondo è quando tutti i nodi sono di grado pari.
Perciò, il cammino Euleriano inizierà e terminerà nello stesso punto,
che lo rende tale da essere chiamato circuito Euleriano.
Quindi, come creare un cammino Euleriano a Königsberg?
è semplice.
Basta eliminare un ponte qualsiasi.
Ed è successo che la storia ha creato un cammino Euleriano da sola.
Durante la II Guerra Mondiale, gli aerei sovietici distrussero due dei ponti,
realizzando facilmente un cammino Euleriano.
Anche se, onestamente, non credo fosse loro intenzione.
Questi bombardamenti quasi spazzarono via Königsberg dalla mappa,
e in seguito fu ricostruita come città russa con il nome di Kaliningrad.
Perciò anche se Königsberg e i suoi sette ponti possono non esistere più,
saranno ricordati nella storia per l'enigma apparentemente triviale
che portò alla nascita di un intero nuovo campo della matematica.
現代の地図でケーニヒスベルクを 見つけるのは不可能です
しかしこの街は １つの特徴的な地形により
数学の分野で 最も有名な街の１つになったのです
この中世ドイツの街はプレーゲル川の 両側にまたがっており
その中心には２つの島がありました
２つの島と川岸はそれぞれ
７本の橋でつながっていました
数学者で後に近くの街の市長になった カール・ゴットリーブ・エーラは
これらの島と橋に関する
１つの問題に取り付かれるようになりました
「どの経路なら 同じ橋を２度渡ることなく
７本全ての橋を渡れるのだろう？」 というものです
ちょっと考えてみてください
７
６
５
４
３
２
１
降参ですか？
当然です
不可能なのです
一方 その理由の説明を試みる過程で 有名な数学者レオンハルト・オイラーは
数学の新しい分野を生み出しました
カールは手紙を書き オイラーに助けを求めました
オイラーは最初はこの問題は 数学に無関係として片付けました
しかしこの問題と格闘するほど
それ以上の何かがあるのではないかと 考えるようになりました
彼が出した答えは それまで存在しなかった新しい幾何学の分野
彼自身は「位置の幾何学」と呼び
現在はグラフ理論というものに 関係していました
オイラーの最初の洞察は
どの経路で島や川岸を往来したかは
関係がないということでした
このように地図上の４つの土地は
現在我々が頂点と呼ぶ
１つの点として
橋は頂点の間の直線 もしくは辺として単純化できます
そしてこの簡素化されたグラフは 各頂点の次数
つまり各地点につながる橋の数を 数えやすくします
ではなぜ次数が重要なのでしょうか？
このクイズのルールでは
旅人がある橋を通って １つの土地に到着したら
他の橋を通って 出て行かなければなりません
これはルート上にある全ての頂点で 到着と出発のための橋が
対になる必要があるということです
すなわち個々の土地につながる橋の数は
偶数でなければいけないということです
唯一例外が認められるのは
出発地点とゴール地点です
この図を見れば４箇所の頂点全てが 奇数の次数を持っていることは明らかです
したがってどのような道筋であっても
どこかの時点で橋は ２度渡らないといけないのです
オイラーはこの証明から ２つ以上の頂点を持つ全てのグラフに当てはまる
一般理論を作りました
全ての辺を１度だけ通るオイラー路には
２つのシナリオしかありません
最初のシナリオは ２つの頂点だけが奇数の次数を持ち
残りの頂点の次数が偶数のものです
この場合には奇数の次数を持つ 頂点の１つが出発地点となり
もう１つの頂点がゴール地点になります
２つ目のシナリオは全ての頂点が 偶数の次数を持つ場合です
この場合は出発地点とゴール地点は 同じ場所になり
オイラー閉路と呼ばれる回路を作ります
ではケーニヒスベルクで オイラー路を作るにはどうしたらよいでしょうか
答えは簡単です
どれか橋を１本取り除けばいいのです
その後 歴史は自ら オイラー路を作りました
第二次世界大戦の最中に ソビエト空軍が街の２本の橋を破壊したため
オイラー路が簡単に作れるようになりました
公平を期して言えば ソビエトの目的は オイラー路ではなかったでしょう
これらの爆撃によって ケーニヒスベルクは正に地図から消し去られ
後日カリーニングラードという ロシアの街として再建されました
だから７本の橋があるケーニヒスベルクの街は もう存在しないかもしれませんが
他愛ないクイズから 数学の新しい分野を生み出した街として
歴史的に記憶されることでしょう
현대의 지도에서 쾨니스버그를 찾으려면 어려울 겁니다.
하지만 지리적으로 매우 특이한 곳이었기 때문에
이곳은 수학적으로 가장 유명한 도시 중 하나가 되었습니다.
중세 독일에 있던 이 도시는 프레겔 강의 양변에 놓여 있었어요.
그 중심에는 두 개의 큰 섬이 있었고
두 섬 사이와 두 섬과 강의 양쪽 둑 사이를
일곱 개의 다리가 연결하고 있었어요.
훗날 인근 마을의 시장인 된 칼 고트립 일러라는 수학자가
차츰 그 섬과 다리에 관해 고민하게 되었어요.
그는 단 한가지 문제에 계속 골몰했죠.
어떤 경로로 가면 일곱 개의 다리를 모두 건너면서도
각 다리를 단 한 번씩만 건너게 될까?
여러분도 잠시 생각해 보세요.
7
6
5
4
3
2
1
포기할 건가요?
당연히 그래야죠.
그건 불가능하니까요.
하지만 왜 불가능한지를 설명하는 와중에, 유명한 수학자 레온하드 오일러는
수학의 새로운 분야를 창시하게 되었어요.
칼은 오일러에게 문제 푸는 걸 도와달라고 편지를 썼어요.
오일러는 처음에는 이 문제가 수학과는 무관하다고 생각해 무시했고요.
하지만 그 문제와 씨름을 거듭할수록
뭔가 중요한 사실이 있을 것만 같았죠.
그가 찾아낸 해답은 일종의 기하학과 관련이 있었는데
아직 존재하지 않았던 분야였기 때문에, 그는 이를 위상 기하학이라 불렀어요
현대에는 그래프 이론이라고 하죠.
오일러가 처음 통찰했던 사실은
둘 중 한 섬이나 한 쪽 강둑으로 들어갔다 나올 때 어떤 경로를 취할 것이냐는
전혀 중요하지 않다는 점이었어요.
그리하여 네 개의 땅을 결절(노드)이라 하는 하나의 점으로
각각 표시하고
땅덩어리 사이를 연결하는 다리를
선으로 표시하는 방식으로 지도를 단순화할 수 있었죠
이처럼 단순화된 그래프를 이용하면 각 결절의 등급을 헤아리기가 쉽습니다.
등급이란 각 땅이 맞닿는 다리의 수를 말합니다.
등급이 왜 중요할까요?
문제에서 제시된 규칙에 따르면
보행자가 일단 한 다리를 이용해서 어떤 땅에 도착하고 나면
반드시 다른 다리를 통해 그곳을 떠나야만 합니다.
달리 말하면, 어떤 경로를 택하든 각 결절에 연결되는 다리는
반드시 분리된 쌍으로 존재해야만 합니다.
결국 도착한 땅에 연결된 다리의 수가
반드시 짝수여야만 한다는 말입니다.
유일한 예외라면 여정의 출발 지점과
종료 지점일 겁니다.
그래프를 보면 네 개의 결절 모두 홀수의 등급을 가지고 있는게 확실하죠.
따라서 어떤 경로를 택하든 관계없이
어느 지점에선가는 한 다리를 두 번 건널 수밖에 없을 것입니다.
오일러는 이러한 증거를 이용해서 두 개 이상의 결절을 지닌
모든 그래프에 적용되는 일반화된 규칙을 수립했습니다.
각 경로를 오직 한 번만 지나게 되는 오일러의 길은
다음 두 경우에만 가능합니다.
첫째, 홀수 등급의 결절이 정확히 두 개만 존재하는 경우입니다.
나머지는 모두 짝수란 얘기겠죠.
이 경우 두 홀수 결절 중 하나가 출발점이고
나머지 하나는 종료점입니다.
둘째는 모든 결절이 짝수 등급인 경우입니다.
이런 오일러의 길에서는 출발점과 종료점이 같아집니다.
그래서 이런 길을 오일러의 순환로라고 부릅니다.
쾨니스버그에 오일러의 길을 만들려면 어떻게 하면 될까죠?
간단합니다.
아무 다리나 하나를 없애면 됩니다.
사실 역사상 오일러의 길이 그곳에 만들어진 적이 있었습니다.
이차대전 중에 소련의 공군이 이 도시의 다리 중 두 개를 폭파했거든요.
그 결과 오일러의 길이 간단하게 만들어졌죠.
물론 그들이 그러려고 했던 건 아니었겠지만요.
이 폭격으로 인해 쾨니스버그는 지도상에서 거의 사라지게 되었고
나중에 그곳은 러시아의 칼리닌그라드라는 도시로 재건되었습니다.
쾨니스버그와 그 일곱 다리는 더 이상 존재하지 않지만
사람들 기억속에는 영원히 남을 겁니다. 사소해 보이는 수수께기 하나 때문에
수학적으로 완전히 새로운 분야 하나가 탄생했으니까요.
Dziś trudno byłoby wam znaleźć Królewiec na mapie,
ale pewna jego geograficzna osobliwość
spowodowała, że Królewiec stał się jednym z najsłynniejszych miast w matematyce.
Przez to średniowieczne niemieckie miasto przepływała rzeka Pregoła.
Pośrodku rzeki leżały dwie duże wyspy.
Połączone były z lądem i między sobą
siedmioma mostami.
Carl Gottlieb Ehler, matematyk, a później burmistrz pobliskiego miasta,
miał obsesję na punkcie tych wysp i mostów.
Wciąż powracał do jednego pytania:
Która trasa umożliwiłaby przejście wszystkich siedmiu mostów
bez pokonania żadnego więcej niż raz?
Pomyślcie o tym przez chwilę.
7
6
5
4
3
2
1
Daliście sobie spokój?
Powinniście.
To niemożliwe.
Próby wyjaśnienia tej zagadki doprowadziły słynnego matematyka Leonharda Eulera
do stworzenia nowego działu w matematyce.
Carl pisał do Eulera z prośbą o pomoc.
Euler początkowo zignorował pytanie jako niezwiązane z matematyką.
Jednak im więcej nad nim myślał,
tym bardziej wydawało mu się, że coś w tym jednak jest.
Odpowiedź, na którą wpadł, związana była z działem geometrii,
który wtedy jeszcze nie istniał.
Nazwał go geometrią położenia, znaną dziś jako teoria grafów.
Euler doszedł do wniosku,
że kolejność przejścia mostów
nie ma tak naprawdę żadnego znaczenia.
Mapę można więc ograniczyć do przedstawienia czterech lądów,
oznaczonych przez pojedyncze punkty,
nazywanych dziś wierzchołkami.
Linie między nimi reprezentują mosty.
Ten uproszczony schemat pozwala nam łatwo policzyć łuki każdego wierzchołka.
Jest to liczba mostów, które dotyka każdy z lądów.
Dlaczego to ma takie znaczenie?
Zgodnie z zasadami,
jeśli człowiek wejdzie na ląd przez jeden most,
będzie musiał wejść na kolejny most, by opuścić ląd.
Innymi słowy, mosty prowadzące na każdy ląd i z niego
muszą łączyć się w pary.
To oznacza, że każdy z nich musi być połączony parzystą liczbą mostów z innymi.
Jedynym wyjątkiem są początek i koniec trasy.
Po spojrzeniu na schemat okazuje się,
że wszystkie lądy mają nieparzystą ilość łuków.
Obrana trasa nie ma więc znaczenia.
W którymś momencie jeden most będzie trzeba przekroczyć dwukrotnie.
Euler wykorzystał ten dowód do sformułowania ogólnej teorii
odnoszącej się do wszystkich grafów z dwoma lub większą liczbą łuków.
Łańcuch Eulera, w którym każdy most przekracza się tylko raz,
jest możliwy tylko w dwóch przypadkach.
Pierwszy przypadek to dokładnie dwa wierzchołki z nieparzystą liczbą łuków,
czyli że wszystkie pozostałe są parzyste.
Tymi dwoma wierzchołkami są punkt początkowy i punkt końcowy trasy.
W drugim przypadku wszystkie wierzchołki mają parzystą liczbę łuków.
Droga rozpoczyna się wtedy i kończy w tym samym miejscu,
co tworzy tak zwany cykl Eulera.
Jak więc stworzyć łańcuch Eulera w Królewcu?
To proste.
Wystarczy usunąć jeden most.
Okazuje się, że historia stworzyła już kiedyś własny łańcuch Eulera.
Podczas II wojny światowej radzieckie lotnictwo zniszczyło dwa mosty,
powodując, że łańcuch Eulera stał się możliwy.
Oczywiście nie o to chodziło radzieckim lotnikom.
Bombardowania w znacznej części zmiotły Królewiec z powierzchni ziemi.
Odbudowano go później jako rosyjskie miasto Kaliningrad.
Choć Królewca i jego siedmiu mostów już nie ma,
to zagadnienie siedmiu mostów zapisało się w historii
jako pozornie trywialna zagadka,
która zapoczątkowała nową dziedzinę matematyki.
Terão muita dificuldade em encontrar Königsberg em qualquer mapa moderno,
mas uma certa peculiaridade na sua geografia
tornou-a numa das cidades mais famosas da matemática.
A cidade medieval germânica situava-se de ambos os lados do Rio Pregel.
No centro havia duas grandes ilhas.
As duas ilhas estavam ligadas uma à outra e às margens do rio
por sete pontes.
Carl Gottlieb Ehler, um matemático
que veio a ser o prefeito duma cidade vizinha,
começou a ficar obcecado com estas ilhas e pontes.
Voltava sempre a uma única pergunta:
Que caminho permitiria que uma pessoa atravessasse as sete pontes
sem cruzar nenhuma delas mais do que uma vez?
Pensem nisso por instantes.
Desistem?
É melhor.
Não é possível.
Mas a tentativa de explicar porquê,
levou Leonhard Euler, o conhecido matemático,
a inventar uma nova área da matemática.
Carl escreveu a Euler, pedindo ajuda para o problema.
A princípio, Euler achou que o problema não tinha nada a ver com a matemática.
Mas quanto mais pensava nisso,
mais lhe parecia que, afinal, podia haver ali qualquer coisa.
A resposta que encontrou tinha a ver com um tipo de geometria
que ainda não existia e a que ele chamou a Geometria de Posição,
hoje conhecida por Teoria dos Grafos.
A primeira conclusão de Euler
foi que o caminho tomado entre a entrada de uma ilha ou de uma margem do rio
e a sua saída não era importante.
Portanto, o mapa podia ser simplificado representando por um simples ponto
cada uma das quatro massas terrestres,
aquilo a que hoje chamamos um nodo.
As pontes seriam representadas por linhas, ou arestas, entre elas.
Este grafo simplificado permite-nos contar facilmente os graus de cada nodo.
É o número de pontes em que cada massa terrestre toca.
Porque é que estes graus são importantes?
Segundo as regras do problema,
quando os viajantes chegassem a uma massa terrestre por uma ponte,
teriam que sair de lá por uma ponte diferente.
Por outras palavras, as pontes que chegavam a um nodo
e as que dele saiam
tinham que ocorrer em pares distintos,
ou seja, o número de pontes que tocavam em cada massa terrestre visitada
teria que ser par.
As únicas exceções possíveis seriam
a localização do início e a do fim da caminhada.
Olhando para o grafo, verifica-se
que todos os quatro nodos têm um grau ímpar.
Assim, seja qual for o caminho escolhido,
a certa altura, seria necessário cruzar duas vezes a mesma ponte.
Euler usou esta prova para formular uma teoria geral
que se aplica a todos os grafos com dois ou mais nodos.
Um caminho euleriano que visita cada aresta apenas uma vez
só é possível num de dois cenários.
O primeiro é quando há exatamente dois nodos de grau ímpar,
o que significa que todos os restantes são pares.
Aí, o ponto de partida é um dos nodos ímpar
e o ponto de chegada é o outro.
O segundo é quando todos os nodos são de grau par.
Aí, o caminho euleriano pode começar e terminar no mesmo local
o que também lhe dá o nome de circuito euleriano.
Então, como podíamos criar um caminho euleriano em Konigsberg?
Muito simplesmente.
Basta retirar qualquer uma das pontes.
Acontece que a História criou um caminho euleriano, por si mesma.
Durante a II Guerra Mundial,
a Força Aérea Soviética destruiu duas das pontes da cidade,
possibilitando um caminho euleriano.
Mas, para ser franco, provavelmente a intenção deles não era essa.
Esse bombardeamento quase varreu Konigsberg do mapa
que foi posteriormente reconstruída como a cidade russa de Kaliningrado.
Embora Konigsberg e as suas sete pontes talvez já não existam,
serão recordadas na História
por este quebra-cabeças aparentemente trivial
que levou ao aparecimento de toda uma nova área da matemática.
Seria difícil encontrar Königsberg em um mapa moderno,
mas uma particularidade em sua geografia
a tornou uma das mais famosas cidades da matemática.
A cidade medieval alemã ocupava as duas margens do rio Pregel.
No centro, ficavam duas grandes ilhas.
As conexões entre as duas ilhas e as margens do rio
se davam através de sete pontes.
Carl Gottlieb Ehler, um matemático que se tornaria prefeito numa cidade próxima,
ficou obcecado por essas ilhas e pontes.
Ele insistia em uma única questão:
qual caminho teria que ser feito para se cruzar as sete pontes
sem passar por uma ponte mais de uma vez?
Reflita por um momento.
[7]
[6]
[5]
[4]
[3]
[2]
[1]
Desistiu?
Muito bem.
É impossível.
Mas a tentativa de explicar o porquê levou o famoso matemático Leonhard Euler
a inventar um novo campo da matemática.
Carl pediu a Euler ajuda com o problema.
Euler a princípio pensou que a questão não tinha relação com matemática.
Mas quanto mais ele pensava,
mais parecia haver algo ali no fim das contas.
A solução que ele encontrou tinha a ver com um tipo de geometria
que ainda não existia, a qual ele nomeou "Geometria de Posição",
conhecida hoje como Teoria dos Grafos.
Euler concluiu primeiro
que o caminho percorrido dentro de uma ilha ou margem específica
não importava.
Assim, o mapa podia ser simplificado se cada porção de terra
fosse representada por um ponto,
o que nós hoje chamamos de vértice,
com linhas, ou arestas, entre eles representando as pontes.
Esse grafo simplificado nos permite contar os graus de cada vértice.
Esse é o número de pontes que cada porção de terra possui.
Qual a importância dos graus?
Segundo as regras do desafio,
quando viajantes entrarem numa porção de terra por uma ponte,
eles têm que sair dela por outra ponte.
Ou seja, as pontes que chegam e que saem de cada vértice
devem ocorrer em pares,
o que significa que o número de pontes em cada porção de terra visitada
deve ser par.
As únicas exceções seriam o começo
e o fim da caminhada.
Olhando para o grafo, fica evidente que todos os vértices têm grau ímpar.
Não importa o caminho escolhido,
em algum momento, uma ponte será cruzada duas vezes.
Euler usou essa prova para formular uma teoria geral
que se aplica a todo grafo com dois ou mais vértices.
Um caminho euleriano que passa apenas uma vez por cada aresta
só é possível num dos seguintes cenários.
O primeiro é quando existem exatos dois vértices de grau ímpar,
e todos os outros são pares.
Nesse caso, o ponto de partida é um dos vértices ímpares,
e o final é o outro.
O segundo é quando todos os vértices têm grau par.
Nesse caso, o caminho inicia e termina no mesmo local,
configurando o que chamamos de circuito euleriano.
Então, como um caminho euleriano poderia ser criado em Königsberg?
É simples.
É só remover uma das pontes.
Curiosamente, a história criou um caminho euleriano por conta própria.
Na 2ª Guerra Mundial, aviões soviéticos destruíram duas das pontes da cidade,
fazendo surgir um caminho euleriano.
Embora essa provavelmente não fosse sua intenção.
Os bombardeios praticamente varreram Königsberg do mapa,
e a cidade foi reconstruída pela Rússia sob o nome de Kaliningrado.
Mesmo que Königsberg e suas sete pontes não estejam mais entre nós,
elas ficarão para sempre na história por causa desse simples enigma
que deu origem a um ramo da matemática inteiramente novo.
Найти Кёнигсберг на современных картах вряд ли получится,
но именно одна его картографическая особенность
сделала город одним из самых известных в математике.
Средневековый город располагался на обоих берегах реки Прегель.
В центре города было два больших острова.
Оба острова друг с другом и с берегами соединяли
семь мостов.
Карлу Готтлибу Элеру, математику, ставшему впоследствии главой близлежащего города,
всё не давали покоя эти острова и их мосты.
Он всё больше задавался вопросом:
«Каким путём можно пройти все семь мостов,
но ни по одному из них не пройти дважды?»
Подумайте несколько секунд.
[7]
[6]
[5]
[4]
[3]
[2]
[1]
Сдаётесь?
Наверное, сдаётесь.
Да, это невозможно.
Однако в попытке объяснить почему, знаменитый математик Леонард Эйлер
изобрёл новое направление в математике.
Карл написал Эйлеру письмо и попросил помочь с задачей.
Эйлер вначале посчитал, что вопрос никак не связан с математикой.
Но чем дольше он думал над решением,
тем больше ему начинало казаться, что что-то тут не так.
Он нашёл ответ, который лежит в плоскости геометрии,
в ту пору ещё не существовавшей, которую он назвал позиционной геометрией
и которая сейчас известна под названием теории графов.
Первая мысль, осенившая Эйлера,
была о том, что маршрут от входа на остров или перехода на берег и до выхода оттуда
не имеет никакого значения.
Поэтому карту можно упрощённо изобразить как совокупность четырёх частей города,
каждая из которых представляет собой точку,
которую мы сейчас называем вершиной,
с линиями, или рёбрами, между ними, представленными мостами.
Упрощённый граф позволяет нам легко сосчитать рёбра каждой вершины.
Это число мостов, которые соединяют эту часть города.
Но зачем нам рёбра?
В соответствии с правилами задачи,
если путешественники попадают в эту часть города по одному мосту,
им надо выйти из неё через другой мост.
То есть мосты, ведущие к вершине и от неё по любому маршруту,
должны сочетаться в различных парах,
это означает, что число мостов, соединяющих каждую из частей города,
должно быть чётным.
Единственными исключениями могут быть точки начала
и конца маршрута.
На нашем графе мы видим на четырёх вершинах нечётное число ребёр.
Поэтому неважно, какой выбран путь,
в определённой точке какой-то мост придётся пересекать дважды.
Эйлер использовал это доказательство, чтобы сформулировать общую теорию,
которая относится ко всем графам с двумя и более вершинами.
Путь Эйлера, двигаясь по которому можно пройти по мостам только один раз,
возможен в одном из двух случаев.
Первый: когда есть ровно две вершины, имеющие нечётное число рёбер,
а остальные должны иметь чётное число рёбер.
В данном случае начинать двигаться надо с одной из нечётных вершин,
а заканчивать — на второй вершине.
Второй случай — это когда все вершины имеют чётное число рёбер.
В таком случае путь Эйлера начнётся и закончится в одной точке,
этот случай принято называть Эйлеровым циклом.
Так как же создать Эйлеров путь в Кёнингсберге?
Очень просто.
Надо просто убрать один из мостов.
И, похоже, история сама создала свой собственный Эйлеров путь.
Во время Второй мировой войны советские ВВС уничтожили два моста,
и путь Эйлера стал вполне возможен.
Хотя, по правде говоря, в планы лётчиков решение задачи не входило.
В результате бомбардировок Кёнигсберг был почти стёрт с лица земли,
а затем город отстроили заново и назвали советским Калининградом.
И хотя Кёнигсберга и его семи мостов больше не существует,
он вошёл в историю благодаря задаче, которая только кажется простой,
но именно её решение привело к появлению новой области математики.
คุณคงลำบากแน่ หากจะมองหา เคอนิกส์แบร์กบนแผนที่ยุคใหม่
แต่จุดหนึ่งที่น่าสนใจ ในภูมิศาสตร์ของมัน
ได้ทำให้มันเป็นหนึ่งในเมืองที่มี ชื่อเสียงที่สุดในโลกคณิตศาสตร์
เมืองเยอรมันยุคกลาง ตั้งอยู่บนสองฝั่งแม่น้ำพรีเกิล
ณ ใจกลางมีเกาะขนาดใหญ่ สองเกาะ
เกาะทั้งสองนี้เชื่อมต่อถึงกัน และยังเชื่อมต่อกับฝั่งแม่น้ำ
ด้วยสะพานทั้งเจ็ด
นักคณิตศาสตร์ คาร์ล ก็อตลีบพ์ อีเลอ ผู้ต่อมาเป็นนายกเทศมนตรีเมืองใกล้ ๆ
หมกมุ่นอยู่กับเกาะและสะพานเหล่านี้
เขาคิดย้อนทวนถึงปัญหาอยู่ข้อเดียว
ต้องใช้เส้นทางไหนดีจึงจะ ข้ามสะพานได้ครบทั้งเจ็ด
โดยที่ไม่ข้ามซ้ำสะพานเดิม
ลองหยุดคิดกันดูสักครู่
7
6
5
4
3
2
1
ยอมแพ้แล้วหรือ
ก็น่าอยู่หรอก
เพราะมันเป็นไปไม่ได้
แต่ความเพียรอธิบายสาเหตุ ทำให้ นักคณิตศาสตร์คนดัง ลีออนฮาร์ด ออยเลอร์
สรรค์สร้างคณิตศาสตร์สาขาใหม่
คาร์ลเขียนจดหมายถึงออยเลอร์ ให้ช่วยไขปริศนา
ครั้งแรกออยเลอร์ละเลยคำถามนี้ เพราะไม่ใช่เรื่องของคณิตศาสตร์
แต่ยิ่งเขาครุ่นคิดถึงมันมากเท่าไร
ก็ยิ่งดูเหมือนว่ามีอะไรสักอย่างอยู่ดี
คำตอบที่เขาค้นพบ เป็นเรื่องเกี่ยวกับเรขาคณิตชนิดหนึ่ง
ซึ่งยังไม่เคยมีมาก่อน เขาเรียกมันว่า เรขาคณิตของตำแหน่ง
ปัจจุบันคือทฤษฎีกราฟ
ข้อสังเกตแรกของออยเลอร์
คือเส้นทางที่เลือกระหว่างการเข้าไปใน เกาะหรือฝั่งแม่น้ำและการออกจากที่นั่น
อันที่จริงแล้วไม่ได้สำคัญนัก
ฉะนั้นจึงสามารถลดรูปแผนที่ให้ง่ายขึ้น โดยให้แต่ละผืนดินจากทั้งสี่แห่ง
ถูกแทนที่ด้วยจุดเดียว
ซึ่งปัจจุบันเราเรียกว่า โนด
ด้วยเส้น หรือ เอ็ดจ์ เชื่อมระหว่างโนด เพื่อเป็นตัวแทนของสะพาน
และกราฟที่ง่ายขึ้นนี้ช่วยให้เรา นับดีกรีของแต่ละโนดได้ง่ายดาย
ดีกรี คือจำนวนสะพานที่แต่ละ ผืนดินสัมผัส
ทำไมดีกรีจึงสำคัญน่ะหรือ
ก็เพราะตามกฎของคำท้า
เมื่อนักเดินทางไปถึง ผืนดินหนึ่งด้วยสะพานหนึ่งแล้ว
พวกเขาต้องออกจากผืนดินนั้น โดยใช้สะพานอื่น
ซึ่งก็คือ สะพานที่เข้าและออก จากแต่ละโนดในเส้นทางใดก็ได้
แต่ต้องมีเป็นคู่ ๆ ที่แตกต่างกัน
หมายความว่าจำนวนสะพาน ที่สัมผัสแต่ละผืนดินที่เดินผ่าน
ต้องเป็นจำนวนคู่
มีเพียงข้อยกเว้นที่เป็นไปได้ คือ ตำแหน่งของจุดเริ่มต้น
และจุดที่สิ้นสุดการเดิน
เมื่อมองไปที่กราฟ เป็นที่ชัดแจ้ง ว่า ทั้งสี่โนด มีดีกรีเป็นจำนวนคี่
ดังนั้น ไม่ว่าจะเลือกเส้นทางใด
เมื่อถึงจุดหนึ่ง จะต้องมีสะพาน สักแห่งที่ถูกข้ามซ้ำสองครั้ง
ออยเลอร์ได้ใช้บทพิสูจน์นี้ สร้างทฤษฎีทั่วไปขึ้นมา
ซึ่งประยุกต์ใช้กับกราฟที่มี ตั้งแต่สองโนดขึ้นไปทั้งหมด
เส้นทางออยเลอร์ ซึ่งเดินผ่าน แต่ละเอ็ดจ์เพียงครั้งเดียว
มีเพียงหนึ่งในสองกรณีต่อไปนี้ เท่านั้นที่เป็นไปได้
กรณีแรก คือ เมื่อมีโนดที่มีดีกรี จำนวนคี่อยู่สองโนดพอดี
หมายถึงโนดที่เหลือทั้งหมดมี ดีกรีจำนวนคู่
ในกรณีนี้ จุดเริ่มต้นคือ หนึ่งในสองโนดที่มีดีกรีจำนวนคี่
และจุดสิ้นสุดคือ อีกโนดที่มีดีกรีจำนวนคี่
กรณีที่สอง คือ เมื่อโนดทั้งหมด มีดีกรีเป็นจำนวนคู่
ในกรณีนี้ เส้นทางออยเลอร์จะ เริ่มต้นและสิ้นสุดในตำแหน่งเดียวกัน
ซึ่งทำให้มันกลายเป็นสิ่งที่เรียกว่า วงจรออยเลอร์
แล้วเราจะสร้างเส้นทางออยเลอร์ ในเคอนิกส์แบร์กได้อย่างไร
มันง่ายมาก
แค่เอาสะพานไหนก็ได้ออก ไปสักหนึ่งสะพาน
และปรากฏว่าประวัติศาสตร์ ได้สร้างเส้นทางออยเลอร์ของมันเอง
ในสงครามโลกครั้งที่ 2 กองทัพอากาศ โซเวียตทำลายสะพานเมืองไปสองแห่ง
ทำให้เส้นทางออยเลอร์ เป็นไปได้อย่างง่ายดาย
ซึ่งถ้าว่ากันตามจริงแล้ว นั่นอาจจะ ไม่ใช่ความตั้งใจของพวกเขาหรอก
การทิ้งระเบิดครั้งนั้นแทบจะกวาด เคอนิกส์แบร์กออกจากแผนที่ไปเลย
และได้สร้างใหม่ขึ้นในภายหลัง เป็นเมืองคาลินินกราดแห่งรัสเซีย
ดังนั้น แม้ว่าอาจไม่มีเคอนิกส์แบร์ก กับสะพานทั้งเจ็ดอีกต่อไปแล้ว
แต่จะเป็นที่จดจำไปชั่วประวัติศาสตร์ เพียงเพราะปริศนาหนึ่งที่ดูแสนธรรมดา
ซึ่งนำไปสู่การกำเนิด คณิตศาสตร์สาขาใหม่
Königsberg'i modern haritalarda bulmak için çok zorlanacaksın
fakat coğrafyasındaki bir acayiplik
onu, matematikte en ünlü şehirlerden biri yaptı.
Ortaçağ Alman şehri, Pregel Irmağı'nın iki tarafında yer alıyor.
Merkezde iki büyük ada vardı.
Bunlar birbirlerine ve ırmak kenarlarına
yedi köprü ile bağlıydılar.
Yakındaki bir kasabanın belediye başkanı olan matematikçi Carl Gottlieb Ehler,
bu adaları ve köprüleri saplantı haline getirmiş.
Dönüp dolaşıp şu soruya takılıyordu:
Hangi yol izlenilirse tüm yedi köprüden,
her birinden yalnızca bir defa geçecek şekilde geçilebilir?
Bir anlığına düşün.
7
6
5
4
3
2
1
Pes ettin mi?
Etmelisin.
Bu mümkün değil.
Ama bunun sebebini açıklamaya çalışmak, ünlü matematikçi Leonhard Euler'in
matematiğin yeni bir alanını bulmasına yol açtı.
Carl, Euler'den bu soru için yardım istedi.
Euler başta, matematik ile alakası olmadığı için soruyu pek kafasına takmadı.
Ama onunla daha çok uğraştıkça,
onun ardında bir şeyler olabileceği daha da belirdi.
Bulduğu cevap, o zamanlar henüz var olmayan
ve onun Konum Geometrisi dediği, günümüzde Çizge Kuramı diye bilinen
bir çeşit geometriyle ilgiliydi.
Euler'in ilk görüşü,
bir adaya veya ırmak kenarına girişle çıkış arasındaki yolun
aslında önemsiz olduğuydu.
Sonuç olarak harita, dört kara parçasının her biri bir nokta ile
gösterilmek üzere, ki bunlara düğüm diyoruz,
aralarındaki çizgeler
veya kenarlar köprüleri gösterecek şekilde sadeleştirilebilir.
Bu basitleştirilmiş graf, her düğümün derecesini kolayca saymamızı sağlıyor.
Bu, her toprak parçasının temas ettiği köprü sayısı.
Dereceler niçin önemli?
Oyunun kurallarına göre
bir kere gezginler bir köprüyle bir adaya girdiğinde
oradan ayrılmak için farklı bir köprü kullanmalılar.
Diğer bir deyişle, herhangi yol üzerindeki her düğüme gelen veya çıkan köprüler
farklı çiftler oluşturmalılar,
yani bir adaya değen köprülerin sayısı
çift olmalıdır.
Tek olası istisna, yürüyüşün başlangıç
ve bitiş noktaları olacaktır.
Grafa bakılınca dört düğümün hepsinin tek dereceli olduğu belirginleşiyor.
Yani hangi yolu seçerseniz seçin,
bir noktada, bir köprüden iki kere geçilmek zorunda.
Euler bu formülü, iki veya daha fazla düğüm içeren
tüm graflar için geçerli genel bir kuram kurmak için kullandı.
Her kenardan sadece bir kere geçen bir Euler yolu,
iki senaryodan birinde mümkündür.
İlki, tek dereceli tam olarak iki düğümün bulunmasıdır,
yani geri kalanlar çift.
Burada başlangıç noktası tek dereceli düğümlerden biri
ve bitiş noktası diğeridir.
İkincisi, tüm düğümlerin çift dereceli olmasıdır.
Bu durumda, Euler yolu aynı noktada başlayıp bitecektir.
Böylesi yola, bir Euler turu da denir.
O halde Königsberg'de bir Euler yolu nasıl oluşturulabilir?
Basit.
Köprülerden birini çıkarın.
Sonuçta, tarih kendi Euler yolunu yarattı.
II. Dünya Savaşı boyunca, Sovyet Hava Kuvvetleri iki köprüyü imha etti,
böylece bir Euler yolu mümkün oldu.
Aslında bu, isteyerek yapılmış bir şey değildi.
Bu bombalamalar Königsberg'i neredeyse haritadan sildi
ve daha sonra Rus Kaliningrad şehri olarak yeniden inşa edildi.
Königsberg ve yedi köprüsü şu an artık ortalıkta olmasa da
matematiğin tamamen yeni bir alanının doğuşuna yol açan
oldukça basit bir bilmeceyle tarih boyunca hatırlanacaktır.
Bạn sẽ thấy khó khăn khi tìm kiếm Königsberg trên bản đồ hiện đại,
nhưng có một điểm kỳ quặc về địa lý
đã làm nó trở thành một trong những thành phố nổi tiếng nhất trong Toán học.
Thành phố nước Đức thời Trung cổ này nằm hai bên bờ sông Pregel.
Ở trung tâm có hai hòn đảo lớn.
Hai hòn đảo được nối với nhau và với bờ sông
bởi bảy cây cầu.
Carl Gottlieb Ehler, một nhà Toán học mà sau này trở thành thị trưởng của thị trấn gần đó,
bị ám ảnh bởi những hòn đảo và cây cầu này.
Ông liên tục đặt ra chỉ một câu hỏi:
Lộ trình nào sẽ cho phép người ta băng qua cả bảy cây cầu
mà không đi qua cái nào trong số chúng quá một lần?
Hãy nghĩ về nó chỉ một lát thôi.
7
6
5
4
3
2
1
Bạn đã bỏ cuộc chưa?
Bỏ cuộc đi.
Điều đó là không thể.
Nhưng nỗ lực để giải thích câu hỏi tại sao đã dẫn nhà Toán học Leonhard Euler
phát minh ra lĩnh vực toán học mới.
Carl viết thư cho Euler nhờ giúp đỡ về vấn đề đó.
Euler ban đầu gạt bỏ câu hỏi đó vì nó chẳng liên quan gì tới Toán cả.
Nhưng ông càng vật lộn với nó,
dường như càng có một cái gì đó ẩn sau nó.
Câu trả lời mà ông nghĩ ra có liên quan đến một loại hình học
chưa được nghiên cứu đến, cái mà ông gọi là "Hình học vị trí",
ngày nay được biết đến với cái tên "Lí thuyết đồ thị".
Nhận thức đầu tiên của Euler đó là
lộ trình lần lượt đi vào và rời khỏi một hòn đảo hoặc một bờ sông
thì thật sự không quan trọng.
Vì vậy, bản đồ có thể được đơn giản hóa
với mỗi trong bốn vùng đất được đại diện bởi một điểm duy nhất,
cái mà chúng ta ngày nay gọi là "nút",
với các đường thằng, hoặc cạnh, giữa chúng là đại diện cho những cây cầu.
Và đồ thị giản lược này cho phép ta dễ dàng tính được "bậc" của mỗi nút.
Đó là số cây cầu mà mỗi vùng đất tiếp xúc.
Vậy tại sao bậc lại quan trọng?
Đó là vì, theo luật của thử thách,
một khi các hành khách đến được một vùng đất bởi một cây cầu,
họ sẽ phải rời khỏi đó bằng một cây cầu khác.
Nói cách khác, những cây cầu dẫn đến và dẫn từ mỗi nút trong bất cứ lộ trình nào
phải diễn ra theo từng cặp riêng biệt,
nghĩa là số cây cầu tiếp xúc với mỗi vùng đất đã được đến
phải là số chẵn.
Những ngoại lệ duy nhất đó là các vị trí của điểm xuất phát
và kết thúc của chuyến đi.
Nhìn vào đồ thị, nó trở nên rõ ràng rằng tất cả bốn nút đều có số bậc là số lẻ.
Vậy nên, bất kể lối đi nào được chọn,
ở cùng một điểm, một cây cầu sẽ được đi qua hai lần.
Euler sử dụng bằng chứng này để xây dựng một lý thuyết chung
mà áp dụng vào tất cả đồ thị với hai hoặc nhiều nút.
Đường đi Euler tiếp xúc mỗi cạnh chỉ một lần
chỉ có thể xảy ra một trong hai trường hợp.
Thứ nhất là khi có chính xác hai nút ở bậc lẻ,
nghĩa là tất cả số nút còn lại có bậc chẵn.
Khi đó, điểm bắt đầu là một trong số những nút lẻ,
và điểm kết thúc sẽ là nút lẻ còn lại.
Trường hợp thứ hai là khi tất cả các nút đều có bậc chẵn.
Khi đó, đường đi Euler sẽ xuất phát và dừng ở cùng một vị trí,
lúc này biến nó trở thành Chu trình Euler.
Vậy làm thế nào mà bạn có thể tạo ra đường đi Euler ở Königsberg?
Rất đơn giản.
Chỉ cần bỏ đi bất kì cây cầu nào.
Và hóa ra, lịch sử đã tạo ra một đường đi Euler cho riêng nó.
Trong suốt Thế chiến II, Lực lượng không quân Xô Viết đã phá hủy hai cây cầu,
làm cho đường đi Euler trở nên dễ dàng.
Mặc dù, công bằng mà nói, điều đó có lẽ không phải là mục đích của họ.
Những vụ đánh bom này gần như đã loại bỏ Königsberg khỏi bàn đồ,
và sau này được xây dựng lại thành thành phố Kaliningrad của Nga
Mặc dù Königsberg và bảy cây cầu của nó không còn tồn tại nữa,
nhưng chúng vẫn sẽ được nhớ đến xuyên suốt lịch sử bởi một câu đố có vẻ tầm thường
dẫn đến sự xuất hiện của cả một lĩnh vực Toán học hoàn toàn mới.
在现在的地图上，你很难找到哥尼斯堡这个城市
但是它在地理上奇特之处
使得它在数学上成为最为著名的城市之一。
这个中世纪的德国城市坐落于普雷格尔河的两岸。
河的中央有两座大的岛屿。
这两座岛屿通过七座桥
与河的两岸以及与彼此连接。
后来成为附近小镇市长的数学家卡尔·戈特利布·埃勒，
对这些桥和岛屿十分着迷。
他一直在考虑一个问题：
哪一条路径可以使人穿过所有这七座桥
并且同一座桥只能经过一次？
思考一下。
7
6
5
4
3
2
1
放弃了吗？
应该是的。
这是不可能的。
但是，大数学家莱昂哈德·欧拉 在试图解释这个数学问题时，
开拓了一个新的数学领域。
卡尔向欧拉写信求助。
开始，欧拉认为这个问题和数学 无关，所以不关心这个问题。
但是随着他对该问题的思考，
他越来越发现该问题有一定的意义。
他得出的答案与一类几何学相关
但当时并不存在，他称之为位置几何学，
就是现在著名的图论。
欧拉最初的想法
是进入岛屿或河岸和离开岛屿或河岸的路线
实际上并不重要。
这样，地图上便可以简化为四个岛
用四个简单的点表示，
我们现在称之为节点
它们之间的线或边代表桥。
这样，简化的图使我们比较容易计算每个节点的度，
即连接岛之间桥的数量。
为什么度很重要呢？
试想，根据这个问题的规定，
一旦有人想要通过一座桥到达一个岛屿，
他就必须通过另外的桥离开。
也就是说，在任何路线上，通往和离开每个节点的桥
必须是不同的桥，
这意味着连接每个岛的桥的数量
一定是偶数。
唯一可能的例外是在出发的位置
和离开的位置。
看下图，很明显所有四个节点的度都为奇数。
于是，无论选择什么样的路线，
在一些点上，一座桥势必会被经过两次。
欧拉用这个证明发展出了一个通用的理论，
适用于存在两个或两个以上节点的图。
每一个边仅经过一次的欧拉路径
只在两种情况下有可能。
第一，当仅有两个节点为奇数度时，
这意味着其它的都是偶数度。
这样，开始点就是奇数度的一个，
结束点是另外一个。
第二，当所有的节点都是偶数度时，
那么，欧拉路径就从同一个位置开始和结束，
这被称为欧拉回路。
于是，你怎么才能在格尼斯堡找到欧拉路径呢？
这很简单。
只要移走任一座桥。
事实说明，历史创造了欧拉路径。
二战期间，苏联空军摧毁了两个城市之间的一座桥，
这便创造出了欧拉路径。
虽然，公平来说，他们的目的不是这样。
这些炸弹从地图上抹掉了格尼斯堡，
并且这里被重建为之后的俄罗斯加里宁格勒市。
所以尽管格尼斯堡和她的七座桥不再存在，
但是它们会因这个导致全新数学 领域出现的谜团被历史记录下来。
你很難在任何現代地圖上 找到柯尼斯堡
它怪異的地理位置
使它成為數學界最知名的城市之一
這座中世紀的普魯士城 位於普列戈利亞河兩岸
河中間有兩座大島嶼
以七座橋互相連接
數學家卡爾·戈特利布·依拉 是附近小鎮的準鎮長
他從小痴迷於這些島和橋樑
他在同一個問題上反覆打轉
到底怎麼走才能跨越七座橋
卻不會重覆走過任何一座？
大家來想一想
7
6
5
4
3
2
1
要放棄嗎？
你一定很想
這怎麼可能？
但是數學名家萊昂哈德·歐拉 單純為了求證
發明了全新的數學領域
卡爾寫信請歐拉幫忙解答
歐拉起初認為 這個問題與數學無關
但當他愈投入，卻愈感其中的蹊蹺
他的答案與當時還不存在的
某種幾何學有關 歐拉命名為位置幾何學
現在稱為圖論
歐拉第一個見解是：
這跟出入島嶼之間的路線沒有關係
他把地圖簡化成四塊陸地
並標示成單點
也就是現在的「節點」
連接它們的「線」或「邊」代表橋
這種簡化的圖形 讓我們能輕易計算節點的分支
也就是是連接每塊陸地的橋樑數
為什麼分支很重要？
根據問題的規則
一旦行人由橋走上陸地
就必須從另一座橋離開
換句話說，在節點上來去的橋
都必須成對才行
意味著連接陸地的橋數
必須是偶數
唯一的例外可能是起點和終點
圖表上，四個節點都是奇數
所以不論選哪條路
還是會經過某一座橋兩次
歐拉用這個證據制定了一個
適用所有兩個以上節點的通論
只行經各邊一次的「一筆畫定理」
唯有兩種情況才有可能
第一種是有兩個奇數邊的節點
意味著其餘節點都有偶數邊
其中，起點是奇數節點
終點也是奇數節點
第二種，所有節點均有偶數邊
一筆畫路線的起點和終點 是同一個節點
稱為歐拉循環
所以要怎麼在柯尼斯堡 規劃一筆畫路線呢？
很簡單
只要拆掉任何一座橋即可
結果，歷史竟然 真的創造出一筆畫路線
二戰期間，蘇聯空軍摧毀了兩座橋樑
形成一筆畫路線
不過，這應該不是他們的本意
柯尼斯堡幾乎全毀，從地圖上消失
它隨後重建成俄羅斯的加里寧格勒
儘管柯尼斯堡與七橋已不復存在
它們仍因這微小的謎題 催生出全新的數學理論
永存於歷史之中