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
You must be logged in to post a comment.
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}
You must be logged in to post a comment.
You must be logged in to post a comment.
- 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
You must be logged in to post a comment.
You must be logged in to post a comment.
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.
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : D
- Explanation : For krushkal’s algorithm time complexity is O (log V) ∵ E → edges ∵ V → ventices So O (m log n)
You must be logged in to post a comment.
You must be logged in to post a comment.
You must be logged in to post a comment.