|
|
|
QUESTIONS FROM OLD EXAMINATIONS
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.
Describe the shortest path problem and the maximal capacity path problem.
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
.
Describe the minimal cost-time ratio path problem and show, with an
example, that it can not be solved by labeling algorithms.
Describe an algorithm to determine the maximal capacity path in the set of
the shortest paths.
Describe an algorithm to determine the shortest path in the set of
the maximal capacity paths.
Describe an algorithm to determine the shortest path between a given pair of
nodes of a given network, with the minimal number of arcs.
be an acyclic network such that
={1,...,n}
and (i,j) is an arc if and only if i<j.
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}.
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.
denote the shortest distance from a given node
s to a node i.
holds for any arc (i,j), where
denotes the distance assigned to arc (i,j).
Describe the adressed calculation sort form of the label seting algorithm
for the maximal capacity path problem.
About Maximal Flow - Minimal Cut Problem
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
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
.
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
.
