GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test | Set 1

Consider a flow network with source s and sink t. Cut (S, T) has $S = {s, v1}$ and $T = {v2, t}$. Directed edges and capacities: (s, v1)=10, (s, v2)=5, (v1, v2)=15, (v1, t)=10, (v2, v1)=3, (v2, t)=20. What is the capacity of cut (S, T)?

In a complete undirected graph $K_{5}$ with 5 vertices, what is the size of the maximum Clique?

In a graph $G = (V, E)$ with $V = 20 vertices$, if the size of the Maximum Independent Set is 12, what is the size of the Minimum Vertex Cover?

If a tree has $V = 15 vertices, how many edges does it contain$?

A BFS is run from vertex s in an unweighted graph. If a vertex v is first discovered from u, then which statement is necessarily true?