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

번역: Elizabeth Kwon 검토: Jihyeon J. Kim

현대의 지도에서 쾨니스버그를 찾으려면 어려울 겁니다.

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.

수학적으로 완전히 새로운 분야 하나가 탄생했으니까요.