Which of the following statements regarding REDUCTION A <=_p B are CORRECT?
Statements 1, 2, and 3 are correct. If A reduces to B and B is in P, then A is in P; if A is NP-hard, B must be NP-hard; and if B is in NP, then A is also in NP because the reduction plus B verification gives a polynomial verifier.
Which of the following statements regarding Graph Algorithms are CORRECT?
BFS uses Queue, DFS uses Stack, Dijkstra requires non-negative weights. Bellman-Ford CAN detect negative weight cycles on V-th iteration.
A directed graph $G = (V, E) has V = 10 vertices$. What is the maximum number of edges G can have such that G remains a Directed Acyclic Graph (DAG)?
In a DAG with 10 vertices v1, v2, ..., v10, edges can only go from vi to vj where i < j. Maximum edges = 10 * 9 / 2 = 45.
In a simple undirected graph with $V = 6 vertices, what$ is the maximum number of edges the graph can have without containing a cycle (i.e. maximum edges in a forest)?
A forest (acyclic undirected graph) with V vertices and k components has V - k edges. Maximum edges occur when $k = 1 (a tree), giving V - 1 = 6 - 1 = 5 edges$.
How many strongly connected components exist in a Directed Acyclic Graph (DAG) with $V = 8 vertices$?
In a DAG, there are no directed cycles of length >= 2. Every individual vertex forms its own strongly connected component. Total SCCs = $V = 8$.