300000
Total number of wins: 111541
| (6 – 20): | Cycle Path Random Challenge |
Definitions + How is this still a "math" game?
The diagrams in this game are based on a field of mathematics known as graph theory!
What is a graph?
Graph: A graph consists of nodes and edges.
Node: The "objects" a graph connects are called nodes. In Spider Web, nodes are the circles.
Edge: An edge is a connection in the graph between two nodes. In Spider Web, the edges are lines.
Extending a path
Path: A path is a sequence of connected edges with a start node and end node.
Eulerian Path: This is a path that uses each edge in the graph exactly once.
The goal in this game is to find an Eulerian Path.
What are Eulerian paths in everyday lifes?
A snowplow, a street cleaning truck, and a postman are examples for cars and people that need to go through each street but want to avoid going through a street twice.
Does the name "Euler" sound familiar?
Graph theory started when mathematician Leonhard Euler was working on this kind of paths.
Euler wrote a paper on the Seven Bridges of Königsberg proving that it was impossible to walk through the city crossing over each bridge exactly once.
Click the map of the problem below to read more about it.
Cycle: A cycle is a path that ends on the node it started on.
Eulerian Cycle: This is an Eulerian Path that is also a cycle. Select "Cycle" in our game above and the solution will always be an Eulerian Cycle!
Game Settings Instructions
In the textbox next to Nodes, you can type in any number between 6-20. This number will be the number of nodes displayed on the graph. The larger the number the more challenging the solution becomes!
Next, select a Type of graph
Cycle: Winning paths will always end on the node they started on.
Path: Winning paths will not end on the node they started on.
Random: Graphs that may allow an Eulerian cycle or an Eulerian path. Winning paths may or may not end on the node they started on.
Challenge: Hand-crafted graphs where edges cross and therefore bridges are not obvious to spot.
Finally, click "Create a New Web" to see your changes to the graph settings!
What node should I pick first?
Degree: The degree is a property of a node. It is the number of edges connected to it. We will distinguish between odd-degree nodes and even-degree nodes, depending on their degree.
Connected Graph: A graph where every pair of nodes can be connected through a path.
Bridge: An edge is a bridge if the two ends of the edge can not be connected otherwise. Thus after crossing a bridge, one will not get back to the previous side. Removing a bridge splits the graph into two disconnected components.
Undirected Graph : A graph where edges have no direction atttached. We only consider those in this game.
Directed Graph : A graph where each edge has a direction atttached like a one-way street.
An undirected graph contains an Eulerian Cycle when all of the nodes have an even degree (degree of 0, 2, 4, 6...). For these, you may select any node as your starting node and still win. Just keep in mind that you will have to finish on the node you started from.
A graph contains an Eulerian Path, but not an Eulerian Cycle, when exactly two nodes have an odd degree (degree of 1, 3, 5, 7...) and all other nodes have an even degree. In this case, you must select a node with an odd degree as your starting node or you will not be able to complete the Eulerian Path.
Why exactly two nodes?
Think of each move as "out" of the node you came from and "in" to the node you travel to. Most nodes will follow this pairing pattern, so they will have an even degree.
When you start the game, the first edge you mark is a move "out" of the starting node. This remains unpaired as you play the game.
To make an Eulerian Cycle, the final edge you mark is a move "in" to the starting node. This creates a pair with the first move, meaning the starting node has an even degree.
If the graph's Eulerian Path is not a cycle, the final edge you mark is an unpaired move "in" to a node that is not the starting node. The starting node remains with an odd degree, and the ending node will also have an odd degree.
Don't worry about any other cases. If the number of nodes with an odd degree were not exactly 0 or 2, there would be no Eulerian Paths and no Eulerian Cycles, meaning no way to win. Graphs like that should not appear in this game.
Preliminary Questions
Can there be an odd number of nodes with an odd degree?
No.
Why?
Proof:
Counting all ends of all edges gives the same number as adding up all degrees of all node, agreed?
Because each edge has 2 ends, the total number of ends of all edges must be even. (Adding up even numbers gives an even number.)
To add up the degrees of all nodes, one would add up the even degrees which gives an even number and add up the odd degrees.
If there were an odd number of odd-degree nodes then that sum would be odd and then even + odd = odd, so the total number of degrees would be odd. But it is equal to the total number of all ends of all edges and that is even. Therefore, the number of odd-degree nodes can not be odd, it must be even.
For example, 1 is an odd number, so there is no graph with only 1 odd-degree node.
When does an Eulerian Path or Cycle exist?
If a node has an even degree, i.e. 2, 4, 6,... edges are attached to the node, then when arriving at that node, an odd number of unused edges is left which is bigger than zero, so one will be able to leave that node and go on. If the degree is odd, i.e. 1, 3, 5,.. edges are attached then one either must start the path at this node or the path will end at this node. Because a path has only 2 ends, there can be only 2 nodes with odd degree. Therefore:
To have an Eulerian Cycle, a graph must have only even-degree nodes, and to have an Eulerian Path, it must have 2 odd-degree nodes, one node will be the start and one will be the end of the path.
How does one find an Eulerian Path or Cycle?
As shown above, if there are no odd-degree nodes, then one can start at any node and will end at the same node. If there are exactly 2 odd-degree nodes, then one needs to start at any one of these 2 nodes and will automatically end at the other one.
Can something go wrong when extending the path?
Yes, something can go wrong. Example:
2 4 / \ / \ 1---3---5
The degree of all nodes is 2 except node 3 which has degree 4. So all degrees are even and we can start anywhere. Let us start at node 1 and go to node 3 and let us drop all edges that have been traversed.
2 4 / \ / \ 1 3---5
The edge 3-2 becomes a bridge. Crossing and removing this edge 3-2 produces a disconnected graph
2 4 / / \ 1 3---5
which can not be completely traversed anymore. Therefore, one should continue from 3 to 4 or to 5 to complete the Eulerian cycle.
How can one prevent crossing a bridge?
To check whether an edge is a bridge, one would start on one end of the edge and visit all it's neighbour nodes and all of their neighbours and so on. If one does not get to the other side of the edge, then the edge is a bridge. Such a complete search of all neighbours is not very expensive. But if one has to do it before crossing each edge, then the total effort is big. The complete algorithm is called Fleury's algorithm, dating back to 1883.
Is there a more efficient algorithm?
A more efficient algorithm is that of Hierholzer (1873).
If the graph has 2 odd-degree nodes, then one finds a path otherwise a cycle, in both cases very fast without checking for bridges.
1) After removing all used edges, the degree of the remaining unused edges is even for all nodes.
Why?
If the degree of a node was even, then it was equally often approached as it was left, so it is still even. If the degree was odd, then it is either the start node or the end node of the first path and then it was left + approached in total an odd number of times, so the remaining degree is odd − odd = even.
2) There must be at least one node with used and unused adjacent edges.
Why?
Because the original graph was connected.
Because of 1) one can find a cycle of unused edges, starting and ending at this node. Because of 2) this cycle can be included in the first path/cycle when it reaches this node. This embedding of cycles of so far unused edges is repeated until all edges are used and one therefore has an Eulerian path or Eulerian cycle that uses all edges.
What is the price of this faster version?
One has to remember the previous path/cycle so that one can include the extra cycle.
Example:
2 4 / \ / \ 1---3---5
Let the first cycle be 1-3-2-1. Node 3 occurs in this cycle and in the unused cycle 3-4-5-3. We insert it into the first cycle and get cycle 1-3-4-5-3-2-1. There are no more unused edges so the algorithm ends here, we found the Eulerian cycle.
How can a cycle be inserted using our interface?
One can click 'Undo' until one has reached the most recent node which has used and unused edges, like node 3 above, and then go through the cycle 3-4-5-3 and then continue with the un-done edges.
If there is an odd-degree node, does one need to find both of them to draw a first path from one to the other?
No. If one finds only one, then one can start the path at this node and one will automatically end up at the other odd-degree node whether one uses all edges or not.
Why?
Because when one arrives on an even-degree node, then an odd number of attached edges have been used.
Why?
Each time one arrived at a node, one also left the node, so an even number of edges are used. Now, one arrives and uses one edge on an even degree node. so one used in total an odd number of edges on the even degree node.
Even − odd = odd, thus an odd number of unused edges is left. An odd number is always non-zero, so there is at least one unused edge that can be used to leave that node. Therefore, one will automatically end at the odd-degree node whether all edges were used or not.
Do you have a suggestion how can one find one odd-degree node?
One could of course check the degree of each node until one finds an odd-degree node. Here is a way without counting.
One can pick any node. If its degree is odd, then one has found one. If not, then one starts at this node to draw a cycle. It will end at either an odd degree node, then one has found an odd degree node, or one will end at the starting node. If so, then one ignores all used edges and does that again i.e. pick a node and draw a path or cycle. This goes on until one either finds an odd-degree node or there are no more unused edges. Then all nodes have an even degree.
What if the graph is like a city with 1-way streets?
A graph with edges that can only be traversed in one direction is called a directed graph. Following the argumentation above, the following 2 statements are plausible.
A directed graph allows an Eulerian Cycle, if and only if, for each node the number of outgoing edges is equal the number of incoming edges.
A directed graph allows an Eulerian Path, if and only if
• one node has one more outgoing edge than incoming edges,
• one node has one more incoming edge than outgoing edges, and
• all other edges have the same number of outgoing and incoming edges.
Follow or subscribe for updates: