In the context of shortest path algorithms, what is 'relaxation'?
Transforming a directed graph into an undirected graph.
Reducing the priority of a node in the priority queue.
Updating the distance to a node if a shorter path is found.
Removing edges that cannot contribute to the shortest path.
How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It restarts the search from the start node with the updated information.
It ignores the new path and continues with the existing path.
It marks the node as visited and does not consider it again.
It updates the cost of the node and re-evaluates its neighbors.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Binary heap
Queue
Stack
Linked list
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(V + E), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
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.
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 - 1
n
1
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
Infinity if there is no path from the vertex to itself.
The shortest distance from a vertex to itself.
The shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.
What is a potential drawback of using A* search in practice?
It can only be applied to problems in two-dimensional space.
It always requires an admissible heuristic, which can be difficult to define.
It is not guaranteed to find a solution even if one exists.
It can be computationally expensive for large graphs with complex heuristics.
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(E^2 * V)
O(V * E)
O(V + E)
O(V^2 * E)
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
The graph is strongly connected.
The graph has no cycles.
All vertices have the same in-degree and out-degree.
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.
A graph representing a social network has users as vertices and friendships as edges. What does finding the chromatic number of this graph signify?
The maximum number of friendships in the network.
The minimum number of groups that can be formed where no two friends are in the same group.
The maximum number of users who are not friends with each other.
The minimum number of groups that can be formed where everyone knows each other within a group.