0
$\begingroup$

I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution.

The text is:

You are the owner of a large chain of franchise shops, and you would like to expand to a new city. The blocks in your city make an $n ×n$ grid. However, although your products are awesome and in high demand, the city will not allow you to open a shop in each block. Instead, for every row of blocks i, you are are given a number $r_i$ that limits the maximum number of shops opened there - and for every column j, there also is a maximum number $c_j$ .

a) Find the maximum number of franchise shops you can legally open in the city. To do so, model the problem as a flow network. Then, describe how to get the right answer using Ford-Fulkerson, and prove the correctness of your construction.

How can I construct the digraph from the $n ×n$ grid ? I think the blocks can be represented in this way grid Should I assume an initial orientation on the grid?

Image taken by https://www.chegg.com/homework-help/questions-and-answers/n-x-n-grid-graphs-defined-drawing-nx-n-grid-vertices-connecting-adjacent-vertices-drawn-g3-q30726135

Improve this question
$\endgroup$
1
2
$\begingroup$

Assume an $n\times n$ grid. I'd build a network as follows. A source on the left with $n$ arcs going to $n$ nodes each representing a row of the grid. Call these $n$ nodes $R_1, R_2...R_n$. The flow capacity on the $i^{th}$ arc (from source to $R_i$) is $r_i$. Do something similar at the sink. Have arcs arriving there from nodes $C_1,C_2..C_n$ with capacity $c_i$. Then connect each $R_i$ to $C_j$ with an arc of capacity 1. Maximize the flow. The arcs $R_i-C_j$ chosen to have a flow in an optimal solution will tell you to place a franchise at grid point $i,j$.

Improve this answer
$\endgroup$
11
  • $\begingroup$ But in this way the minimum capacity along a path is always 1 and the flow is the same for every paths, am I wrong? Thank you for your time. $\endgroup$
    – th3gr3yman
    Nov 23 at 11:14
  • $\begingroup$ Well there are $n^2$ paths. That is, every node of the grid corresponds to a path. So you can only pick them all if your $r_i$ and $c_i$ are at least $n$. But for the general case, the flows will be maximal subject to those constraints and will pick out the max number of grid points that are feasible. $\endgroup$
    – TickaJules
    Nov 23 at 14:02
  • $\begingroup$ Is this correct for 3x3 ? drive.google.com/file/d/1RIRf6xiK9o0u8Y3tVdKaa1kwyKuqNSUv/… $\endgroup$
    – th3gr3yman
    Nov 23 at 14:29
  • $\begingroup$ Assuming a full 3x3 grid, you're missing 6 arcs in the middle ($R_1$ to $C_2$, $R_1$ to $C_3$, $R_2$ to $C_1$.......) So each point of the grid (say in row $i$ and column $j$) corresponds to an arc from $R_i$ to $C_j$. $\endgroup$
    – TickaJules
    Nov 23 at 14:33
  • $\begingroup$ Ok thank you but I don't get the capacity of 1. For example: in the path S-->$R_1$-->$C_1$-->T the minimum capacity is 1 so for every arcs flows exactly 1 (1/$r_1$,1,1/$c_1$) and so on for the others. $\endgroup$
    – th3gr3yman
    Nov 23 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.