How the Königsberg bridge problem changed mathematics - Dan Van der Vieren

איך בעיית הגשרים של קניגסברג שינתה את פני המתמטיקה - דן ואן דר וירן

תרגום: Roni Ravia עריכה: Sigal Tifferet

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

7

6

6

5

5

4

4

3

3

2

2

1

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.

שהובילה לגילוי תחום חדש לגמרי במתמטיקה.