Homework 10 Fundamental Algorithms

A.Paz due Apr 19-th

  1. Ex 4.2.a (p 406) in the book

  2. Ex.4.16 (p 407) in the book

  3. 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?

  4. 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.