Basic Exercise

In the Project Selection Problem, the profits for projects a, b, c, d, e, f, and g are 8, 5, 3, -2, -1, -4, and 2, respectively. In addition, a’s prerequisites are d and e, b’s prerequisites are e and g, and c’s prerequisite is f. Construct the prerequisite graph G and then extended the prerequisite graph G’. Show how is a minimum cut found in G’. Show the corresponding feasible set of projects with maximum profit.