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.
現代の地図でケーニヒスベルクを
見つけるのは不可能です
しかしこの街は 1つの特徴的な地形により
数学の分野で
最も有名な街の1つになったのです
この中世ドイツの街はプレーゲル川の
両側にまたがっており
その中心には2つの島がありました
2つの島と川岸はそれぞれ
7本の橋でつながっていました
数学者で後に近くの街の市長になった
カール・ゴットリーブ・エーラは
これらの島と橋に関する
1つの問題に取り付かれるようになりました
「どの経路なら 同じ橋を2度渡ることなく
7本全ての橋を渡れるのだろう?」
というものです
ちょっと考えてみてください
7
6
5
4
3
2
1
降参ですか?
当然です
不可能なのです
一方 その理由の説明を試みる過程で
有名な数学者レオンハルト・オイラーは
数学の新しい分野を生み出しました
カールは手紙を書き
オイラーに助けを求めました
オイラーは最初はこの問題は
数学に無関係として片付けました
しかしこの問題と格闘するほど
それ以上の何かがあるのではないかと
考えるようになりました
彼が出した答えは
それまで存在しなかった新しい幾何学の分野
彼自身は「位置の幾何学」と呼び
現在はグラフ理論というものに
関係していました
オイラーの最初の洞察は
どの経路で島や川岸を往来したかは
関係がないということでした
このように地図上の4つの土地は
現在我々が頂点と呼ぶ
1つの点として
橋は頂点の間の直線
もしくは辺として単純化できます
そしてこの簡素化されたグラフは
各頂点の次数
つまり各地点につながる橋の数を
数えやすくします
ではなぜ次数が重要なのでしょうか?
このクイズのルールでは
旅人がある橋を通って
1つの土地に到着したら
他の橋を通って
出て行かなければなりません
これはルート上にある全ての頂点で
到着と出発のための橋が
対になる必要があるということです
すなわち個々の土地につながる橋の数は
偶数でなければいけないということです
唯一例外が認められるのは
出発地点とゴール地点です
この図を見れば4箇所の頂点全てが
奇数の次数を持っていることは明らかです
したがってどのような道筋であっても
どこかの時点で橋は
2度渡らないといけないのです
オイラーはこの証明から
2つ以上の頂点を持つ全てのグラフに当てはまる
一般理論を作りました
全ての辺を1度だけ通るオイラー路には
2つのシナリオしかありません
最初のシナリオは
2つの頂点だけが奇数の次数を持ち
残りの頂点の次数が偶数のものです
この場合には奇数の次数を持つ
頂点の1つが出発地点となり
もう1つの頂点がゴール地点になります
2つ目のシナリオは全ての頂点が
偶数の次数を持つ場合です
この場合は出発地点とゴール地点は
同じ場所になり
オイラー閉路と呼ばれる回路を作ります
ではケーニヒスベルクで
オイラー路を作るにはどうしたらよいでしょうか
答えは簡単です
どれか橋を1本取り除けばいいのです
その後 歴史は自ら
オイラー路を作りました
第二次世界大戦の最中に
ソビエト空軍が街の2本の橋を破壊したため
オイラー路が簡単に作れるようになりました
公平を期して言えば ソビエトの目的は
オイラー路ではなかったでしょう
これらの爆撃によって
ケーニヒスベルクは正に地図から消し去られ
後日カリーニングラードという
ロシアの街として再建されました
だから7本の橋があるケーニヒスベルクの街は
もう存在しないかもしれませんが
他愛ないクイズから
数学の新しい分野を生み出した街として
歴史的に記憶されることでしょう
현대의 지도에서 쾨니스버그를
찾으려면 어려울 겁니다.
하지만 지리적으로 매우
특이한 곳이었기 때문에
이곳은 수학적으로 가장 유명한
도시 중 하나가 되었습니다.
중세 독일에 있던 이 도시는
프레겔 강의 양변에 놓여 있었어요.
그 중심에는 두 개의 큰 섬이 있었고
두 섬 사이와 두 섬과
강의 양쪽 둑 사이를
일곱 개의 다리가 연결하고 있었어요.
훗날 인근 마을의 시장인 된
칼 고트립 일러라는 수학자가
차츰 그 섬과 다리에 관해
고민하게 되었어요.
그는 단 한가지 문제에 계속 골몰했죠.
어떤 경로로 가면 일곱 개의
다리를 모두 건너면서도
각 다리를 단 한 번씩만 건너게 될까?
여러분도 잠시 생각해 보세요.
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
要放棄嗎?
你一定很想
這怎麼可能?
但是數學名家萊昂哈德·歐拉
單純為了求證
發明了全新的數學領域
卡爾寫信請歐拉幫忙解答
歐拉起初認為
這個問題與數學無關
但當他愈投入,卻愈感其中的蹊蹺
他的答案與當時還不存在的
某種幾何學有關
歐拉命名為位置幾何學
現在稱為圖論
歐拉第一個見解是:
這跟出入島嶼之間的路線沒有關係
他把地圖簡化成四塊陸地
並標示成單點
也就是現在的「節點」
連接它們的「線」或「邊」代表橋
這種簡化的圖形
讓我們能輕易計算節點的分支
也就是是連接每塊陸地的橋樑數
為什麼分支很重要?
根據問題的規則
一旦行人由橋走上陸地
就必須從另一座橋離開
換句話說,在節點上來去的橋
都必須成對才行
意味著連接陸地的橋數
必須是偶數
唯一的例外可能是起點和終點
圖表上,四個節點都是奇數
所以不論選哪條路
還是會經過某一座橋兩次
歐拉用這個證據制定了一個
適用所有兩個以上節點的通論
只行經各邊一次的「一筆畫定理」
唯有兩種情況才有可能
第一種是有兩個奇數邊的節點
意味著其餘節點都有偶數邊
其中,起點是奇數節點
終點也是奇數節點
第二種,所有節點均有偶數邊
一筆畫路線的起點和終點
是同一個節點
稱為歐拉循環
所以要怎麼在柯尼斯堡
規劃一筆畫路線呢?
很簡單
只要拆掉任何一座橋即可
結果,歷史竟然
真的創造出一筆畫路線
二戰期間,蘇聯空軍摧毀了兩座橋樑
形成一筆畫路線
不過,這應該不是他們的本意
柯尼斯堡幾乎全毀,從地圖上消失
它隨後重建成俄羅斯的加里寧格勒
儘管柯尼斯堡與七橋已不復存在
它們仍因這微小的謎題
催生出全新的數學理論
永存於歷史之中