I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize this lunch with two tables of ten people with the following constraints :

  • At least one member of each four department has to be on each table
  • At most three people of each department can sit together at a table
  • At least three people of each Executive management department have to be at the table $1$.

I did the following graph :

enter image description here

And applied Ford-Fulkerson (I'm not sure on how to apply it, the itreation are in parenthesis $(number \ of \ the \ iteration)$ ):

enter image description here

The thing is that I'm not able to let everybody sit ... I have only 8 people from society 2. Do I have too much constraints or did I did a mistake ?

What would be the minimum cut ? Is there a minimum cut if I don't have a maximal stream ? Would it verify the Ford-Fulkerson theorem ?

  • $\begingroup$ Do you know that everybody can be seated? What's the idea behind your construction? $\endgroup$ – Raphael Apr 14 '17 at 11:47
  • $\begingroup$ @Raphael No I'm not sure ! But as far as I have two tables of ten places for twenty people, everybody can be seated. The thing is that I don't know if I can apply the constraints given by my boss. The idea was to find it thanks to my computer science knowledge. The issue is that I don't know if I used and applied them (the Ford-Flukerson algorithm) well ! The purpose is to have a better understanding of those concepts. $\endgroup$ – Revolucion for Monica Apr 14 '17 at 12:16
  • $\begingroup$ Okay, so the algorithm finding seats for only 18 people may be the correct answer! $\endgroup$ – Raphael Apr 14 '17 at 15:08

Your Answer

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

Browse other questions tagged or ask your own question.