You got back to where you started the detour. When you get stuck with this, there are two possibilities: Then go detour using only edges you did not use previously, until that's no longer possible. In that case draw the path you've found so far until you get to a vertex that has not yet all adjacent edges drawn (if none exists, the puzzle doesn't have a solution). You got stuck at a different vertex than you started at, and the starting vertex has all edges already drawn. Repeat until you either solved the puzzle, or found it unsolvable. Then just draw the path you've found so far in reverse (that is, starting where you got stuck, and ending at you original starting point), and then continue until you get stuck again. You got stuck at a different vertex than you started at, and the starting vertex still has not yet drawn edges. Congratulations, you've solved the puzzle! Start at an arbitrary vertex (that is, at an arbitrary intersection). However you'll have to remember the current partial path. As bonus, you'll not even have to seek for a node with odd number of edges if one exists. Here's an algorithm that will give you a solution to this type of puzzle whenever one exists. You've been told many solutions and how to identify a graph where it is possible. There are 4 vertices which have an odd degree. Here is one solution:Īnother example, look at this this shape. In your case, the graph is connected and all your vertices have an even degree, meaning that your problem is solvable. All other numbers means there are no Eulerian trail at all, meaning that the drawing is not possible under these restrictions.If there are 2, then there exists at least one Eulerian trail.Such a graph is called an Eulerian graph. If there are 0, then there exists at least one Eulerian cycle, which is an Eulerian trail which starts and ends at the same vertex.The existence of an Eulerian trail in a connected graph is directly linked to the number of vertices which have an odd degree (the degree of a vertex is the number of segments in the intersection) : In mathematics, drawing a geometric shape without lifting the pen and without tracing the same line more than once is identical to finding a Eulerian trail in the undirected graph composed by the intersections of the shape.
0 Comments
Leave a Reply. |