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 an edge between two vertices with different colors.
Removing an edge between two vertices with the same color.
Adding a new vertex and connecting it to an existing vertex.
In the context of shortest path algorithms, what is 'relaxation'?
Removing edges that cannot contribute to the shortest path.
Reducing the priority of a node in the priority queue.
Updating the distance to a node if a shorter path is found.
Transforming a directed graph into an undirected graph.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Greedy edge relaxation
Reweighting edges using a potential function
Dynamic programming
Divide and conquer approach
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^2 * E)
O(V * E)
O(V + E)
O(E^2 * V)
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Both Dijkstra's and Bellman-Ford algorithm
Only Dijkstra's algorithm
Only Bellman-Ford algorithm
Neither algorithm can find the shortest path
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The shortest distance from a vertex to itself.
The shortest distance from the source vertex to that vertex.
Infinity if there is no path from the vertex to itself.
The number of edges in the shortest path from a vertex to itself.
In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(E log V)
O(V^3)
O(V^2)
O(V log V)
Which of the following data structures is commonly used to implement the priority queue in A* search?
Queue
Stack
Linked list
Binary heap
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
The graph cannot exist
Cannot be determined
Yes
What is the relationship between A* search and Dijkstra's algorithm?
A* is a generalization of Dijkstra's algorithm.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
A* and Dijkstra's algorithm are entirely unrelated.
Dijkstra's algorithm is a special case of A* search.