Algorithms - Algorithm Design Techniques
- Option : A
- Explanation :
If we find shortestt path fram C to D then it is
13 currently. So we can use maximum 12 value
for x
so x = 12
7. The number of articulation points of the following graph is
- Option : D
- Explanation :
there are 3 aoticulation point in the given graph
which break the graph in to component.
{2, 3, 5}
- Option : B
- Explanation : A graph is said to be strongly connected if there is path from each vertex of graph to every other vertex means every vertex is reachable from every other vertex. The strongly connected component is always maximal that is if A is strongly connected component there should not exist another strongly connected component which contains A
9. Consider the directed graph given below.
Which one of the following is TRUE?
- Option : C
- Explanation : Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Topological ordering is possible iff graph has no directed cycles. (A) As the given graph doesn’t contain any directed cycles, it has at least one topological ordering. So option (A) is false (B) PQRS cannot be topological ordering because S should come before R in the ordering as there is a directed edge from S to R. SRQP cannot be topological ordering, because P should come before Q in the ordering as there is a directed edge from P to Q (C) PSRQ and SPRQ are topological orderings as both of then satisfy the above mentioned topological ordering conditions. (D) PSRQ is not the only one topological ordering as SPRQ is other possibility.
- Option : D
- Explanation : For krushkal’s algorithm time complexity is O (log V) ∵ E → edges ∵ V → ventices So O (m log n)
