Learning About the Graph Construct using Games, Part III - Conditions for a Solution to Exist
(Page 2 of 6 )
We have just defined the problem. As you may have noticed, this problem is very famous, and is repeatedly published in kids' magazines. But, did you know these paths have a name of their own? They are called Euler tours. Euler discovered a way to solve this problem a long time ago, and found the conditions for a drawing to have a solution.
Let's begin at the beginning. What are the conditions for a drawing to have an Euler tour? If we answer this question, finding the tours themselves will be an extremely easy task.
In fact, to know if a drawing has an Euler tour we do the following:
- For every point, count the number of lines coming out of this point.
- If every single point has an even number of lines coming out of it, then this drawing has an Euler tour.
- If exactly two points have an odd number of lines coming out of them, while all others have an even number of lines coming out of them, then this drawing has an Euler tour.
- In all other cases, the drawing doesn't have an Euler tour.
Why is that? It is not as hard as it looks. First, every time you pass through a point and get out, you add two lines to the count of lines coming out of this point. So, except for the very first point and the very last point, all other points should have an even number of lines coming out of them.
What about the first and last points? These have one line coming out of them (the first point), or going into them (the last point), so we could have only two points having an odd number of lines coming out of them.
The other case is when the first point is the same as the last point. So, now, all points have an even number of lines coming out of them, and the problem still can be solved.
Great, now by looking at any drawing, we can very easily determine if it has an Euler tour or not. For example, this figure:
Doesn't have an Euler tour, since the four corners of the square have five lines each. To be honest with you, some guy gave me this problem when I was a kid, and it took me three days of hard work, before I gave up and realized that it was impossible! If I had known the rules above, I wouldn't have wasted all that time!
Now, we turn our attention to the serious problem of finding the actual tour -- in other words, to drawing the figure without passing over any line twice.
Next: Representing the Problem as a Graph >>
More Development Cycles Articles
More By Mohamed Saad
