How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
It ignores negative weight cycles and finds the shortest path regardless.
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
Both admissible and consistent.
The heuristic must be consistent, meaning it satisfies the triangle inequality.
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
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 minimum number of groups that can be formed where no two friends are in the same group.
The maximum number of friendships in the network.
The minimum number of groups that can be formed where everyone knows each other within a group.
The maximum number of users who are not friends with each other.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Dynamic programming
Divide and conquer approach
Greedy edge relaxation
Reweighting edges using a potential function
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V - 1
V
E
E - 1
Which of the following data structures is commonly used to implement the priority queue in A* search?
Linked list
Queue
Binary heap
Stack
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
The graph cannot exist
Yes
Cannot be determined
No
What is the purpose of the heuristic function in the A* search algorithm?
To store the visited nodes to avoid cycles.
To calculate the exact cost of the path from the start node to the current node.
To determine the order in which nodes are visited during the search.
To estimate the cost of the cheapest path from the current node to the goal node.
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Adding an edge between two vertices with different colors.
Adding a new vertex and connecting it to an existing vertex.
Removing an edge between two vertices with the same color.
Adding a new vertex and connecting it to all existing vertices.
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is planar.
Every vertex has a degree of at least 2.
The number of vertices is greater than or equal to 3.
The graph is connected.