Algorithmic Graph Theory II

An edge is a ------------- crossing a cut if its weight is the minimum of any edge crossing the cut

• safe edge

• light edge

• spanning edge

• none of these

In Kruskal’s algorithm, the set A is a ……….. whose vertices are all those of the given graph

To combine trees, Kruskal's algorithm calls the ADD -SET Procedure

• True

• False

The running time of Kruscal's algorithm is -------

• O(V lg E)

• O(E lg V)

• O(E +lg V)

• O(V +lg E)

Prim’s algorithm has the property that the edges in the set A always form a …………...

• forest

• single tree

• cycle

• single vertex

     For Prim’s algorithm the tree starts from an arbitrary root vertex.

• True

• False

• decrease

• increase

Dijkstra's algorithm and the shortest paths algorithm for directed acyclic graphs relax each edge ---------

• two times

• unlimited times

• atleast once

• exactly once

The Bellman-Ford algorithm relaxes each edge ------------ times

• 1

• 2

The Bellman-Ford algorithm returns a ----------- whether or not there is a negative weight cycle