proofs

Question 1

what is white path theorem

Answer 1

In a depth-first forest of a (directed or undirected) graph G D .V; E/, vertex is
a descendant of vertex u if and only if at the time u:d that the search discovers u,
there is a path from u to consisting entirely of white vertices

Question 2

proof for largest set of non-overlapping actvties

Answer 2

1.) Let Aik=Aij - Sik
Let Akj=Aij-Skj
Then |Aij|=|Aik|+|Akj|+1
2.) Use copy and paste argument to prove Ski is optiomal , proof for Sik is symmetric
3.) Suppose A’kj is a set of mutually compatible sources i Ski, where |A’kj| > \Akj|. Then use A’kj when solving the subproblem for Sij. The size of the resulting set of mutually compatible activues would be |Aik|+|A’kj|+1 >|Aik|+|Akj|+1 = |A|. Contratdicts assumption that Aij is optimal.

Question 3

prove greedy choice is correct

Answer 3

Theorem
If Sk is nonempty and am has the earliest finish time in Sk, then am is included in some optimal solution.

Proof
Let Ak be an optimal solution to Sk, and let aj, have the earliest finish time of any activity in Ak. If aj = am, done. Otherwise, let A’k, = Ak- (aj) U (au) be Ak but with am, substituted for aj.

Claim: Activities in A’k are disjoint.

Proof: Activities in Ag are disjoint, ai is the first activity in Ak to finish, and fm ≤ fj.

Since |A’k| = |Ak|, conclude that A’k is an optimal solution to Sk, and it includes a_m

Question 4

toplologcial sort correctness

Answer 4

Suppose the DFS is run on G = (V, E) to determine finishing times for its
vertices.
Just need to show if (u, v) € E, then v.f < u.f.
When we explore (u, v), what are the colors of u and v?
- u is gray.
- Is v gray, too?
· No, because then v would be ancestor of u:
(u, v) is a back edge.
contradiction of previous lemma (dag has no back edges).
- Is v white?
· Then becomes descendant of u.
. By parenthesis theorem, u.d < v.d < v.f < u.f.
- Is v black?
· Then v is already finished.
· Since we’re exploring (u, v), we have not yet finished u.
. Therefore, v.f < u.f.

Question 5

prove Gscc is a dag

Answer 5

Lemma. GsCC is a dag.
More formally, let C and C’ be distinct SCC’s in G, let u, v EC, u’, v’ € C’, and
suppose there is a path u - u’ in G. Then there cannot also be a path v’ - v in
G.

Component Graph

Proof.
· Suppose there is a path v’ v in G.
. Then there are paths u - u’ - v’ and v’ -* V - u in G.
· Therefore, u and v’ are reachable from each other, so they are not in
separate SCC’s.

Question 6

prove a subpath of a shortest path is a shortest path

Answer 6

look in book

Question 7

Run Dijkstra’s algorithm on the directed graph of Figure 24.2, first using vertex s
as the source and then using vertex ´ as the source. In the style of Figure 24.6,
show the d and values and the vertices in set S after each iteration of the while
loop

Question 8

pusedocode for dikstrja

Answer 8

DIJKSTRA.G; w; s/
1 INITIALIZE-SINGLE-SOURCE.G; s/
2 S D ;
3 Q D G:V
4 while Q ¤ ;
5 u D EXTRACT-MIN.Q/
6 S D S [ fug
7 for each vertex 2 G:AdjŒu
8 RELAX.u; ; w