An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
E x E
V x E
V x V
Depends on the graph's connectivity
If a graph has negative weight cycles, what can we say about finding the shortest path?
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.
Dijkstra's algorithm will always find the correct shortest path.
Bellman-Ford algorithm will take significantly longer to find the shortest path.
The graph must be undirected to have negative weight cycles.
Topological sorting is possible for which type of graph?
Weighted graphs
Complete graphs
Directed acyclic graphs (DAGs)
Undirected graphs
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
Tracking the spread of information in a social network
Representing relationships in a family tree
Modeling financial transactions where profits and losses are possible
Finding the shortest route between two cities on a map
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
Kruskal's Algorithm
Depth-First Search (DFS)
Breadth-First Search (BFS)
Which algorithm is more suitable for finding the shortest path in a graph with negative edge weights?
Prim's algorithm
Bellman-Ford algorithm
Kruskal's algorithm
Dijkstra's algorithm
You are building a flight routing system. What graph algorithm can you use to find the cheapest flight itinerary with potentially multiple layovers?
A* Search Algorithm
Bellman-Ford Algorithm
Dijkstra's Algorithm
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
Incidence Matrix
None of the above
Adjacency Matrix
Edge List
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
In a GPS navigation system, what graph algorithm is commonly used to find the shortest route between two locations represented as nodes on a road network?
Floyd-Warshall Algorithm
Topological Sort