Home arrow Development Cycles arrow Page 4 - 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 - The Steps Required
(Page 4 of 6 )

Given a graph, here is the method we are going to use:

  1. Count the number of edges coming out of every node (This is called the outdegree).
  2. If exactly two nodes have an odd number of edges, let's mark them as u,v.
  3. If no nodes have an odd number of edges, set u and v to point to the first node.
  4. In all other cases, exit, and report no solution.

Up until now, we have seen nothing new. We have just made sure a solution exists, and we marked the start and end node of the path (If all nodes have an even outdegree, we mark the first node of the graph as both the first and last nodes).

Now, the real fun starts.

  1. Find a path from node u to node v (a path is just a collection of connected edges starting at node u and ending at node v), and mark all edges as taken.
  2. If there are still edges not taken, start at any node that has an untaken edge coming out of it, and find a loop that starts and ends at this node. (A loop is simply a path that starts and ends at the same node). Mark all edges of the loop as taken.
  3. If there are still edges not taken, go back to step six.

Up until now, we came up with a path, and a collection of zero or more loops.

There are four steps remaining. But, before going on, let's look at an example of this in action.

For this figure:

We may start by determining that the start and end points are going to be 3 and 4 (The only one having an odd number of edges)

First we find a path. Let's suppose it will be like this:

Then we find a loop starting at a certain point, such as 3. It is marked in blue here.

Then we find another loop, marked below in green.

Now, the whole graph is covered, and we are nearly finished. All that remains is to output the sequence of edges to follow.

  1. Start at the start node we chose in step 2 or 3 above
  2. If you find a new loop starting at this node, go for it else…
  3. If you are already in a loop, continue walking in it else…
  4. Walk on any edge you have not yet visited.

The last four steps are the steps required to actually output the solutions. We have found the path, and all the loops. Intuitively, what these steps do is simply merge all the loops, and the path together to form a full Eulerian tour on the graph.

Ok, so these were the steps required to solve the problem. Is everything over? Umm...no actually, because we still don't know how to find a path between two nodes! Also, how can we find a loop starting at a certain node? In the previous part, we tackled the problem of finding the shortest path. Certainly we can use it here to find paths too, but this will be an over-complication, since we are not really interested in the shortest path. We are only interested in finding any path. We will show an easier way to find paths and loops. First let's  look at…


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