Answer the following questions: 1. How many arcs (edges) are there? 2. How many

ID: 3850083 • Letter: A

Question

Answer the following questions:

1. How many arcs (edges) are there?

2. How many acyclic paths are there from node a to node d ? What are they?

3. What are the predecessors of node b?

4. What are the successors of node b?

5. How many simple cycles are there? List them. Do not repeat paths that differ only in the starting point.

6. List all the non-simple cycles of length up to 7.

7. Find all the paths from a to d that do not repeat any node.

8. How many simple cycles are there that include all six nodes? List these cycles.

9. What are the neighbors of node a?

Depth First Search

10. Call DFS(d, G) to generate the list of all possible vertices that are reachable from d.

Maximum Flow:

Follow Ford-Fulkerson method to find the maximum flow of this given flow-network. (source node: 1 and sink node: 6)

Question 1:

There are 9 edges in this graph. List of edges is as follows:

f->a , e->f, d->e , c->d , b->c, a->b, a->d, b->f, e->b.

Question 2:

There are two acyclic paths from a to d.

Path 1: a->d

Path 2: a->b->c->d

Question 3:

In the directed graph, if there is an edge from node a to node b, Node a is a predecessor of node b. Node b is the successor of node a.

So, there are two incoming edges at node b from node a and node e.

So there are two predecessors of node b 1) node a and 2) node e.

Question 4:

So, there are two outgoing edges from node b to node c and node f.

So there are two successors of node b 1) node c and 2) node f.

Note that you have posted multiple questions, so according to chegg rules, I have answered first 4 subparts!

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.