CS161_HW4.pdf

Problem 1
a) Answer :
In above graph if we delete the edge in to the order of d,e,f we can make bipartite graph here no of deleted edge is 3 but we can achieve it by deleting e,f here no of deleted edge is 2
b) Answer:
In the above graph if we follow the algo rule it is detected as bipartite graph but vertex E has cyclic dependency.
C) Answer:
Here we have to find the minimum weighted path between a and j. By the rule we have to traverse b after a (a,b,f,j) which is not the right path.
D)Answer:
In the above graph if we find the shortest graph by dijkstra path will be a,b,c,d and if we delete the edge it becomes the incomplete graph and we will not achieve any closed cycle.
Problem 2:
a) Answer:
b) Answer:
i) True
ii) False
iii) True
iv) True
v) False
vi) True
c) Answer: If we put k = n-1 then in the graph n-1 element will be added in incremental order with one vertex and we can get the sorted list by applying DFS. but only when we select the vertex which has the minimum value at the very first time.
I think there is no such...