Network Flow
- From: "rambotrout" <rambotrout@xxxxxxxxx>
- Date: 14 Apr 2005 16:33:31 -0700
I was posed with an interesting question for which I have no answer
yet. I post it here so that someone can have a try at it.
There is a directed, uncapacitated network with several source-sink
pairs (source and sink are distinct nodes). Each source-sink pair has
at least 2 simple paths (non-cyclic). Each flow through a path can take
positive, zero or negative value. We start with a network without any
flow (all paths carrying zero flow). Then arbitrary set flow on each
path (positive, zero or negative) such that the total path flows for
each source-sink pair sum up to zero. Assuming that all flows on a link
are additive regardless of where they originated from (or where they
destined to), prove that the resulting network cannot have all its
links carrying either non-positive only or non-negative only flows. In
other words, they must be one of the followings:
1) a mixture of positive, negative, and zero.
2) a mixture of positive and negative.
3) all zeros.
Note that the network is composed of directed links; meaning that each
link carries flow one directional only. A negative total flow on a link
does not mean the flow flowing in the opposite direction. It just means
the link is *indebt of flow*.
I've figured out a clue to start with: Observing that all links
carrying only non-negative flows, we can deduce that this is possible
only if there is some external flow has been injected into the network.
.
- Prev by Date: Re: Computational Mathematics and Computer Science
- Next by Date: In want know about one algorithm (k-node) and how to converted distributed algorithm for link failure?.
- Previous by thread: finding a maximum in a matrix
- Next by thread: How to evaluate the hardness of a Multiobjective Optimization problem?
- Index(es):
Relevant Pages
|
