Impossible DFS of Directed graph question

0
votes

Consider the following directed graph. For a given n, the vertices of the graph correspond to the integers 1 through n. There is a directed edge from vertex i to vertex j if i divides j. Draw the graph for n = 12. Perform a DFS of the above graph with n = 12. Record the discovery and finish times of each vertex according to your DFS and classify all the edges of the graph into tree, back, forward, and cross edges. You can pick any start vertex (vertices) and any order of visiting the vertices.

I do not see how it is possible to traverse this graph because of the included stipulations. It is not possible to get a back edge because a dividing a smaller number by a larger number does not produce an integer and will never be valid.

Say we go by this logic and create a directed graph with the given instructions. Vertex 1 is able to travel to vertex 2, because 2 / 1 is a whole number. However, it is impossible to get to vertex 3 as vertex 2 can only travel to vertex 4, 6, 8, or 10. Since you cannot divide by a bigger number it will never be possible to visit a lower vertex once taking one of these paths and therefore not possible to reach vertex 3.

1
depth-first-searchdirected-graph
Please edit your question to include a sample vertex you want to use, show which edges you have already classified (and why) and explain where you stuck based on the given graph/example. – Progman
@Progman I added some clarification to the problem involving my thought process trying to traverse from starting vertex 1. – codefreak1996

1 Answers

0
votes

Your assumption about the back tracks is correct. You cannot have back tracks because you don't have any circles. Consider the following example:

When we start at 2 we will find the edges 2->4, 4->8, 4->12, 2->6 and 2->10. The edges 2->8 and 2->12 are forward edges, they are like shortcuts to get forward much faster. The edge 6->12 is a cross edge because you are switching from one branch to another branch. And since we have no circles to somehow get back to a previous node, we don't have any backward edges.