Hi, you are rightm but I am not the one who is saying that it is max flow. I am telling the same as you but in different way, the thread author is mistaken.
Can you provide some more ideas? I have no idea that i can prove. 2009/9/30 Prabhu Hari Dhanapal <[email protected]> > @ Miroslav - > > I think you are mistaken, the max flow does return exactly wht you are > looking for.The max flow over a path is nothing but its maximum bottle > neck. A path having 100 edges would not mean than 100 beads can be > pushed into it. Its just like water flowing in pipes .. the flow of > water is constricted by the pipe of minimum diameter. > > Hope that helps :) > > > On Wed, Sep 30, 2009 at 9:17 AM, sharad kumar <[email protected]>wrote: > >> ya something like finding different augmenting paths caluclating the max >> flow.pls refer coreman..... >> >> On Wed, Sep 30, 2009 at 1:36 PM, Prabhu Hari Dhanapal < >> [email protected]> wrote: >> >>> This is something like a "Flow Network Problem" . >>> >>> In the problem , you are just required to push max number of beads to >>> the receiver - which is the same as Max flow >>> >>> The attached file explains some concepts that might help you solve this >>> . >>> Max flow - min cut theorem , the ford fulkerson algorithm and others >>> ... >>> >>> >>> >>> >>> On Wed, Sep 30, 2009 at 3:46 AM, Miroslav Balaz <[email protected] >>> > wrote: >>> >>>> So at each step you can move any number of beads form some betwwen some >>>> pairs (in particular more than one) of adjecent vertices? >>>> >>>> It seems to be complicated problem. >>>> IMHO it is about some routing strategy than graph flow. >>>> If you do reduction to edge capacit, than the maximum flow and longest >>>> path on the flow will give you an upperbound (longest path+roof(N/max >>>> flow)-1) >>>> >>>> 2009/9/19 MrM <[email protected]> >>>> >>>> >>>>> there is a graph, consisting of N Vertices and some Edges ! >>>>> each Vertex has a Capacity(for storing Beads), and Capacity of 1st and >>>>> N-th Vertex is infinite ! >>>>> there are M Beads in the first Vertex, and we want to move this M >>>>> Beads to the N-th Vertex with the minimum number of steps ! >>>>> in each step, we can move some Beads from i-th Vertex to j-th Vertex >>>>> if and only if there exists an Edge between i-th and j-th Vertex ! >>>>> the number of Beads at each Vertex cannot exceed its Capacity ! >>>>> find the minimum number of required steps ! >>>>> inputs : >>>>> 1. N 2. adjacency matrix 3. capacity of Vertices [2 ... N-1] >>>>> 4. M >>>>> >>>>> Example : >>>>> N = 5, >>>>> adjacency matrix : >>>>> 0 1 1 0 0 >>>>> 1 0 0 1 0 >>>>> 1 0 0 1 0 >>>>> 0 1 1 0 1 >>>>> 0 0 0 1 0 >>>>> capacities : >>>>> 2-> 2, 3-> 2, 4-> 3 >>>>> M = 10 >>>>> Result for example : 6 >>>>> >>>>> i will appreciate anyone who write something like Psudo-Code for this >>>>> problem ! >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> -- >>> Hari >>> >>> >>> >>> >> >> >> > > > -- > Hari > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
