For each of the following descriptions of a directed graph, say whether they are DAG's (in...

  

Transcribed Image Text:

For each of the following descriptions of a directed graph, say whether they are DAG's (in general). If they are not, give an example of a possible directed cycle within the graph. If they are, give the topological order for the DAG. (a) The graph has a set of non-negative integers as vertices, and there is an edge from x to y if and only if y is a multiple of x and not equal to x. (b) The graph has a set of ordered pairs of non-negative integers (x, y) as vertices, and (x, y) has an edge to (x', y') if and only if x < x' and y < y' or x For each of the following descriptions of a directed graph, say whether they are DAG's (in general). If they are not, give an example of a possible directed cycle within the graph. If they are, give the topological order for the DAG. (a) The graph has a set of non-negative integers as vertices, and there is an edge from x to y if and only if y is a multiple of x and not equal to x. (b) The graph has a set of ordered pairs of non-negative integers (x, y) as vertices, and (x, y) has an edge to (x', y') if and only if x < x' and y < y' or x