Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is connected.
The graph is planar.
The number of vertices is greater than or equal to 3.
Every vertex has a degree of at least 2.
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It can detect negative weight cycles.
It can handle graphs with negative edge weights.
It only requires a single source vertex as input.
It is more efficient for sparse graphs.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Sparse graphs with negative edge weights
Directed acyclic graphs (DAGs)
Unweighted graphs
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 can be computationally expensive for large graphs with complex heuristics.
It is not guaranteed to find a solution even if one exists.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It adds a large constant to all edge weights to make them positive.
It reweights the edges using a shortest path potential function.
It removes all negative edges from the graph.
Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding the shortest path in an unweighted, undirected graph.
Determining if a graph is connected.
Finding all possible paths between two vertices in a graph.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
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.
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
Which of the following data structures is commonly used to implement the priority queue in A* search?
Binary heap
Queue
Linked list
Stack
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Greedy edge relaxation
Dynamic programming
Reweighting edges using a potential function
Divide and conquer approach
In a graph coloring problem, what scenario leads to the requirement of an additional color?
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.
Adding a new vertex and connecting it to all existing vertices.