One of the important areas of current mathematics, topology, was born with the following riddle the great Euler described and solved in one of his articles: "The problem, as I understand, is very well known, is stated as follows: In the city of Königsberg in Prussia, there is an island called Kneiphof, surrounded by two branches of the Pregel river. There are seven bridges, A, B, C, D, E, F and G, the two arms crossing river. The question is whether a person can perform a walk so that cross each bridge only once. He has informed me that while some denied doing so others doubted, nobody claimed it was really possible. "
So where can you begin to tackle the problem? Think and observe. There are many aspects of the problem that are totally irrelevant, that do not matter at all. For example, the island is larger or smaller, the bridges are narrower or wider, straight or longer or shorter curved. What is essential is the scheme, which bridges together and how they behave towards each other unions. The bottom line is therefore the following: Can you draw the following picture of a single stroke without repeating any lines?
This already suggests you some of your childhood memories. Could you repeat the following figures without lifting the pencil from the paper and without repeating the same line twice? Could you do the same somewhere leaving and returning to the same point?
Figure 4 is so easy to draw that, unless you do not do bad idea, leaving any point you get to the same point without repeating arches and scrolling all, and that almost without trying. Figure 2 seems simpler, has fewer lines, but for her, as for Figure 6 only three strokes.
Both are impossible given very clear way, trivial, as is sometimes said insultingly. Figure 5 seems to be no christian that analyze, but there have a solution:
What is the mystery of the arcs of a case and another? How to find out if a drawing can be done as requested and other not? And if you can, how do you find the recipe?
Let's start with simple cases:
Figure 8 can but can not get out and get to the same point. Figure 9 can be if it gets out of A ending in B. And also you can get if B leaves ending in A, but if we left C we can not. Figure 10 can not be done at all. Figure 11 can be out of any point and ends at the same point. What distinguishes the vertices is clear. The number of possible inputs and outputs of them, ie the number of arc occurring in each. Here are those numbers, the degree of each vertex:
And why is that number important? What stuck us in a corner is the lack of an exit. But having many inputs and outputs is not always good. Figure 12 has more inputs and outputs than the Figure 3 and 3 is however possible and 12 impossible. Consider a possible figure of trace back to the same starting vertex. For each vertex of the path, as we do not stop it, it turns out as many times as we went, naturally different arcs.
Thus, each vertex is of even degree . The first well, as we return to finish it.
So if a figure is possible ending in the same vertex output must have all vertices of even degree.
So if a figure is possible ending in the same vertex output must have all vertices of even degree.
Explains that our problem?
Completely?
Not yet!
Will it be that if all vertices are of even degree we can take a tour coming to end the vertex output ? Let's see!
What is certain is that we never get stuck in our way if not in the output vertex S, because as each vertex is of even degree, to enter one that is distinct from S for the first time we have a odd number of arcs output, i.e., at least one arch, we enter the second time is again an odd number, then we used three arches which contribute to that vertex, so whenever we go out we can.
Therefore, our figure walking out of S, we get stuck only being in S again. If we have come across the figure we have our problem solved. And if we have not traveled? If we are missing our way C arcs go, the truth is that we can proceed and to expand our way and make a larger one to keep checking the game. When we reach the first vertex of S1 exiting arcs that are not paths, let them. As before, we can not stop us if not in S1. Now, when S1 we are paths all arcs coming out of it, still from S1 by the initial path C until the first vertex S2 which presents arcs that are not paths or the path C or the extension that just did. So, just go all arcs.
Therefore, if all arcs are of even degree, the proposal is possible and we have the recipe to trace the request path.This recipe also tells us that the output vertex, which can be any, is necessarily the same as the final!
What if there are odd vertices? Look again at Figure 9.
If leaves of A or B, you get to do it, but not if you leave C. The vertices A and B are both odd, the C is even.
What mystery is this? What once took us to the solution can tell us how to proceed now. In a path like we have to do there is an initial vertex, end vertex and all others pass. But a vertex of step (or initial or final) has many arches input and output, is even degree. So if a figure supports a path as that calls step every vertex must be even. But the vertices of passage are all but two. Therefore, if a figure has more than two odd vertices, it is impossible.
Moreover, if a figure has two odd vertices, if we try to trace it by the rules, we will have to leave one of the odd vertices and try to finish in the other odd vertex. We only have a matter to be completely resolved our problem. If a figure has two or just an odd vertex, is it possible?
If a figure we have one or two odd vertices, left with one choice of S. We can not get stuck in any pair vertex, because if we can get out of it , nor in S, since the emerging spend one of their bows and so you then get an even number of them and, therefore, if we re-enter can exit.
We get stuck in the other odd vertex, which shows that there can be a single odd vertex.
Now we ask: we have come to this path C whole figure? If so, congratulations, and we have our problem solved. It is not?
Then proceed as before. We left 'S' on the road 'C' until the first vertex of S1 arches leaving no road routes C. Note that all vertices that still have no route arcs C lack an even number of arcs go. So, coming out of S1 by arcs that are not in C we do not get stuck in any vertex other than S1. Thus we arrive at S1 for C1 path arcs that are not in C having traveled all the arcs of S1 that were not in C. Now we can continue by C until the first vertex S2 having arches that are not in C or C1. Proceed well, and so just go all arcs of figure.
NOTES
The method, which we have seen to solve problems like the bridges of Königsberg, also allows us to solve the problem of reaching the center of any maze that put us ahead, even without knowing its structure at all.Resolve to reach the entry point stated treasure in the R. Ball maze garden (one of the greatest writers of mathematical recreations of all time). Suppose that we have no map and therefore our aim should be walking around the maze (assuming, of course, is well illustrated treasure somewhere in the maze that you can get) and exit through the only entrance there.
Can we do it?
YES!
The path is the maze (italicized line in the second figure) consists of arcs and bifurcation points. As each arc we go once we round another turn, repeat twice each arc. Once done, we have a figure as we have been studying in this chapter with all pairs vertices. So she can go without repeating all arcs starting from any point. In addition, we can do without knowing the map of the maze. All we need is to point out the arches somehow we have already covered.
To do this simply with a chalk. In each bifurcation point out with an arrow which path we have taken to not take it back when we're in the same spot.
Naturally, this approach does not give us the shortest way to the treasure, but it does provide us get there and get back out.
That's all buddy!!
SEE YOU SOON!
