An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
Cannot be determined
The graph cannot exist
Yes
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is planar.
The graph is connected.
Every vertex has a degree of at least 2.
The number of vertices is greater than or equal to 3.
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 - 1
n
n/2
1
What is the purpose of the heuristic function in the A* search algorithm?
To calculate the exact cost of the path from the start node to the current node.
To store the visited nodes to avoid cycles.
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.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Breadth First Search
Bellman-Ford Algorithm
Depth First Search
A* Search
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Directed acyclic graphs (DAGs)
Unweighted graphs
Dense graphs with positive edge weights
Sparse graphs with negative edge weights
What is a potential drawback of using A* search in practice?
It can be computationally expensive for large graphs with complex heuristics.
It is not guaranteed to find a solution even if one exists.
It always requires an admissible heuristic, which can be difficult to define.
It can only be applied to problems in two-dimensional space.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Divide and conquer approach
Dynamic programming
Reweighting edges using a potential function
Greedy edge relaxation
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 all existing vertices.
Removing an edge between two vertices with the same color.
Adding a new vertex and connecting it to an existing vertex.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Stack
Linked list
Binary heap
Queue