Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
None of the above
Incidence Matrix
Adjacency Matrix
Edge List
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Calculating the minimum spanning tree of the graph.
Finding the shortest path between any two vertices.
Determining if the graph has a Hamiltonian cycle.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
What is the primary application of topological sorting in computer science?
Finding the shortest path between two nodes
Finding the minimum spanning tree of a graph
Detecting cycles in a graph
Scheduling tasks with dependencies
Which graph traversal algorithm is most efficient for detecting cycles in a directed graph, crucial for identifying dependencies in a project management system?
Prim's Algorithm
Depth-First Search (DFS)
Kruskal'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
Undirected Graph
Directed Acyclic Graph (DAG)
Complete Graph
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
-1
0
Infinity
1
Social media platforms utilize graph analysis to detect communities or clusters of users with shared interests. What graph concept is employed to identify these densely connected groups?
Graph Coloring
Minimum Spanning Tree
Community Detection
Shortest Path
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Queue
Heap
Stack
Disjoint Union Set (Union-Find)
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 shortest path might involve traversing a cycle repeatedly to minimize the total weight.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
Standard shortest path algorithms are not designed to handle cycles.
Topological sorting is possible for which type of graph?
Weighted graphs
Directed acyclic graphs (DAGs)
Undirected graphs
Complete graphs