What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?
O(V * E)
O(V^2 * E)
O(E^2 * V)
O(V + E)
Which of the following data structures is commonly used to implement the priority queue in A* search?
Queue
Stack
Linked list
Binary heap
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It can handle graphs with negative edge weights.
It only requires a single source vertex as input.
It is more efficient for sparse graphs.
It can detect negative weight cycles.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Sparse graphs with negative edge weights
Dense graphs with positive edge weights
Unweighted graphs
Directed acyclic graphs (DAGs)
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(V^2), where V is the number of vertices
O(V + E), where V is the number of vertices and E is the number of edges
O(E log V), where V is the number of vertices and E is the number of edges
It depends on the heuristic function and can be exponential in the worst case.
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Adding a new vertex and connecting it to all existing vertices.
Adding a new vertex and connecting it to an existing vertex.
Adding an edge between two vertices with different colors.
Removing an edge between two vertices with the same color.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
All vertices have the same in-degree and out-degree.
The graph has no cycles.
The graph is strongly connected.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V
E - 1
V - 1
E
In A* search, what does the heuristic function estimate?
The number of nodes that are yet to be explored
The cost of the cheapest path from the current node to the goal node
The total cost of the path from the start node to the current node
The depth of the current node in the search tree
What is the minimum number of edges that need to be removed from a complete graph with 'n' vertices to make it acyclic (i.e., having no cycles)?
n/2
n
n - 1
1