An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
E x E
V x E
Depends on the graph's connectivity
V x V
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Determining if the graph has a Hamiltonian cycle.
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Finding the shortest path between any two vertices.
Calculating the minimum spanning tree of the graph.
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?
Shortest Path
Community Detection
Graph Coloring
Minimum Spanning Tree
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It is a tree (acyclic)
It connects all vertices in the graph
It may contain cycles
It has the minimum total edge weight
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
0
-1
Infinity
1
Which algorithm is more suitable for finding the shortest path in a graph with negative edge weights?
Kruskal's algorithm
Dijkstra's algorithm
Prim's algorithm
Bellman-Ford algorithm
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a tree
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in an unweighted graph
Finding the shortest path in a dense graph
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Queue
Linked List
Heap
Stack
Why are negative weights problematic for some shortest path algorithms?
All of the above
These algorithms assume that adding an edge to a path always increases its total weight.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
If a graph has negative weight cycles, what can we say about finding the shortest path?
Bellman-Ford algorithm will take significantly longer to find the shortest path.
Dijkstra's algorithm will always find the correct shortest path.
The graph must be undirected to have negative weight cycles.
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.