Home arrow Development Cycles arrow Page 2 - Learning About the Graph Construct using Games, Part III
DEVELOPMENT CYCLES

Learning About the Graph Construct using Games, Part III


In the third and final part of our series about the graph construct using games, we learn about Euler tours, and how to use a graph to solve the problem of whether a figure can be drawn without lifting one's pencil from the paper.

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 11
March 22, 2005
TABLE OF CONTENTS:
  1. · Learning About the Graph Construct using Games, Part III
  2. · Conditions for a Solution to Exist
  3. · Representing the Problem as a Graph
  4. · The Steps Required
  5. · Depth First Traversals
  6. · Solving the Problem

print this article
SEARCH DEVARTICLES

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:

  1. For every point, count the number of lines coming out of this point.
  2. If every single point has an even number of lines coming out of it, then this drawing has an Euler tour.
  3. 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.
  4. 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.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials