文档介绍：Algorithms plexity
Herbert S. Wilf
University of Pennsylvania
Philadelphia, PA 19104-6395
Copyright Notice
Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose, multiple
copies may be made for classes, etc. Charges, if any, for reproduced copies must be just enough to recover
reasonable costs of reproduction. Reproduction mercial purposes is prohibited. This cover page must
be included in all distributed copies.
Edition, Summer, 1994
This edition of Algorithms plexity is the
le “pub/wilf/” at the anonymous ftp site
“”. It may be taken at no charge by all interested persons. Comments and corrections
are e, and should be sent to ******@
Chapter 3: work Flow Problem
Introduction
work
ow problem is an example of a beautiful theoretical subject that has many important
applications. It also has generated algorithmic questions that have been in a state of extremely rapid
development in the past 20 years. Altogether, the fastest algorithms that are now known for the problem
are much faster, and some are much simpler, than the ones that were in use a short time ago, but it is still
unclear how close to the ‘ultimate’ algorithm we are.
De
nition. work is an edge-capacitated directed graph, with two distinguished vertices called the
source and the sink.
To repeat that, this time a little more slowly, suppose
rst that we are given a directed graph (digraph)
G. That is, we are given a set of vertices, and a set of ordered pairs of these vertices, these pairs being
the edges of the digraph. It is perfectly OK to have both an edge from u to v andanedgefromvto u,or
both, or neither, for all u =6 (u, u) directed from vertex v to vertex
w,thenvis the initial vertex of e and w is the terminal vertex of e. We may then write v = Init(e)and
w=Term(e).
Next, in work there is associated with each directed edge e of the digraph a posi