Which of the following graph traversals visits vertices level-by-level in order of their distance from the source?
BFS computes unweighted shortest path distances by exploring vertices layer by layer in increasing distance from source.
If all edge weights in a graph are equal to a constant positive integer C, which algorithm finds the shortest path from a source in O(V + E) time?
When every edge has the same positive weight C, minimizing total path weight is equivalent to minimizing the number of edges. BFS finds minimum-edge paths in O(V + E).
What is the sum of degrees of all vertices in a simple graph with 15 edges?
Sum of degrees = 2 * |E| = 2 * 15 = 30.
If a simple graph has 8 vertices and 3 connected components, what is the MAXIMUM possible number of edges it can contain?
Formula for max edges in a graph with V vertices and k components = (V - k)(V - k + 1)/2 = (8 - 3)(8 - 3 + 1)/2 = 5 * 6 / 2 = 15.
What is the maximum number of edges in a simple acyclic undirected graph (Forest) with V vertices and C connected components?
Each tree component with $v_{i}$ vertices has $v_{i}$ - 1 edges. Summing over C components gives total edges = V - C.