In an undirected graph, if the sum of the degrees of all vertices is 30, how many edges are there in the graph?
30
Cannot be determined.
15
60
Which of the following graph traversal algorithms is generally more suitable for finding the shortest path in an unweighted graph?
Breadth-First Search (BFS)
Both DFS and BFS are equally suitable.
Neither DFS nor BFS can find shortest paths in unweighted graphs.
Depth-First Search (DFS)
Which of the following is the BEST representation of a graph when the number of edges is much smaller than the number of vertices?
Adjacency Matrix
Edge List
Incidence Matrix
Adjacency List
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Heap
Queue
Stack
Linked List
Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Depth-First Search
Topological Sort
Dijkstra's Algorithm
Breadth-First Search
Which of the following statements accurately describes a key difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
DFS is always more efficient than BFS in terms of time complexity.
DFS is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
DFS explores a path as far as possible before backtracking, while BFS explores all neighbors at the current level before moving to the next level.
DFS uses a queue, while BFS uses a stack for traversal.
A cycle in a graph that is not a simple cycle (visits a vertex more than once) is called a:
Closed Walk
Path
Circuit
Trail
Consider a graph where you want to find if a path exists between two given nodes. Which traversal algorithm would be generally more efficient for this task?
Both DFS and BFS have the same efficiency for this task.
Neither DFS nor BFS can determine if a path exists between two nodes.
Which of the following is NOT a characteristic of a bipartite graph?
It can have an odd-length cycle.
Vertices can be divided into two disjoint sets.
Edges can only connect vertices from different sets.
It can be used to model matching problems.
Removing a vertex from a graph also requires you to remove:
All vertices connected to it.
The vertex with the highest degree.
All cycles in the graph.
All edges connected to it.