Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It has the minimum total edge weight
It is a tree (acyclic)
It connects all vertices in the graph
It may contain cycles
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
Adjacency Matrix
None of the above
Edge List
Incidence Matrix
How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
In weighted graphs, 'distance' always refers to geographical distance, while in unweighted graphs, it can represent abstract relationships.
In a weighted graph, 'distance' represents the sum of edge weights along a path, while in an unweighted graph, it's the number of edges.
Distance is only defined for unweighted graphs.
There is no difference; 'distance' has the same meaning in both types of graphs.
Which of the following algorithms is typically used for topological sorting?
Kruskal's algorithm
Depth-First Search (DFS)
Prim's algorithm
Dijkstra's algorithm
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
Adjacency List
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
V x E
E x E
V x V
Depends on the graph's connectivity
What is the primary application of topological sorting in computer science?
Scheduling tasks with dependencies
Finding the shortest path between two nodes
Finding the minimum spanning tree of a graph
Detecting cycles in a graph
Which of the following operations is typically less efficient with an edge list representation compared to an adjacency matrix?
Checking if the graph is connected
Determining the degree of a vertex
Finding all edges connected to a specific vertex
Adding a new edge
Topological sorting is possible for which type of graph?
Directed acyclic graphs (DAGs)
Weighted graphs
Complete graphs
Undirected graphs