@ 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 -~----------~----~----~----~------~----~------~--~---
