Having considered this problem, in 1736 Euler proved that this was impossible, and he considered a more general problem: which areas, separated by river branches and connected by bridges, can be walked around by visiting each bridge exactly once, and which are impossible.
Königsberg bridges">
Let's slightly modify the problem. We will denote each of the areas under consideration, separated by a river, by a point, 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. In modern mathematics, such figures 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 passed exactly once?
Such graphs, which can be drawn without lifting the pencil from the paper, are called unicursal (from the Latin unus cursus - one path), or Eulerian. So, the problem is posed this way: under what conditions is a graph unicursal? It is clear that a unicursal graph will not cease to be unicursal if the length or shape of its edges is changed, as well as the location of the vertices is changed - as long as the connection of the vertices by edges does not change (in the sense that if two vertices are connected, they should remain connected, and if they are separated – then disconnected).
If a graph is unicursal, then the topologically equivalent graph will also be unicursal. Unicursity is thus a topological property of a graph.
First, we need to distinguish connected graphs from disconnected ones. Connected figures are those such 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 along the points belonging to this letter. Connectedness is a topological property: it does not change when the figure is transformed without breaks or gluing. It is clear that if a graph is unicursal, then it must be connected.
Secondly, consider the vertices of the graph. We will call the index of a vertex the number of edges found at this vertex. Now let's ask ourselves: what can the indices of the vertices of a unicursal graph be equal to?
There can be two cases here: the line drawing the graph can begin and end at the same point (let’s call it a “closed path”), or maybe 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 a vertex is not the initial or final one, then, having arrived at it, you must then exit it - thus, as many edges enter it, the same number exit 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: the number of edges that came out of it, the same number that entered. And if the starting point does not coincide with the ending point, then their indices are odd: you need to exit the starting point once, and then, if we return to it, then exit again, if we return again, exit again, etc.; but we need to come to the final one, and if we then leave it, then we 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 be equal to two.
 |
Calculate 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 go around all the bridges...
The question arises: if a connected graph has no vertices with an odd index or exactly two such vertices, then is the graph necessarily unicursal? It can be strictly proven that yes! Thus, unicursity is uniquely related to the number of vertices with an odd index.
Exercise: build another bridge on the diagram of the Königsberg bridges - where you want - so that the resulting bridges can be walked around, having visited each exactly once; really go this route.
Now there's another one interesting fact: It turns out that any system of areas connected by bridges can be bypassed if you need to visit each bridge exactly twice! Try to prove it yourself.
| FORUM NEWS Knights of Aether Theory | 01.10.2019 - 05:20: -> - Karim_Khaidarov. 30.09.2019 - 12:51: |
The 7 bridges of the city of Kaliningrad (Koningsberg) led to the creation of the so-called graph theory by Leonhard Euler.
A graph is a certain number of nodes (vertices) that are connected by edges. Two islands and banks on the Pregel River, where he stood, were connected by 7 bridges. The famous philosopher and scientist I. Kant, walking along the bridges of Königsberg, came up with a problem that is known to everyone in the world as the “7 Königsberg bridges” problem: is it possible to walk across all these bridges and at the same time return to the starting point of the route so as to walk along each bridge only once?
Many have tried to solve this problem both practically and theoretically. But no one succeeded. Therefore, it is believed that in the 17th century, residents began a special tradition: when walking around the city, cross all the bridges only once. But, naturally, no one succeeded.
In 1736, this problem interested the scientist Leonhard Euler, who was an outstanding and famous mathematician and member of the St. Petersburg Academy of Sciences. He was able to find a rule thanks to which it was possible to solve this riddle. In the course of his judgments, Euler made the following conclusions: 1. the number of odd vertices (vertices to which an odd number of edges lead) of the graph must be even. There cannot be a graph that has an odd number of odd vertices. 2. 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. 3. A graph with more than 2 odd vertices cannot be drawn with one stroke.
This leads to the conclusion that it is impossible to cross all seven bridges without crossing one of them twice. Subsequently, this graph theory became the basis for the design of communication and transport systems and became widely used in programming, computer science, physics, chemistry and many other sciences and fields.
It is noteworthy that historians believe that there is a person who solved this problem, that he was able to cross all the bridges only once, although theoretically...
And it was like that. Kaiser (that is, Emperor) Wilhelm was famous for his simplicity of thinking, directness and “close-mindedness.” Once he almost became the victim of a joke that learned wits played on him - the jokers showed the Kaiser a map of the city of Königsberg and asked him to try to solve this famous problem, which, by definition, was unsolvable. But Kaiser only asked for a piece of paper and a pen, specifying that he would solve it in just 1.5 minutes. The scientists were amazed - Wilhelm wrote: “I order the construction of the eighth bridge on the island of Lomze.” That's all, the problem is solved... And so a new eighth bridge across the river appeared in Kaliningrad, named in honor of the Kaiser. Even a child can solve the problem with eight bridges...
Did you know that the seven bridges of the city of Koeningsberg (now this city is called Kaliningrad) became the “culprits” for the creation of graph theory by Leonhard Euler (a graph is a certain number of nodes (vertices) connected by edges). But how did this happen?
Two islands and banks on the Pregel River, on which Koeningsberg stood, were connected by 7 bridges. The famous philosopher and scientist Immanuel Kant, walking along the bridges of the city of Königsberg, posed a problem known to everyone in the world as the problem of the 7 Königsberg bridges: is it possible to walk across all these bridges and at the same time return to the starting point of the route so as to cross each bridge only 1 time. Many have tried to solve this problem both practically and theoretically. But no one succeeded, nor was it possible to prove that it was impossible even theoretically. Therefore, according to historical data, it is believed that in the 17th century, residents formed a special tradition: while walking around the city, cross all the bridges only once. But, as you know, no one succeeded.
In 1736, this problem interested the scientist Leonhard Euler, an outstanding and famous mathematician and 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 he could easily and simply get an answer to this question of interest to everyone. In the case of the city of Koeningsberg and its bridges, this turned out to be 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) of the graph 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 with one stroke 
If we consider this rule for the 7 bridges of Koeningsberg, then parts of the city in the figure (graph) are indicated by vertices, and bridges are indicated by edges connecting these vertices. The graph of the 7 Königsberg bridges had 4 odd vertices (that is, all of its vertices were odd), therefore, it is impossible to walk across all 7 bridges without passing through any of them twice.
It would seem that such an unusual discovery cannot have any real application or practical benefit. But a use was found, and some more. 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, 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 cross all the bridges only once, although theoretically, but there was a solution... And this is how it happened...
Kaiser (Emperor) Wilhelm was famous for his simplicity of thinking, directness and soldierly “narrow-mindedness.” One day, while at a social event, he almost became the victim of a joke that the learned minds present at the reception decided to play on him. They showed the Kaiser a map of the city of Königsberg and asked him to try to solve this famous problem, which, by definition, was simply unsolvable. To everyone’s surprise, the Kaiser asked for a piece 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 a pen, and wrote: “I order the construction of the eighth bridge on the island of Lomze.” And the whole problem is solved.....
This is how a new 8th bridge across the river appeared in the city of Königsberg, which was named the Kaiser Bridge. And now even a child can solve the problem with 8 bridges .
Unconventional solutions to the problem
Kaiser's "solution"
On the map of old Königsberg there was another bridge, which appeared a little later and connected the island of Lomse with the southern side. This bridge owes its appearance to the Euler-Kant problem itself. This happened under the following circumstances.
Emperor Wilhelm was known for his straightforwardness, simplicity of thinking and soldierly “narrow-mindedness.” One day, while at a social event, he almost became the victim of a joke that the learned minds present at the reception decided to play on him. They showed the Kaiser a map of Königsberg and asked him to try to solve this famous problem, which by definition was unsolvable. To everyone's surprise, the Kaiser asked for a pen and a piece of paper, saying that he would solve the problem in a minute and a half. The stunned German establishment could not believe their ears, but paper and ink were quickly found.
The Kaiser put the piece of paper on the table, took a pen and wrote the following: “I order the construction of the eighth bridge on the island of Lomze.” This is how it appeared in Königsberg new bridge, which was called the “Kaiser Bridge”. And now even a child could solve the problem with eight bridges.
see also
Literature
Wikimedia Foundation. 2010.
The city of Königsberg, which arose in the 13th century, formally consisted of three independent urban settlements, several settlements and towns. They were located on the banks and islands of the Pregel River, which divided the city into four main parts: Altstadt and Löbenicht, Kneiphof, Lomse, Fortstadt. For communication and trade between urban settlements, bridges began to be built in the 14th century.
Due to the constant military danger from Poland and Lithuania, a defensive or so-called bridge was built in front of each of the bridges. Lookout tower with locking overhead or bi-fold gates made of oak with wrought iron lining. And the bridges themselves acquired the character of defensive structures.
Bridges were the site of processions, religious and festive events and processions, and in the years of the so-called. “In the first Russian era” (1758 - 1762), when Koenigsberg became part of the Russian Empire during the Seven Years' War, Orthodox religious processions took place across the bridges. Once such a religious procession was dedicated to the Orthodox holiday of the Blessing of the Water of the River Pregel, which aroused the genuine interest of the indigenous residents of Koenigsberg.
By the beginning of the 20th century, all seven bridges were drawable, but due to the weakening and decline of navigation along the Pregel River, the three bridges that have survived to this day are no longer drawable.
Shop Bridge, Krämerbrücke
The oldest of the seven bridges in Königsberg is Lavochny Bridge(Krämerbrücke), which connected the city of Altstadt (Royal Castle) and the island of Kneiphof.
Built in 1286, in 1900 a new metal bridge was built on the site of the old wooden bridge. The name of the bridge indicates that it itself and the adjacent territory of the Pregolya River were a concentration of trade.
At the entrance to the bridge, a statue of Hans Zagan, the son of a Kneiphof shoemaker, was installed. According to legend, during the battle between the troops of the Teutonic Order and the Litvins near Rudau (Melnikovo village, Zelenograd region), Hans picked up the order banner from the hands of a wounded knight. The Nazis, who came to power in Germany in 1933, for ideological and moral reasons, demolished the monument to Zagan, because he was a Jew.
In 1972 it was demolished due to the construction of the Estakadny Bridge.
Lavochny Bridge. In the background are warehouses and the ship loading area - Lastadie
Lavochny bridge with port warehouses-barns Speicher (Speicher) on the right embankment of the Pregel River. Districts Laak and Hundegatt. On the left is Kneiphof Island
Green Bridge, GrüneBrücke
The second oldest bridge in Königsberg is Green Bridge. Built in 1322. The bridge burned down in 1582, was rebuilt by 1590 and existed in wooden form until 1907, when it was replaced by a metal bridge.
Connected the island of Kneiphof and the Fortstadt area through the old branch of the Pregolya river for travel from Royal Castle to the suburb of Ponart. The name of the bridge itself comes from the color of the paint that was used to paint the spans and supports of the bridge.
In the 17th century it was Green Bridge letters were heard arriving in Konigsberg. Waiting for mail Green Bridge The business people of the city gathered and, while waiting for correspondence, discussed their affairs. In 1623, exactly around Green Bridge The Koenigsberg Trade Exchange was built.
In 1972, the Green Bridge, like the Lavochny Bridge, fell victim to the Trestle Bridge.
Green Bridge. View from Kneiphof Island
View of the Green Bridge and the Mercantile Exchange
Giblet (Working) Bridge, Koettel brücke
In 1377, after the Lavochny and Green bridges, upstream of the old bed of the Pregel River, a Offal or Worker a bridge that also connected the island of Kneiphof and the Forstadt area.
Both translation options are not ideal, because... The German name of the bridge comes from Saxony and in the Russian version roughly means “auxiliary, working, intended for transporting garbage” bridge. Most likely, it owes its name to the nearby slaughterhouse.
In 1886, the wooden one was rebuilt into an iron one.
During the Second World War Giblet Bridge was destroyed and never rebuilt.
Giblet Bridge. View of the Mercantile Exchange from Kneiphof Island
Giblet Bridge. View from the Green Bridge
Forge Bridge, Schmitderbrüke
In 1397, in Königsberg, upstream of the new bed of the Pregel River, the Forge Bridge was erected, which, like the Lavochny Bridge, connected the city of Altstadt and the island of Kneiphof.
Blacksmiths were traditionally located near this bridge on the banks of the Pregel River.
By 1787, the bridge had become very worn and dilapidated and was replaced by a new bridge, but also wooden. In 1896, a new metal bridge was erected on the site of the old wooden bridge.
The Forge Bridge was destroyed during World War II and was never rebuilt.
Forge bridge with observation tower
Kuznechny Bridge
Wooden bridge, Holzbrücke
In 1404, a quadruple bridge was built between Altstat and the island of Lomze, which was called Wooden.
On the Wooden Bridge there was commemorative plaque with excerpts from the Prussian Chronicle. The ten-volume work of Albrecht Lukhel David itself told about ancient pagan Prussia and the history of the Teutonic Order until 1410.
In 1904, a new metal bridge was erected on the site of the old Wooden Bridge, but the name of the bridge remained the same. The Wooden Bridge has been preserved in this form to this day.
Wooden bridge. View of the island of Kneiphof
High Bridge, Hohebrücke
Built in Königsberg in 1520 to connect the island of Lomse and the Forstadt region.
It was reconstructed in 1882, its wooden parts were replaced with metal ones. In the same year, next to High Bridge A bridge house was erected in the Forstadt area. This beautiful, small building in the neo-Gothic style has survived to this day.
In 1937, the old one was dismantled and a new one made of metal with concrete supports was built nearby. From old High Bridge Concrete-brick supports have been preserved.
High Bridge. View of Lomse Island
High Bridge. View from the island of Lomse to the Forstadt district
Honey Bridge, Honigbrücke
The youngest of the seven bridges in Königsberg connected the island of Lomse and the island of Kneiphof.
There are several versions about the origin of the name Honey Bridge. According to one of them, Besenrode, a member of the Kneiphof Town Hall, paid for the construction of the bridge with barrels of honey, in another way, honey was used to pay for the construction of a trading post near the bridge. But these versions are probably just urban legends.
Most likely, the name of the bridge comes from the word “hon”, which means mockery (mockery). By building this bridge, the inhabitants of the island of Kneiphof received the shortest route to the island of Lomse, bypassing the High Bridge, which belonged to Altstadt. Thus, it became, as it were, a mockery of the main of the Königsberg cities - Altshadt. For this, the Altstadt people nicknamed the Kneiphofites - honey lickers.
in 1882, a new metal bridge was erected on the site of the old Honey Bridge.
Honey Bridge. View of the Kneiphof island and the Cathedral
Has survived to this day and is mainly used as pedestrian bridge, since currently only the Cathedral is located on Kneiphof Island - the main attraction of the city of Kaliningrad. Nowadays, newlyweds hang padlocks with their names and wedding date on the railings. Honey Bridge, and the keys to the locks are broken and thrown into the Pregel River.
The problem of the seven bridges of Königsberg, Leonhard Euler and graph theory
Since ancient times, the inhabitants of Königsberg have struggled with a riddle: is it possible to cross all the bridges, crossing each one only once? This problem was solved both theoretically, on paper, and in practice, on walks - passing along these very bridges. No one was able to prove that this was impossible, but no one could make such a “mysterious” walk across the bridges.
In 1736, the famous mathematician, member of the St. Petersburg Academy of Sciences, Leonhard 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 cross all the bridges without crossing any of them twice. This is impossible to do on the seven bridges of Königsberg.
On a city diagram (graph), the edges of the graph correspond to bridges, and the vertices of the graph (the points at which the lines connect) correspond to parts of the city. Reflecting on the problem, Euler came to the following conclusions:
graph vertices can be even or odd- with one stroke of the pen you can draw a graph, all of whose vertices are even, you can start at any vertex of the graph and end with the same vertex
- the number of odd vertices (those to which an odd number of edges lead) must be odd; a graph with an even number of odd vertices does not exist
- It is impossible to draw a graph with more than two odd vertices with one stroke.
The graph of Königsberg bridges has four odd vertices, that is, everything. Thus, it is not possible to cross all the bridges without passing one twice.
FORUM NEWS  Knights of Aether Theory | 02.23.2020 - 19:17: -> - Karim_Khaidarov. 23.02.2020 - 19:14: |
