You need to pass all 7 bridges. The history of the bridges of koenigsberg. Green Bridge, GrüneBrücke

Shop Bridge, Krämerbrücke

Green Bridge, GrüneBrücke

Offal (Working) bridge, Koettel brücke

Blacksmith's Bridge, Schmitderbrüke

High bridge, Hohebrücke

Honey Bridge, Honigbrücke

Since ancient times, the inhabitants of Koenigsberg have struggled with a riddle: is it possible to pass through all the bridges of Koenigsberg, passing through each only once? This problem was solved both theoretically, on paper, and in practice, on walks - passing along these same bridges. No one was able to prove that this was not feasible, but no one could make such a “mysterious” walk along the bridges.

In 1736, the famous mathematician, member of the St. Petersburg Academy of Sciences Leonard Euler undertook to solve the problem of seven bridges. In the same year, he wrote about this to the engineer and mathematician Marioni. Euler wrote that he had found a rule by which it is not difficult to calculate whether it is possible to pass over all bridges and at the same time not pass through any of them twice. It is impossible to do this on the seven bridges of Koenigsberg.

It was thanks to this bridge problem that another bridge appeared on the map of old Königsberg, with the help of which Lomse Island was connected to the south side. It happened in this way. Emperor (Kaiser) Wilhelm was known for his simplicity of thought, quick reaction and soldier's "narrowness". At one of the receptions, where the Kaiser was present, the invited scientists decided to play a joke with him: Wilhelm was shown a map of Königsberg, offering to solve the problem of bridges. The task was obviously unsolvable. Wilhelm, to everyone's surprise, demanded a pen and paper, declaring that the problem was solvable and that he would solve it in a matter of minutes. Paper and ink were found, although no one could believe that Kaiser Wilhelm had the solution to this problem. On the submitted piece of paper, the Kaiser wrote: "I order the construction of the eighth bridge on the island of Lomse." The new bridge was called the Imperial Bridge or Kaiser-brucke.

This eighth bridge made the bridge task easy fun even for a child....

Dear HR, HR...

There is a famous mathematician, a member of the academies, probably a professor or even academician Euler, and there is simply Kaiser Wilhelm. Euler decided that the problem could not be solved, while Wilhelm showed in an accessible way that this was not the case. Sometimes disputes with you remind me of the above textbook example.

Well, I don’t want this woman to work for me anymore.

Because she turned out to be a bad worker.

But we can't fire her...

And why is that?

So after all ... an article is such and such, a section, a paragraph, a paragraph ...

I need an employee, not articles!

Read labor law...

I'm reading. I call and fire myself. And I understand that most of you will remain at the level of "article such and such, section, paragraph, paragraph ..."

Municipal Autonomous educational institution

"Average comprehensive school No. 6 "Perm

History of mathematics

The old-old problem about the bridges of Koenigsberg

Completed by: Zheleznov Egor,

10 "a" class student

Head: Orlova E. V.,

mathematic teacher

2014, Perm

Introduction …………………………………………………………………………..3

The history of the bridges of Koenigsberg …………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

The problem of the seven bridges of Koenigsberg ………………………………………….......8

Drawing figures with one stroke ……………………………………….12

Conclusion ………………………………………………………………………… 15

References ...…………………………………………………………….16

Annex 1 …………………………………………………………………………………………………………18

Annex 2 ………………………………………………………………………22

Annex 3 ………………………………………………………………………23

Annex 4 ………………………………………………………………………26

Doing

Koenigsberg is the historical name of Kaliningrad, the center of the westernmost region of Russia, famous for its mild climate, beaches and amber products. Kaliningrad has a rich cultural heritage. Here they once lived and worked great philosopher I. Kant, storyteller Ernst Theodor Amadeus Hoffmann, physicist Franz Neumann and many others whose names are inscribed in the history of science and creativity. An interesting problem is related to Koenigsberg, the so-called problem of the bridges of Koenigsberg.

The purpose of our study: study the history of the emergence of the Königberg bridge problem, consider its solution, and clarify the role of the problem in the development of mathematics.

To achieve the goal, it is necessary to solve the following tasks:

study the literature on the topic;

organize the material;

select tasks in the solution of which the method of solving the problem of Kentgsberg bridges is used;

make a bibliographic list of references.

History of the bridges of Koenigsberg

Arising in city of Königsberg (now) consisted of three formally independent urban settlements and several more “settlements” and “villages”. They were located on the islands and the banks of the river.(now Pregol), dividing the city into four main parts:, , And . For communication between city parts already in began to build . Due to the constant military danger from neighboring And , and also due to civil strife between the Königsberg cities (in- there was even a war between the cities, caused by the fact that Kneiphof went over to the side of Poland, while Altstadt and Löbenicht remained loyal) in Königsberg bridges had defensive qualities. In front of each of the bridges, a defensive tower was built with lockable lifting or double-leaf gates made of oak and with iron forged upholstery. And the bridges themselves acquired the character of defensive structures. The piers of some bridges had a pentagonal shape typical of bastions. Casemates were located inside these supports. From the supports it was possible to fire through the embrasures.

Bridges were a place of processions, religious and festive processions, and during the years of the so-called "First Russian Time" (-), when Königsberg briefly became part of the Seven Years' War, religious processions passed along the bridges. Once such a procession was even dedicated to the Orthodox feast of the Blessing of the Waters of the Pregel River, which aroused genuine interest among the inhabitants of Königsberg.

By the end of the 19th century, 7 main bridges were built in Königsberg (Appendix 1).

The oldest of the seven bridges Lavochnybridge(Krämerbrücke / Kramer-brücke). It was built in 1286. The very name of the bridge speaks for itself. The square adjacent to it was a place of lively trade. It connected the two medieval cities of Altstadt and Kneiphof. It was built immediately in stone. In 1900 it was rebuilt and made movable. Trams began to run across the bridge. During the war, it was badly damaged, but restored until it was dismantled in 1972.

Was the second oldestGreen bridge (Grüne Brücke / Grüne brücke). It was built in. This bridge connected the island of Kneiphof with the southern bank of the Pregel. It was also stone and three-span. In 1907, the bridge was rebuilt, the middle span became drawable and trams began to run along it. During the war, this bridge was badly damaged, was restored, and in 1972 it was dismantled.The name of the bridge comes from the color of the paint, which was traditionally used to paint the supports and the superstructure of the bridge. INat the Green Bridge, a messenger handed out letters that had arrived in Königsberg. Business people of the city gathered here in anticipation of correspondence. Here, while waiting for the mail, they discussed their affairs. It is not surprising that it is in the immediate vicinity of the Green Bridge inKönigsberg trading house was built. IN on the other side of the Pregel, but also in the immediate vicinity of the Green Bridge, a new building of the trading exchange was built, which has survived to this day (now the Palace of Culture of Sailors).In 1972, instead of the Green and Lavochny bridges, the Trestle Bridge was built.

After Lavochnoye and Green was builtworking bridge (Koettelbrucke / Kettel or Kittelbrücke), also connecting Kneiphof and Vorstadt. Sometimes the name is also translated as Gut Bridge. Both translations are not ideal, since the German name comes fromand in Russian means approximately “working, auxiliary, intended for garbage transportation”, etc. This bridge was built in . It connected the city of Kneiphof with the suburb of Vorstadt. The bridge was half stone, and the spans were wooden decks. In 1621, during a severe flood, the bridge was torn off and swept into the river. The bridge was returned to its place. In 1886 it was replaced with a new, steel, three-span, movable one. Trams also ran along it. The bridge was destroyed duringand did not recover later.

Seven bridges of Koenigsberg - Wikipedia (ru /wikipedia .ord)

Graph theory – site www .ref .by /refs

Attachment 1

shop bridge

green bridge

Gut bridge

Blacksmith bridge

wooden bridge

high bridge

Honey Bridge. Side view of

former drawbridge.

Honey bridge. Remains of the draw mechanism.

Kaiser Bridge

Appendix 2

Leonhard Euler

H German and Russian mathematician, mechanic and physicist. Born April 15, 1707 in Basel. He studied at the University of Basel (in 1720-1724), where his teacher was Johann Bernoulli. In 1722 he received a master's degree in arts. In 1727 he moved to St. Petersburg, taking a position as an adjunct professor at the newly founded Academy of Sciences and Arts. In 1730 he became a professor of physics, in 1733 - a professor of mathematics. During the 14 years of his first stay in St. Petersburg, Euler published more than 50 papers. In 1741–1766 worked at the Berlin Academy of Sciences under the special patronage of Frederick II and wrote many works covering essentially all branches of pure and applied mathematics. In 1766, at the invitation of Catherine II, Euler returned to Russia. Shortly after arriving in St. Petersburg, he completely lost his sight due to cataracts, but thanks to his excellent memory and the ability to perform calculations in his mind, he spent the rest of his life scientific research: during this time he published about 400 works, their total number exceeds 850. Euler died in St. Petersburg on September 18, 1783.

Euler's works testify to the extraordinary versatility of the author. His treatise on celestial mechanics, The Theory of the Motion of Planets and Comets, is widely known. Author of books on hydraulics, shipbuilding, artillery. Euler is best known for his research in pure mathematics.

Annex 3

Tasks

W
task 1(problem about the bridges of Leningrad). In one of the halls of the House of Entertaining Science in St. Petersburg, visitors showed a diagram of the city's bridges (Fig.). It was necessary to bypass all 17 bridges connecting the islands and the banks of the Neva, on which St. Petersburg is located. It is necessary to go around so that each bridge is passed once.

And cutting the quarters

Emerge suddenly from the darkness

St. Petersburg channels,

St. Petersburg bridges!

(N. Agnivtsev)

D prove that the required unicursal bypass of all the bridges of St. Petersburg at that time is possible, but cannot be closed, i.e., endin point from which it started.

Task 2. There are seven islands on the lake, which are interconnected as shown in the figure. Which island should the boat take travelers to so that they can cross each bridge and only once? Why can't travelers be taken to island A? 17

W hell 3. (in search of treasure) .

On fig. the plan of the dungeon is depicted, in one of the rooms of which the treasures of the knight are hidden. To safely enter this room, you must enter through certain gates into one of the extreme rooms of the dungeon, go through all 29 doors in sequence, turning off the alarm. You can't go through the same doors twice. Determine the number of the room in which treasures are hidden and the gate through which you need to enter? twenty

hell 4. Pavlik - an avid cyclist - depicted on chalkboard part of the plan of the area and the village (fig. 8), where he lived last summer. According to Pavlik, not far from the village, located on the banks of the Oya River, there is a small deep lake fed by underground springs. Oya originates from it, which, at the entrance, the village is divided into two separate streams, connected by a natural channel so that a green island is formed.wok(in the figure marked with the letterBUT) with beach and playground. Dalekaboutbehind the village, both streams, merging, form a wide river. Pavlik claims that, returning on a bicycle from a sportssite located on the island, home (in the figure, the letterD ), he passes once over all eight bridges shown on the plan, never once interrupting the movement. Our connoisseurs of the theory of such puzzles marked with lettersA, B, C, D sections of the village, separated by a river (sections are network nodes, bridges are branches), and found that a unicursal route starting atBUT (odd node), it is possible, but it must certainly end in B - in the second odd node, the remaining two nodesFROM AndD - even. But Pavlik, too, is telling the truth: his route fromBUT inD really ran along all eight bridges and was unicursal. What is the matter here? What do you think?

W hell 5 . English mathematician L. Carroll (author of the world famous books"Alice in Wonderland", "Alice Through the Looking Glass", etc.) liked to ask his little friends a puzzle to bypass the figure (Fig. 9)with a single stroke of the pen and without passing twice a single section of the contour. Lines were allowed to cross. Such a task is easily solved.

Let's complicate it with an additional requirement: at each transition through a node (considering the points of intersection of the lines in the figure as nodes), the direction of the bypass must change by 90°. (Starting from any node, you will have to make 23 turns) 6 .

Task 6 . (A fly in a jar) A fly has climbed into a sugar jar. The jar is in the shape of a cube. Will the fly be able to sequentially go around all 12 edges of the cube without passing twice along one edge. Jumping and flying from place to place is not allowed. 22

W hell 7 . The picture shows a bird. Is it possible to draw it with one stroke?

W hell 8 . On theFigure 10 shows a sketch of one of Euler's portraits. The artist reproduced it with one stroke of the pen (only the hair is drawn separately). Where in the figure are the beginning and end of the unicursal contour located? Repeat the movement of the artist's pen (hair and dotted lines in the figure are not includedinbypass route) 6 .

Fig.10

hell 9. Draw the following figures in one stroke. (Such figures are called unicursal (from the Latin unus - one, cursus - path)).

Appendix 4

Problem solving

1

.

3 . To solve it, you need to build a graph where the vertices are the numbers of the rooms, and the edges are the doors.

Odd Vertices: 6, 18. Since the number of odd vertices = 2, it is safe to enter the treasure room.

You need to start the path through the gate IN and finish in room no. 18 .

5. An example of the required bypass is given in the figure.

6 . The edges and vertices of the cube form a graph, all 8 vertices of which have multiplicity 3 and, therefore, the bypass required by the condition is impossible.

7. Taking the intersection points of the line as graph vertices, we get 7 vertices, only two of which have an odd degree. Therefore, there is an Euler path in this graph, which means that it (that is, the bird) can be drawn with one stroke. You need to start the path at one odd vertex, and end at another.

8. You need to start bypassing at the odd node in the corner of the right eye and end at the odd node of the eyebrow above the left eye (dotted lines are not included in the network). All other nodes in the figure are even.

9 .

Having considered this problem, in 1736 Euler proved that this is impossible, and he considered more common task: which areas, separated by river branches and connected by bridges, can be bypassed by visiting each bridge exactly once, and which ones are impossible.

Königsberg bridges">

Let's modify the problem a bit. Each of the areas under consideration, separated by a river, will be denoted by a dot, and the bridges connecting them by a line segment (not necessarily a straight line). Then, instead of a plan, we will simply work with a certain figure made up of segments of curves and straight lines. Such figures in modern mathematics are called graphs, segments are called edges, and the points that connect the edges are called vertices. Then the original problem is equivalent to the following: is it possible to draw a given graph without lifting the pencil from the paper, that is, in such a way that each of its edges is traversed exactly once.

Such graphs, which can be drawn without lifting the pencil from the paper, are called unicursal (from the Latin unus cursus - one way), or Euler. So, the problem is posed in this way: under what conditions is a graph unicursal? It is clear that a unicursal graph will not cease to be unicursal if we change the length or shape of its edges, as well as change the arrangement of vertices, so long as the connection of vertices by edges does not change (in the sense that if two vertices are connected, they must remain connected, and if they are disconnected - then disconnected).

If a graph is unicursal, then the topologically equivalent graph is also unicursal. Unicursality is thus a topological property of a graph.

First, we need to distinguish connected graphs from disconnected ones. Connected figures are such figures that any two points can be connected by some path belonging to this figure. For example, most of the letters of the Russian alphabet are connected, but the letter Y is not: it is impossible to move from its left half to the right by points belonging to this letter. Connectivity is a topological property: it does not change when the figure is transformed without breaks and gluing. It is clear that if a graph is unicursal, then it must be connected.

Second, consider the vertices of the graph. We will call the index of a vertex the number of edges that occur in this vertex. Now let's ask ourselves the question: what can be the indices of the vertices of a unicursal graph.

There can be two cases here: the line drawing the graph can start and end at the same point (let's call it a "closed path"), or at different points (let's call it an "open path"). Try to draw such lines yourself - with whatever self-intersections you want - double, triple, etc. (for clarity, it is better that there are no more than 15 edges).

It is easy to see that in a closed path, all vertices have an even index, and in an open path, exactly two have an odd index (this is the beginning and end of the path). The fact is that if the vertex is not the initial or final one, then, having arrived at it, you must then leave it - thus, how many edges enter it, the same number leave it, and the total number of incoming and outgoing edges will be even . If the initial vertex coincides with the final vertex, then its index is also even: how many edges left it, the same number entered. And if the starting point does not coincide with the end point, then their indices are odd: you need to leave the starting point once, and then, if we return to it, then exit again, if we return again, exit again, etc.; but you need to come to the final one, and if we leave it later, then you need to return again, etc.

So, for a graph to be unicursal, it is necessary that all its vertices have an even index, or that the number of vertices with an odd index is equal to two.

Count the indices of its vertices and make sure that it cannot possibly be unicursal. That's why you didn't succeed when you wanted to bypass all the bridges...

The question arises: if there are no vertices with an odd index in a connected graph, or there are exactly two such vertices, then is the graph necessarily unicursal? It can be rigorously proven that yes! Thus, unicursality is uniquely related to the number of vertices with an odd index.

Exercise: build another bridge on the diagram of the Konigsberg bridges - wherever you want - so that the resulting bridges can be bypassed, having visited each exactly once; really do it this way.

Now another one interesting fact: it turns out that any system of areas connected by bridges can be bypassed if it is necessary to visit each bridge exactly twice! Try to prove it yourself.

FORUM NEWS
Aether Theory Knights

01.10.2019 - 05:20: -> - Karim_Khaidarov.
30.09.2019 - 12:51:

Fundamentals of graph theory as mathematical science founded in 1736 by Leonhard Euler, considering the problem of the Königsberg bridges. Today, this task has become a classic.

Former Koenigsberg (now Kaliningrad) is located on the Pregel River. Within the city, the river washes two islands. Bridges were thrown from the coast to the islands. The old bridges have not been preserved, but there is a map of the city where they are depicted. The Koenigsbergers offered visitors the following task: to cross all the bridges and return to the starting point, and each bridge should have been visited only once.

The problem of the seven bridges of Königsberg

The Problem of the Seven Bridges of Königsberg or the Problem of the Königsberg Bridges (German: Königsberger Brückenproblem) - old mathematical problem, which asked how it is possible to pass through all seven bridges of Königsberg without passing through any of them twice. It was first solved in 1736 by the German and Russian mathematician Leonhard Euler.

For a long time, such a riddle has been common among the inhabitants of Königsberg: how to pass through all the bridges (across the Pregolya River) without passing through any of them twice. Many Königsbergers tried to solve this problem both theoretically and practically during walks. However, no one could prove or disprove the possibility of the existence of such a route.

In 1736, the problem of seven bridges interested the outstanding mathematician, member of the St. Petersburg Academy of Sciences, Leonhard Euler, about which he wrote in a letter dated March 13, 1736, to the Italian mathematician and engineer Marioni. In this letter, Euler writes that he was able to find a rule by which it is easy to determine whether it is possible to pass over all bridges without passing over any of them twice. The answer was "no".

Solution of the problem according to Leonhard Euler

On a simplified diagram, parts of the city (graph) correspond to bridges with lines (arcs of the graph), and parts of the city correspond to points of connection of lines (vertices of the graph). In the course of reasoning, Euler came to the following conclusions:

The number of odd vertices (vertices to which an odd number of edges lead) must be even. There cannot be a graph that has an odd number of odd vertices.
If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex.
A graph with more than two odd vertices cannot be drawn with a single stroke.
The graph of Königsberg bridges had four (in blue) odd vertices (i.e. all), therefore it is impossible to pass through all the bridges without passing through any of them twice

The graph theory created by Euler has found very wide application in transport and communication systems (for example, for studying the systems themselves, compiling optimal routes for delivering goods or routing data on the Internet).

Further history of the Königsberg bridges

In 1905, the Imperial Bridge was built, which was subsequently destroyed during the bombing during the Second World War. There is a legend that this bridge was built by order of the Kaiser himself, who could not solve the problem of Königsberg bridges and became a victim of a joke played with him by the learned minds who were present at the secular reception (if you add the eighth bridge, then the problem becomes solvable). The Jubilee Bridge was built on the pillars of the Imperial Bridge in 2005. On the this moment there are seven bridges in Kaliningrad, and the graph built on the basis of the islands and bridges of Kaliningrad still does not have an Euler path.

Did you know that the seven bridges of the city of Koenigsberg (now this city is called Kaliningrad) became the "culprits" of Leonhard Euler's creation of the theory of graphs (A graph is a certain number of nodes (vertices) connected by edges). But how did it happen?

Two islands and banks on the Pregel River, on which Koenigsberg stood, were connected by 7 bridges. The famous philosopher and scientist Immanuel Kant, walking along the bridges of the city of Koenigsberg, set a problem known to everyone in the world as the problem of 7 Koenigsberg bridges: is it possible to pass through all these bridges and at the same time return to the starting point of the route so that to pass through each bridge only 1 time. Many have tried to solve this problem both practically and theoretically. But no one has been able to do this, and no one has been able to prove that it is impossible even theoretically. Therefore, according to historical data, it is believed that in the 17th century, the inhabitants formed a special tradition: walking around the city, go through all the bridges only 1 time. But, as you know, no one succeeded.

In 1736, this problem interested the scientist Leonhard Euler, an outstanding and famous mathematician and a member of the St. Petersburg Academy of Sciences. He wrote about this in a letter to his friend, the scientist, Italian engineer and mathematician Marioni dated March 13, 1736. He found a rule using which it was easy and simple to get an answer to this question of interest to everyone. In the case of the city of Koningsberg and its bridges, this proved impossible.

In the process of his reasoning, Euler came to the following theoretical conclusions:

The number of odd vertices (vertices to which an odd number of edges lead) must be even. There cannot be a graph that has an odd number of odd vertices.

If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex.

A graph with more than 2 odd vertices cannot be drawn in one stroke

If we consider this rule for the 7 bridges of Koenigsberg, then the parts of the city in the figure (graph) are indicated by vertices, and the bridges are indicated by edges connecting these vertices. The graph of 7 Konigsberg bridges had 4 odd vertices (that is, all of its vertices were odd), therefore, it is impossible to pass through all 7 bridges without passing through any of them twice.

It would seem that such an unusual discovery cannot have any real application and practical benefits. But there was an application, and what else. Graph theory, created by Leonhard Euler, formed the basis for the design of communication and transport systems, it is used in programming and computer science, in physics, chemistry and many other sciences and fields.

But the most interesting thing is that historians believe that there is a person who solved this problem, he was able to pass through all the bridges only once, though theoretically, but the solution was .... And this is how it happened...

Kaiser (Emperor) Wilhelm was famous for his simplicity of thinking, directness and soldier's "narrowness". Once, being at a social event, he almost became the victim of a joke that the learned minds present at this reception decided to play with him. They showed the Kaiser a map of the city of Koenigsberg, and asked him to try to solve this famous problem, which, by definition, was simply not solvable. To everyone's surprise, Kaiser asked for a sheet of paper and a pen, and at the same time specified that he would solve this problem in just a minute and a half. The stunned scientists could not believe their ears, but ink and paper were quickly found for him. The Kaiser put the piece of paper on the table, took up a pen, and wrote: "I order the construction of the eighth bridge on the island of Lomse." And the problem is solved....

So in the city of Königsberg, a new 8th bridge across the river appeared, which was called the Kaiser Bridge. And now even a child can solve the problem with 8 bridges .