Homework 10 Fundamental Algorithms
A.Paz due Apr 19-th
- Ex 4.2.a (p 406) in the book
- Ex.4.16 (p 407) in the book
- G=(V,E) is a digraph with n vertices. A vertex s is called a "sink" if
for every vertex v which differs from s there is an edge (v,s) in E and
there are no edges (s,v) in E. G is given by it's adjacency MATRIX.
Provide an algorithm to determine whether G has a sink. Try to minimize
the complexity of your algorithm in terms of the number of entries in
the matrix that must be examined. What is the complexity of your algorithm?
- G=(V,E) is an undirected WEIGHTED graph. Let T be the shortest-paths tree
(definitions will be provided in class this Wednesday) rooted at a given
vertex v. Suppose now that all the weights in G are increased by a
constant number C (same constant for all edges). Is T still the shortest-
paths tree from v? If yes provide a proof, if no give a counterexample.