(a) The definition of a topological ordering of a graph G= is an ordering of the vertices from 1 to n such that if (i,j) is in E then i

(b) Do Prims and Kruskals algorithms work if some edges have negative weights? Justify (prove or give counter example) in each case. You may assume distinct edge weights.

(c) Consider the following graph. If there is ever a decision between multiple neighbor nodes in the BFS or DFS algorithms, assume we always choose the letter closest to the beginning of the alphabet first.

In what order will the nodes be visited using a Breadth First Search?

In what order will the nodes be visited using a Depth First Search?