| Author |
Message |
bee
Joined: 29 Nov 2003
Posts: 126
Helped: 2
|
 17 Nov 2007 21:37 Max-flow min-cut??? |
|
|
|
Does anyone has idea abt "max-flow min-cut"?
Waiting
|
|
| Back to top |
|
 |
toshine
Joined: 04 Sep 2007
Posts: 7
Helped: 2
|
| 18 Nov 2007 14:32 Max-flow min-cut??? |
|
|
|
The max-flow min-cut theorem states that for a unicast transmission senario, that is only one source node and one receive node, the maximum flow from the source node to the receive node is equivalent to the (value of) min cut between the source node and the receive node.
In the above statements, the concept of min cut, or minimum cut, should be explained. Cut is a set of edges, and when you remove this set of edges the source node will be disconnected from the receive node. For every cut, there is an associated value which is the sum of the capacities of the edges in the cut. Obviously, minimum cut is a cut whose value is the smallest one. Sometimes, we also call the value of the minimum cut as minimum cut.
This theorem has been proved for more than half a century by several persons. With the advent of network coding theory, it appears very frequently.
|
|
| Back to top |
|
|
urwelcome
Joined: 12 Apr 2007
Posts: 75
Helped: 4
|
| 25 Nov 2007 0:44 Re: Max-flow min-cut??? |
|
|
|
Max-flow min-cut implies that maximum amount of flow is equal to the capacity of minimal cut.
cut-cut is partition of vertices of graph into two sets.
these vertices from two set are connected by edges (lines)
these edges has some weight (capacit)
there may be many many cuts like this in a large graph.
minimal cut-minimal cut is the one in which the lines or edges which are connecting two partition of a set have minimum capacity or weight as compared to all other cuts in graph.
so finally capacity is upper bounded by the weakest cut.
this forms max-flow min-cut
also refer to wikipedia
|
|
| Back to top |
|
|
mardani2
Joined: 18 Jul 2007
Posts: 31
Location: iran,tehran university
|
| 02 Dec 2007 15:40 Re: Max-flow min-cut??? |
|
|
|
Dear My friend
for more information you can refer to literatures about "capacity of the relay channels" or "network coding".
|
|
| Back to top |
|
|
