Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
Yes, different starting vertices may lead to different MSTs
No, the MST is unique for a given 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?
Community Detection
Shortest Path
Minimum Spanning Tree
Graph Coloring
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?
Dijkstra's Algorithm
Breadth-First Search (BFS)
Bellman-Ford Algorithm
Depth-First Search (DFS)
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
0
1
-1
Infinity
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
You are tasked with designing a system to schedule tasks with dependencies between them. What graph data structure would be most appropriate to represent these dependencies?
Directed Acyclic Graph (DAG)
Bipartite Graph
Complete Graph
Undirected Graph
Why are negative weights problematic for some shortest path algorithms?
All of the above
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
These algorithms assume that adding an edge to a path always increases its total weight.
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
What is the primary distinction between an unweighted graph and a weighted graph?
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.
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.
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Floyd-Warshall Algorithm
Kruskal's 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
Finding all edges connected to a specific vertex
Determining the degree of a vertex