Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It is a tree (acyclic)
It may contain cycles
It has the minimum total edge weight
It connects all vertices in the graph
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
Incidence Matrix
Edge List
Adjacency Matrix
None of the above
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
It depends on the specific graph operations
Which graph traversal algorithm is most efficient for detecting cycles in a directed graph, crucial for identifying dependencies in a project management system?
Depth-First Search (DFS)
Kruskal's Algorithm
Prim's Algorithm
Breadth-First Search (BFS)
You are tasked with designing a system to schedule tasks with dependencies between them. What graph data structure would be most appropriate to represent these dependencies?
Bipartite Graph
Complete Graph
Undirected Graph
Directed Acyclic Graph (DAG)
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
No, the MST is unique for a given graph
Yes, different starting vertices may lead to different MSTs
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
-1
0
1
Infinity
What is the primary challenge in finding shortest paths in graphs with negative weight cycles?
Negative weights make it impossible to define a meaningful concept of 'shortest' path.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
Standard shortest path algorithms are not designed to handle cycles.
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Dijkstra's Algorithm
Floyd-Warshall Algorithm
Bellman-Ford Algorithm