07-18-2017, 10:00 AM
CS502 Design and Analysis of Algorithms
Assignment 3 Solution - Spring 2017
Question. 1 Consider the following Directed Acyclic Graph.
![[Image: dvLRV2c.jpg]](https://i.imgur.com/dvLRV2c.jpg)
Note: Write a list of vertices only, no need to show the intermediate steps.
Answer: 1, 3, 4, 8
Question. 2
Two directed graphs are given below Graph (A) & Graph (B), You are required to answer the following questions
1. Is “Graph (A)” a connected graph? State Yes / No with valid reason
2. Is “Graph (B)” contains a Hamiltonian cycle? State Yes / No with valid reason
![[Image: w3zvPmJ.png]](https://i.imgur.com/w3zvPmJ.png)
![[Image: yAxKbmk.png]](https://i.imgur.com/yAxKbmk.png)
Graph (A) Graph (B)
Answer:
Assignment 3 Solution - Spring 2017
Question. 1 Consider the following Directed Acyclic Graph.
Run BFS on this graph by taking node ‘1’ as source node and list the vertices in order while running BFS.
Answer: 1, 3, 4, 8
Question. 2
Two directed graphs are given below Graph (A) & Graph (B), You are required to answer the following questions
1. Is “Graph (A)” a connected graph? State Yes / No with valid reason
2. Is “Graph (B)” contains a Hamiltonian cycle? State Yes / No with valid reason
Graph (A) Graph (B)
Answer:
- No, because 1 is not connected with 5 directly and also 5 is not connected with 3 directly.
- Yes, 1, 2, 3, 4, 1 creates a Hamiltonian cycle.