ERNESTO MARTINS'
Personal Home Page



QUESTIONS FROM OLD EXAMINATIONS


About Optimal Path Problems

  1. Let be a given network, where is the set of nodes and the set of arcs. Let s be a given node of and let cij be a given real number associated with each arc (i,j). For any cycle C in the C cost c(C) is the sum of the cij real values associated with the arcs of C. Assume the non existence of cycles with negative cost and describe an algorithm to determine a cycle which minimize c(C) over C*, the set of cycles in such that s is one of its nodes.
  2. Describe the shortest path problem and the maximal capacity path problem.
  3. Let be a given network, and let s and t be two distinct nodes of . Let us assume the existence of at least one path from s to i and from i to t, for any node i different from s and t. Prove that the shortest path (from s to t) problem satisfy the Principle of Optimality if and only if there are no negative cycles in .
  4. Describe the minimal cost-time ratio path problem and show, with an example, that it can not be solved by labeling algorithms.
  5. Describe an algorithm to determine the maximal capacity path in the set of the shortest paths.
  6. Describe an algorithm to determine the shortest path in the set of the maximal capacity paths.
  7. Describe an algorithm to determine the shortest path between a given pair of nodes of a given network, with the minimal number of arcs.
    Note: The efficiency of the algorithm will be considered in the classification.
  8. Describe an algorithm to determine a path between a given pair of nodes of a given network with minimal number of arcs.
    Note: The efficiency of the algorithm will be considered in the classification.
  9. Let be an acyclic network such that ={1,...,n} and (i,j) is an arc if and only if i<j.
    1. Describe an algorithm to determine the shortest tree rooted at node 1, i.e., the tree of the shortest paths from node 1 to each node {2,...,n}.
    2. Describe an algorithm to determine the shortest tree rooted at node n, i.e., the tree of the shortest paths from each node {1,...,n-1} to node n.
  10. Let denote the shortest distance from a given node s to a node i.
    Prove that holds for any arc (i,j), where denotes the distance assigned to arc (i,j).
  11. Describe the adressed calculation sort form of the label seting algorithm for the maximal capacity path problem.

About Maximal Flow - Minimal Cut Problem

  1. Let be given network and s and t two given different nodes of and let be a minimal cut for s and t. Prove that is a minimal cut for and for all and
  2. Let be given network and s and t two given different nodes of and let be a minimal cut for s and t. Denoting by and the amount of flow in arc (i,j) and the capacity of arc (i,j) respectively, prove that = holds for any arc (i,j) of .
  3. Let be given network and s and t two given different nodes of and let be a minimal cut for s and t. Denoting by the amount of flow in arc (i,j), prove that holds for any arc (i,j) of .



    PAGE OF CONTENTS


    Optimal Path Problem Web Page


    BACK MATH'S DEPARTMENT