Learning About the Graph Construct using Games, Part III

To solve this problem, first, we will represent the figure as a graph. Unlike the previous problem, the reduction to a graph is quite clear here. Each point will be represented as a node, and lines will be edges in the graph.

Question: should the graph be directed or undirected? Answer: clearly the graph is undirected in this case. There is no specific direction for any of the lines in the figure. Remember from part 1 that, to represent an undirected graph, we actually need to put in two edges for every edge. For an edge connecting u and v, we have to put an edge going from u to v, and another one going from v to u.

There are small modifications from the graph we used in the previous two parts. The classes are a little different:

class node
{
  String data;
  node2 links;
  boolean equals(node t)
  {
    if(t.data.equals(data))
      return true;
    return false;
  }
}

class node2
{
  int id; //this is an edge. The id is the id of the node this edge is going to
  int color; //color of this edge
  boolean taken;
  node2 next;
}

If you remember, the class node represented a node of the graph. It contains a linked list of all the edges this node has. We have just added a String to it, to have a label for every node. (This will be useful when we output the solution later).

In the class node2, which represents one node of the linked list, we have added two new members: the color, and taken. They will both be used later when we start solving the problem.

In the class itself, we add also two small functions…

void addUndirectedEdge(String a,String b)
{
  addEdge(a,b);
  addEdge(b,a);
}

Pretty self explanatory, huh?

And another easy one…

void prepare()
{
  addUndirectedEdge("1","4");
  addUndirectedEdge("2","3");
  addUndirectedEdge("2","5");
  addUndirectedEdge("3","5");
  addUndirectedEdge("1","3");
  addUndirectedEdge("2","4");
  addUndirectedEdge("1","2");
  addUndirectedEdge("3","4");
}

This is where we construct the graph. The one above is the envelope we talked about before. We can modify this function to insert any new shapes we would like.

So, still, how are we going to solve the problem at hand? How can we find the Euler tour?