01-28-2013, 03:15 PM
CS502 Fundamentals of Algorithms Assignment No .4 Solution Fall Semester 2013 Due Date 01/Feb/2013
Assignment No. 04
Semester: Fall 2012
Fundamentals of Algorithm-CS502
Total Marks: 20
Due Date: 01/Feb/2013
Instructions:
Please read the following instructions carefully before submitting assignment:
You will submit your assignment before or on due date on VU-LMS.
Assignment should be completed by your own efforts it should not be copied from internet, handouts or books.
You should submit your .doc File via assignment interface at VU-LMS.
Assignment sent via Email will not be replied and accepted/graded in any case.
If the submitted assignment does not open or file is corrupt, it will not be graded.
You will submit solution only in document (.doc or .docx) File.
Objectives:
To understand the real applications Graph.
For any query about the assignment, contact at
Assignment Questions
Question1: Marks 10
A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.
a. Prove that in a breadth-first search of an undirected graph, the following properties hold:
1. There are no back edges and no forward edges.
2. For each tree edge (u, v), we have d[v] = d[u] + 1.
3. For each cross edge (u, v), we have d[v] = d[u] or d[v] = d[u] + 1.
b. Prove that in a breadth-first search of a directed graph, the following properties hold:
1. There are no forward edges.
2. For each tree edge (u, v), we have d[v] = d[u] + 1.
3. For each cross edge (u, v), we have d[v] ≤ d[u] + 1.
4. For each back edge (u, v), we have 0 ≤ d[v] ≤ d[u].
Question 2: Marks 5
Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.
Question 3: Marks 5
Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, then any depth-first search must result in d[v] ≤ f[u].
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]
