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 primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs are always undirected, while weighted graphs are always directed.
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Heap
Stack
Queue
Linked List
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Kruskal's Algorithm
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
Dijkstra's Algorithm
Why are negative weights problematic for some shortest path algorithms?
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
These algorithms assume that adding an edge to a path always increases its total weight.
All of the above
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
Which of the following algorithms is typically used for topological sorting?
Dijkstra's algorithm
Depth-First Search (DFS)
Kruskal's algorithm
Prim's algorithm
You are designing a social network and want to recommend friends to users. What graph algorithm would be most suitable for identifying potential friends based on shared connections?
Breadth-First Search (BFS)
Consider a social network graph where vertices are users and edges are friendships. Which representation would be best for quickly finding all the friends of a particular user?
Adjacency List
In a weighted graph representing a road network with construction delays (represented by negative weights), what does finding the 'shortest path' mean?
Finding the path with the lowest fuel consumption.
Finding the path with the least overall travel time, considering delays.
Finding the path with the fewest road closures.
Finding the path with the shortest geographical distance.
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