Koenigsberg - City of SEVEN BRIDGES (previously called so)
Old map of Koenigsberg. Letters indicate parts of the city: A - Altstadt, B - Kneiphof, C - Lomse, D - Vorstadt. The numbers indicate the bridges (in the order of construction): 1 - Shop, 2 - Green, 3 - Worker, 4 - Blacksmith, 5 - Wooden, 6 - High, 7 - Honey
shop bridge
The oldest of the seven bridges was the Shop Bridge (Krämerbrücke/Krämerbrücke), which connected the most important of the Königsberg cities, Altstadt, with the nearby Königsberg Castle and the city of Kneiphof lying on the island.
green bridge
The second oldest was the Green Bridge (Grüne Brücke / Grüne brücke).
working bridge
After Lavochnoye and Zeleny, the Worker Bridge (Kettel or Kittelbrücke) was built, which also connected Kneiphof and Vorstadt.
Blacksmith bridge
In 1397, the Blacksmith's Bridge (Schmiedebrücke/Schmiedebrücke) was built.
wooden bridge
Antique post from the fence of the Wooden Bridge. The coat of arms of Kneiphof is visible on the column - a hand raised from the water holding a crown. In the background is the Cathedral. Wooden bridge (Holzbrücke/Holzbrücke) between Altstadt and Lomse.
high bridge
Another Königsberg bridge that has survived to this day is the High Bridge (Hohe Brücke / Hoe-brücke).
honey bridge
The youngest of the seven bridges is the Honey Bridge (Honigbrücke/Honigbrücke), which connects the islands of Lomse and Kneiphof.
Did you know… that Euler derived his Grafov theory thinking about the seven bridges of Königsberg.
For a long time, such a riddle has been common among the inhabitants of Königsberg: how to pass through all the bridges without passing through any of them twice?
Many Königsbergers tried to solve this problem both theoretically and practically during walks. But no one has been able to do this, but no one has been able to prove that it is even theoretically impossible.
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 the bridges without passing over any of them twice (in the case of the seven bridges of Königsberg, this is impossible).
The father of graph theory (as well as topology) is Euler (1707-1782), who in 1736 solved a problem that was widely known at that time, called the Königsberg bridge problem. In the city of Koenigsberg there were two islands connected by seven bridges to the banks of the Pregol River and to each other as shown in Figure 4.
The task was the following: find a route for passing through all four parts of the land that would begin with any of them, end on the same part and pass exactly once over each bridge. It is easy, of course, to try to solve this problem empirically by enumeration of all routes, but all attempts will fail.
Figure 4- The problem of Königsberg bridges.
Euler's exceptional contribution to the solution of this problem is that he proved the impossibility of such a route.
To prove that the problem has no solution, Euler marked each part of the land with a point (top), and each bridge with a line (edge) connecting the corresponding points. Got a graph. The statement about the non-existence of a positive solution for this problem is equivalent to the statement about the impossibility of bypassing the given graph in a special way.
Figure 5 - Graph.
Graph elements. Ways to set a graph. Subgraphs.
Such a structure as a graph in quality (the term "network" is also used as a synonym) has a wide variety of applications in computer science.
CountGis called the systemV, U) ,
Where V={ v} - many elements called peaks graph;
U=={ u} - .a set of elements called ribs graph.
Each edge is defined either by a pair of vertices (v1,v2) or by two opposite pairs (v1,v2) and (v2,v1).
If an edge from U is represented by only one pair (v1,v2) , then it's called oriented edge leading from v1 to v2. In this case, v1 is called the beginning, and v2 is called the end of such an edge.
If an edge U is represented by two pairs (v1,v2) and (v2,v1), then U is called undirected edge. Any undirected edge between vertices v1 and v2 leads both from v1 Vv2, and vice versa. Moreover, the vertices v1 and v2 are both the beginnings and the ends of this edge. They say the rib leads like fromv1 inv2, so fromv2 inv1.
Any two vertices that are connected by an edge are adjacent.
By the number of elements, the graphs are divided into final And endless.
A graph all of whose edges are undirected is called unoriented count.
If the edges of a graph are defined by ordered pairs of vertices, then such a graph is called oriented.
R 
Figure 6 - Oriented graph.
Exist mixed graphs, consisting of both directed and undirected edges.
If two vertices are connected by two or more edges, then these edges are called parallel.
If the beginning and end of the edge coincide, then such an edge is called loop .
A graph without loops and parallel edges is called simple.
If an edge is defined by vertices v1 and v2, then edge is incident vertices v1 and v2.
A vertex that is not incident to any edge is called isolated.
A vertex incident to exactly one edge and that edge itself are called terminal, or hanging.
Edges that are associated with the same pair of vertices are called multiple or parallel.
Two vertices of an undirected graph v1 and v2 are called adjacent, if there is an edge (v1,v2) in the graph.
Two directed graph vertices v1 and v2 are called adjacent, if they are different and there is an edge from v1 to v2.
Consider some concepts for a directed graph.
Figure 7 - Directed graph.
Simple way: 
Elementary Path: 
Elementary contour: 
Circuit: 
For undirected graphs the concepts of "simple path", "elementary path", "contour", "elementary circuit" replace, respectively, the concepts of "chain", "simple chain", "cycle", "simple cycle". The count is called connected if for any two vertices there is a path (chain) connecting these vertices.
An undirected connected graph without cycles is called tree.
Undirected disconnected graph without cycles - forest.
Figure 8 - Connected graph.
Figure 9 - Forest.
Figure 10 - Tree.
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 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 "closed path"), or at different points (let's call it "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: |
When I was little (about 8 years old, probably), I went up to my father and asked: “Why is Kaliningrad called the city of seven bridges?” In response, he told me interesting story, laid everything out on the shelves. It was exciting and very educational. Naturally, I no longer remember this story in its original form, but I will try to tell it as excitingly as possible.
As you know, the city of Koenigsberg, founded in 1255, consisted of three independent urban settlements. They were located on the islands and banks of the Pregel River (now Pregol), which divides the city into four parts:
- Altstadt;
- Kneiphof;
- Lomze;
- Vorshtadt.
For communication between the city parts in the XIV century, bridges began to be built. Due to the constant military danger from neighboring Poland and Lithuania, the Königsberg bridges began to have a second function - defensive. 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. The piers of some bridges had a pentagonal shape typical of bastions. Inside these supports were casemates, from which it was possible to fire through the embrasures.
All seven bridges of Koenigsberg were drawbridges. In connection with the decline of navigation along the Pregol, the bridges were no longer raised. The only exception was the High Bridge, which is periodically drawn apart to prevent the mechanism and wiring of masted ships.
There was a tradition: a guest of the city, in order to subsequently return to Königsberg, had to throw a coin into Pregel from one of the bridges.
Here is an interesting fact for you associated with tradition: during the cleaning of the Pregolya channel by a dredger in the nineties of the XX century, numismatists literally fought for the right to stand with a sieve at the “gut”, from which bottom silt poured out.
And here is the second fact:"The problem of seven Königsberg bridges". The famous philosopher and scientist Immanuel Kant, walking along the bridges of the city of Koenigsberg, set the task: is it possible to pass through all these bridges and at the same time return to the starting point of the route so as to pass over 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.
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 Königsberg and its bridges, this turned out to be impossible. But he managed to create a theory of graphs (mathematicians will understand), which is still used today.
You can also try to solve this problem. Here is a diagram of the city's bridges:
Let's figure out what these seven bridges are.
Krämerbrücke (Shop Bridge).
Considered the oldest of the seven bridges. It was built in 1286 to connect the city of Altstadt and Kneiphof, and at its entrance was a statue of Hans Sagan, the son of a Kneipch shoemaker. The legend said: during the battle between the troops of the Teutonic Order and Lithuania, Hans picked up the falling order banner from the hands of a wounded knight.
The name of the bridge was due to the fact that the adjacent banks of the Pregel, and he himself were a place of trade.
In 1900 it was rebuilt, and in 1972 it was demolished due to the construction of the Trestle Bridge.
Grünebrücke (Green Bridge).
The Green Bridge was built in 1322 and connected Kneiphof and Vorstadt. It got its name from the color of the paint, in which the supports and the superstructure of the bridge were traditionally painted.
In the 17th century, at the Green Bridge, a messenger handed out letters that had arrived in Königsberg. In anticipation of correspondence, they gathered here business people cities, which, while waiting for the mail, discussed their daily business. According to legend, it was for this reason that the first building of the Königsberg Trade Exchange was built near the Green Bridge in 1623.
In 1875, a new trading exchange building was built on the other side of the bridge, which has survived to this day. Now this building is the Palace of Culture of Sailors.
In 1907, the bridge was rebuilt, and in 1972 it suffered the same fate as the Lavochny Bridge: they were replaced by the Trestle Bridge.
Köttelbrücke (Working Bridge).
The working bridge was built in 1337. Connected Kneiphof and Vorstadt. Sometimes its name is translated as "Offal", which is associated with a slaughterhouse located nearby. From where the giblets were transported by swimming along the Pregel through this bridge.
Initially, the bridge was a drawbridge and consisted of three spans. In 1621, it was washed away by a flood and was rebuilt without a lifting mechanism.
During the development of Vorstadt in 1886, the Worker Bridge was rebuilt in stone and metal. He was given back the divorce function.
The bridge burned down during the Great Patriotic War and was demolished along with the bull supports in the 70s of the twentieth century.
Schmiedebrücke (Blacksmith's bridge).
The blacksmith's bridge was built in 1397. Connected Altstadt and Kneiphof.
Blacksmiths were traditionally located near this bridge on the banks of the Pregel, apparently from this it got its name.
After the construction, the bridge took over part of the load from the parallel, slightly downstream, Lavochny Bridge. It was originally equipped with two stone pillars, covered with spans of boards, which were badly worn by 1787 and were replaced. In 1896, the Kuznechny Bridge survived the reconstruction and received decorative supports, steel spans and became a drawbridge. On the side of the Altstadt, a caretaker's tower was built, in which there was an installation for raising bridge spans using the water pressure of the city water supply, and the control of the adjustable mechanism was carried out.
It was destroyed during the Great Patriotic War and was not restored after the war.
Holzbrücke (Wooden bridge).
The wooden bridge was built in 1404 and connected Altstadt and Lomse.
On it was a memorial plaque with excerpts from the "Prussian Chronicle" by Albrecht Luhel David. This ten-volume work told about pagan Prussia and the history of the Teutonic Order.
The wooden bridge was reconstructed in 1904 and still exists in this form.
Hohebrücke (High Bridge).
The high bridge was built in 1520, connecting Lomse and Vorstadt. In 1882, it was rebuilt, adding to it the "Bridge Superintendent's House" (a room for distributing the mechanisms for drawing the bridge). This Neo-Gothic building still stands today.
The high bridge was demolished in 1938.
A few tens of meters from the preserved stone pillars of the old high bridge a new High Bridge was erected, which still stands today. It has a movable middle part for masted ships.
Honigbrücke (Honey Bridge).
The youngest of the seven bridges, connecting Lomse and Kneiphof. There are different versions about the origin of the name:
- Besenrode, a member of the Kneipch City Hall, paid for the construction of the bridge with barrels of honey.
- The same Bezenrode paid for the construction of a trading shop on the territory beyond the river with barrels of honey.
- The name comes from the word "Hon", which means - a mockery or mockery. By building this bridge, the inhabitants of Kneiphof gained direct access to the city of Lomse, bypassing the High Bridge, which belonged to Altstadt. Thus, the Honey Bridge became a mockery of the main of the Königsberg bridges.
Now it has a pedestrian character and leads to the island of Kant to the Cathedral and the sculpture park. Access for private vehicles is prohibited there.
Did you know that the seven bridges of the city of Koenigsberg (now this city is called Kaliningrad) became the "culprits" of Leonard 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 in such a way as 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 Königsberg 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 benefit. 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 a 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 .