diff -r 58357e986a08 -r 6c408d864fa1 doc/groups.dox --- a/doc/groups.dox Sun Apr 26 16:36:23 2009 +0100 +++ b/doc/groups.dox Wed Apr 29 03:15:24 2009 +0200 @@ -352,17 +352,17 @@ minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs. -Formally, let \f$G=(V,A)\f$ be a digraph, -\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and +Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, +\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and upper bounds for the flow values on the arcs, for which -\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. -\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow -on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the +\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, +\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow +on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the signed supply values of the nodes. If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with \f$-sup(u)\f$ demand. -A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution of the following optimization problem. \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] @@ -404,7 +404,7 @@ The dual solution of the minimum cost flow problem is represented by node potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. -An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem +An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ node potentials the following \e complementary \e slackness optimality conditions hold. @@ -413,15 +413,15 @@ - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; - if \f$lower(uv)