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 (vertex), and each bridge with a line (edge) connecting the corresponding points. Got a graph. The statement about the nonexistence 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.
Shop Bridge, Krämerbrücke
Green Bridge, GrüneBrücke
Offal (Working) bridge, Koettel brücke
Blacksmith's Bridge, Schmitderbrüke
Wooden bridge, Holzbrücke
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: they showed Wilhelm 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, but 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 ..."
The foundations of graph theory as a mathematical science were laid in 1736 by Leonhard Euler, considering the problem of 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 Königsberg Bridges (German: Königsberger Brückenproblem) is an old mathematical problem that 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 to the Italian mathematician and engineer Marioni dated March 13, 1736. 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".
Solving 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 the 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. At the 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.
For more than 10 years, the newspaper “Novye KOLESA Igor RUDNIKOV” under the heading “Walks around Koenigsberg” has been publishing articles on the history of our city. Out of more than 500 essays-walks for the book, we chose 34 - sad and funny, tragic and epic. The chapters contain sketches of the customs and life of the Königsbergers, based on historical facts, legends and legends: fashion and architecture, police, military and firefighters, restaurants and cafes, universities and schools, the historical connection of Königsberg with Russia and much more ... Photos of Königsberg and illustrations by the artist S. Fedorov, made especially for this book, will give us the opportunity to present this city-“Atlantis”.
Seven bridges of Königsberg
Euler's problem was solved by the war and the Soviet government
It is known that the great Swiss mathematician Leonhard Euler created a whole branch of science by solving the problem of seven Königsberg bridges.
In vain trample shoes
There is a legend that the inhabitants of Koenigsberg loved to walk along the streets of three medieval cities “merged” into a single whole: Altstadt, Löbenicht and Kneiphof, but they could not stand trampling their shoes in vain. These cities were connected by seven bridges. And now, as if economical city dwellers once thought: is it possible to go through all the bridges so that you visit each of them only once and return to the place where you started the walk?
Euler was interested in the problem. “No one has yet been able to do this, but no one has proven that it is impossible ... Neither geometry, nor algebra, nor combinatorial art is sufficient for the solution,” he wrote to his colleague, an Italian mathematician and engineer.
In the end, having built the most complicated algorithm, Euler received a negative answer. It turned out to be impossible to cross all the bridges only once and, having described the circle, return to the starting point.
Shop, Green and Blacksmith
So, the Lavochny Bridge (Kremerbrücke) was the oldest. It was built in 1286 on the initiative of the mayor of Altstadt (who had just received city rights). He connected Altstadt with the island of Kneiphof, which did not yet have an urban settlement.
A booth was built next to the Shop Bridge - as it is written in German papers, "for storing possible rubbish." In 1339, the bridge is mentioned as named after St. George, but in 1397 it acquires a new name: Kogenbrücke, that is, the Bridge of Ships (merchant ships were then called Kogami in the Hansa). In 1548, this name became official, changing to one letter: Kokenbrücke.
In 1787 the bridge was reconstructed. The "junk box" was removed. In 1900, a new one, made of metal, was built in place of the wooden Kokenbrücke. He safely survived the war and was demolished in 1972 during the construction of the Estakadny Bridge.
Shop bridge and old port warehouses
Gut bridge
Next - Green (Gruenebrücke). It was built in 1322 across a branch of the Pregel River in order to provide traffic from the suburbs of Ponart to the Royal Castle. Burned down in 1582. Six years later it was rebuilt, again from wood. It existed in this form until 1907, then it was replaced with a metal one, it was adjustable. The mechanism was set in motion manually. Survived the war. “Sentenced” to him in the same 1972, during the construction of the Overpass.
In 1379, on the initiative of the Altstadters and by the decision of the master of the Teutonic Order Winrich, a bridge was built parallel to Lavochny. It was named Blacksmith (Schmidebrücke). He also had a booth "for trash."
By 1787, the Blacksmith's Bridge was dilapidated and was replaced with a new one, also made of wood. It was built in metal in 1846. Instead of a booth, they put a turret for a steam installation - an adjustable mechanism.
During the assault on Königsberg, it was destroyed and never rebuilt.
Offal, Tall and Wooden
The Offal (Meat) Bridge (Kettelbrücke) ran parallel to the Green Bridge, located near the slaughterhouse, in front of the Stock Exchange building (now the Sailors' Palace of Culture). It was built in 1377 at the expense of the inhabitants of Kneiphof to connect them with Vorstadt - the warehouse area. There, in Vorstadt, stocks of wood for heating were initially stored.
Partially, the Gut Bridge was destroyed even before the storming of the city in April 1945, and its spans were used to repair the Wooden Bridge (Halzbrücke). Wooden intact to this day, it connects the former Altstadt with Oktyabrsky Island (former Lomse Island). If you look closely, you can see that the forging of the railing is different: in some places its elements are oak leaves, in others, borrowed from Potrokhovy, there are rings.
In 1377, permission was obtained for the construction of the High (Hoebrücke) bridge (connecting Oktyabrsky Island with the current Dzerzhinsky Street). At the end of the 19th century, its wooden version was replaced by a brick and metal structure. By the way, next to this bridge is the only surviving building of lifting mechanisms in the whole city - a turret called the Bridge House. (She was about to fall into the Pregel, but a few years ago she was restored.)
In 1937, a new metal and concrete bridge was built just to the east. It is he who exists to this day. True, since then it has not been modernized, although, according to the plan, all the bridges of Königsberg were to undergo ongoing reconstruction.
Or maybe it's for the best? Eyewitnesses recall how in 1996, sappers - ours, from Kaliningrad - blew up the concrete coating with heavy bombs while repairing the Trestle Bridge! Moreover, structures of this kind are very sensitive not even to a shock wave, but simply to a synchronous oscillation. After all, there is a case when a rather strong bridge collapsed from the fact that a company of soldiers walked along it in the foot ...
Imperial and Honey
The Honey Bridge (Honigbrücke), built in 1542, has also been preserved. According to legend, it owes its “delicious” name to ... a bribe that Ober-Burgrave Basenrade allegedly received from the Kneiphof City Council. For permission to build a bridge linking Kneiphof with the island of Lomse, bypassing the Altstadt. It was as if the Kneiphofers had delivered a whole barrel of honey to Bazenrad, and the angry Altstadters called them “honey lickers” for this.
One way or another, Medovy survived World War II. And now it leads to the Cathedral from Oktyabrskaya Street. He was almost killed by a barge called "Scarlet Sails" - remember, there was such a floating restaurant on Pregol. During a strong wind, the barge was torn off the anchor and she rammed her bow into the railing of the bridge. Right in the center. But ... local craftsmen successfully solved the problem with the help of an autogen. And the barge was dragged for scrap.
…Other Königsberg bridges appeared much later and have nothing to do with the Euler problem.
So, the Imperial Bridge (Kaiserbrücke) built in 1905 connected the island of Lomse with Vorstadt. The bridge was partly damaged during the war. One of its spans was preserved until the mid-eighties, and then it was scrapped.
Railway and Berlin
The Old Railway Bridge connected the old South and East stations with the Altstadt warehouse district. In 1929, it was recognized as emergency, after four years it was dismantled. And after the war, the first settlers restored the bridge, although not in its former form.
New Zheleznodorozhny - better known as a bunk - was blown up by German sappers during the assault on Königsberg. Soviet sappers "pointed" him immediately after the war. He divorced then, not rising up with both halves, but “driving apart” to the sides by turning.
By the way, it was he who remained in the history of Soviet cinema. In the film "Meeting on the Elbe", which was filmed in Kaliningrad in 1948-1949, there is a shot of former friends and allies, Russians and Americans, crowding on both sides of the river - like the Elbe - and the Americans raise the bridge, thereby marking the beginning of cold war.
So, in the role of the "bridge over the Elbe" our bunk was filmed. They reconstructed it in the late fifties and made it rising.
But the Berlin (Palmburg) - the one behind the village of Borisovo, along the ring road towards Isakovo - froze in a "half-reduced" state. Just froze in a spasm. It was blown up in 1945, before the assault.
high bridge
During the reign of the first secretary of the regional committee of the CPSU Konovalov, one part of the bridge was reduced. The builders proceeded to the second, but from Moscow they angrily shouted at them: “Are you restoring Nemetchyna ?!” As a result, special equipment was sent for scrap, and the bridge remained ... a historical monument. General Koenigsberg-Kaliningrad history. Although restoring it is not a problem.
Monster across the avenue
... By the way, when the Trestle Bridge was being built, the width of its carriageway coincided with the total width of Lavochny and Kuznechny. It was cheaper to restore two parallel bridges - Kuznechny and Potrokhovy - and carry out traffic on them. But ... then megalomania reigned in everything, construction volumes were required.
Even funnier - and more tragic! - happened to that monster that sticks out across Moskovsky Prospekt. The architects - the authors of this "miracle" - claim that they acted on the basis of the German project for the reconstruction of Koenigsberg. In fact, the German plans provided for a completely different bridge - from Kalinin Avenue to Litovsky Val. And this place was chosen solely for mercantile reasons: many residential buildings fell under demolition, people needed to be resettled ... This means that new construction had to be carried out, this is a large amount of investment ... And the architect received a percentage of the shaft: the greater the amount of work, the more impressive the fee. And now ... we have what we have.
... In general, the Euler problem today has a completely different solution. On the remaining bridges in Kaliningrad, it is quite possible to describe a circle without repeating “simple movements”. That's just ... do you want to? And it's not even about the shoes.
Municipal autonomous educational institution
"Secondary 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 in one stroke ……………………………………….12
Conclusion ……………………………………………………………………… 15
References ...…………………………………………………………….16
Annex 1 ……………………………………………………………………………………………………………………………18
Appendix 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. The great philosopher I. Kant, the storyteller Ernst Theodor Amadeus Hoffmann, the physicist Franz Neumann and many others, whose names are inscribed in the history of science and creativity, once lived and worked here. 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) V 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 area 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
Annex 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
Annex 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 was engaged in scientific research until the end of his life: during this time he published about 400 works, their total number exceeds 850. Died Euler in Saint 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., endV
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? 20
W
hell 4. Pavlik - an avid cyclist - depicted on the blackboard 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 along 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 letterA)
with beach and playground. DalekObehind 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 atA
(odd node), it is possible, but it must certainly end in B - in the second odd node, the remaining two nodesWITH
AndD
- even. But Pavlik, too, is telling the truth: his route fromA
VD
really ran along all eight bridges and was unicursal. What is the matter here? What do you think? W 
hell 5
. The English mathematician L. Carroll (the 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
.
OnFigure 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 includedVbypass route) 6
.
Fig.10
W
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
.
