- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- A simple acyclic path between source and...

Q. |
## A simple acyclic path between source and sink which pass through only positive weighted edges is called? |

A. | augmenting path |

B. | critical path |

C. | residual path |

D. | maximum path |

Answer» A. augmenting path | |

Explanation: augmenting path between source and sink is a simple path without cycles. path consisting of zero slack edges is called critical path. |

View all MCQs in:
Design and Analysis of Algorithms

- A network can have only one source and one sink.
- Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.
- A matching M is maximal if and only if there exists no augmenting path with respect to M.
- There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
- Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
- Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
- A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
- A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
- How many edges does a n vertex triangle free graph contains?
- is a matching with the largest number of edges.

Login to Continue

It will take less than 2 minutes

Report MCQ