CS 344 HW #4
If the problem has a solution, then there are no dead ends and no intersections with an odd degree.
If we have a solution, it is obvious that there cannot be any dead ends because you only traverse a road once. However, if you have a dead end, you have to traverse it twice. This is because, since you have to go down the dead end to check if there are any power shortages, to get out of that street, you have to turn around and traverse the same road. Therefore, if there is a solution, then there are no dead ends.
In addition, if there is a solution, all the intersections must be even. This is because, every time you go to an intersection, you need to take an unused path to get out. Therefore, this means that there must be an even number of paths leading to the intersection. If there is an odd number, then that means on the last path toward the intersection, there will not be a corresponding path to leave the intersection. Which means, you must traverse a path you have already taken and therefore, this would not have a solution. In conclusion, if you have a solution, then all intersections must have an even degree.
If there are no dead ends and no intersections with an odd degree, then there is a solution.
Since there are no dead ends, or odd degree intersections, you will never be stuck at a node. This means that whenever you go on a road (edge) to a node, there will always be a path that you can take to leave that node. Since all the intersections have even degrees, this means that for every node and each edge that goes into that node, there will be one edge you can take to leave it. So this means that you will always have a new path to take, and that the only time you run out of paths is when you return to teh beginning. Therefore, if there are no dead ends or odd intersections, then there exists a solution.
The algorithm for this problem is quite simple. Since any path you choose will work, we will use Depth First Search to traverse through the whole graph. However, instead of keeping track of the nodes we visited, we will keep track of the edges we traversed through. Then, we will continue along the graph until we hit all the edges, and the path provided will take linear time. If we ever get to a point where you must revisit an old edge and all the edges haven’t already been visited that means there is no solution.
This problem essentially asks to find the longest path between A and D.<