What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
Unweighted graphs are always undirected, while weighted graphs are always directed.
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
Depends on the graph's connectivity
V x E
V x V
E x E
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
Incidence Matrix
It depends on the specific graph operations
Edge List
Adjacency Matrix
What is the primary challenge in finding shortest paths in graphs with negative weight cycles?
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
Standard shortest path algorithms are not designed to handle 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.
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a dense graph
Finding the shortest path in an unweighted graph
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in a tree
What is the primary application of topological sorting in computer science?
Finding the minimum spanning tree of a graph
Scheduling tasks with dependencies
Detecting cycles in a graph
Finding the shortest path between two nodes
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Bellman-Ford Algorithm
Breadth-First Search (BFS)
Dijkstra's Algorithm
Prim's Algorithm
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Disjoint Union Set (Union-Find)
Stack
Heap
Queue
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 shortest geographical distance.
Finding the path with the fewest road closures.
Finding the path with the least overall travel time, considering delays.
In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
2
0
1
V (number of vertices)