What is the degree of a vertex in a graph?
The number of edges connected to that vertex.
The number of self-loops on that vertex.
The length of the longest path starting from that vertex.
The total number of vertices in the graph.
Adding an edge between two vertices in an undirected graph always:
May increase or decrease the number of connected components.
Creates a cycle.
Decreases the number of connected components.
Increases the number of connected components.
Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Edge List
Adjacency List
Incidence Matrix
Adjacency Matrix
Which of the following is an advantage of using an adjacency matrix representation for a graph?
Efficient for sparse graphs.
Less memory usage for large graphs.
Constant time edge existence check.
Faster to find all neighbors of a vertex.
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Linked List
Queue
Heap
Stack
Which of these scenarios is BEST represented using a weighted graph?
Finding the shortest path between two cities on a road network with distances.
Representing the hierarchical structure of a company.
Modeling the flow of information in a computer network.
Storing the friendship relations between people on a social media platform.
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Skipping certain branches of the graph to improve efficiency.
Using a heuristic function to guide the search towards the goal node.
Returning to the parent node after exploring all descendants of a node.
Revisiting already explored nodes to find alternative paths.
In an undirected graph with 5 vertices, what is the maximum number of edges possible?
5
10
25
20
Which type of graph is MOST suitable for representing a one-way system on a city map?
Directed Graph
Weighted Graph
Undirected Graph
Tree
Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Dijkstra's Algorithm
Breadth-First Search
Topological Sort
Depth-First Search