Execute a depth-first search (Tiefensuche) on the following graph starting from vertex A. Use the algo-...

  

Transcribed Image Text:

Execute a depth-first search (Tiefensuche) on the following graph starting from vertex A. Use the algo- rithm presented in the lecture. When processing the neighbors of a vertex, process them in alphabetical order. A D G B E C F H e) Does the above graph have a topological ordering? How can we use the above execution of depth- first search to find a directed cycle? f) Draw a scale from 1 to 16, and mark for every vertex v the interval I, from pre-number to post- number of v. What does it mean if I, CI, for two different vertices u and v? g) Consider the graph above with the edge from E to D removed. How does the execution of depth-first search change? Which topological sorting does the depth-first search give? If you sort the vertices by pre-number, does this give a topological sorting? Execute a depth-first search (Tiefensuche) on the following graph starting from vertex A. Use the algo- rithm presented in the lecture. When processing the neighbors of a vertex, process them in alphabetical order. A D G B E C F H e) Does the above graph have a topological ordering? How can we use the above execution of depth- first search to find a directed cycle? f) Draw a scale from 1 to 16, and mark for every vertex v the interval I, from pre-number to post- number of v. What does it mean if I, CI, for two different vertices u and v? g) Consider the graph above with the edge from E to D removed. How does the execution of depth-first search change? Which topological sorting does the depth-first search give? If you sort the vertices by pre-number, does this give a topological sorting?