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
What is the primary distinction between an unweighted graph and a weighted graph?
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 have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs are always undirected, while weighted graphs are always directed.
Why are negative weights problematic for some shortest path algorithms?
These algorithms assume that adding an edge to a path always increases its total weight.
All of the above
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It may contain cycles
It has the minimum total edge weight
It connects all vertices in the graph
It is a tree (acyclic)
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?
Depth-First Search (DFS)
Dijkstra's Algorithm
Bellman-Ford Algorithm
Breadth-First Search (BFS)
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
Which of the following operations is typically less efficient with an edge list representation compared to an adjacency matrix?
Checking if the graph is connected
Adding a new edge
Determining the degree of a vertex
Finding all edges connected to a specific vertex
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.
Standard shortest path algorithms are not designed to handle cycles.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
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?
Minimum Spanning Tree
Graph Coloring
Shortest Path
Community Detection
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 shortest geographical distance.
Finding the path with the fewest road closures.
Finding the path with the lowest fuel consumption.
Finding the path with the least overall travel time, considering delays.