My problem is:
There is an input list of 5 children and a list of chores that they would prefer to complete.
Let days be equal to 10, and for each day, there are 2 chores that they must complete.
There are restraints where each child must complete at least 3 chores and at most 5 chores, each chore must only be completed by 1 child, and no child is allowed to complete both chores in a day.
My goal is to find an allocation where each child is allocated the chores where this allocation satisfies the restraints above.
I understand that I can create a bipartite graph with vertices ui corresponding to children, and vj corresponding to chores. Then, I can draw edges from vertices ui to vj corresponding to each child's preference to each chore. I understand these edges will have a capacity of one (as each chore can only be completed once). Furthermore, I know to add a start vertex, with an edge from each vertex ui to the start vertex, and also to add a sink vertex, with an edge from each vertex vj to the sink vertex.
However, I am confused about how to implement the restraint where each child must complete at least 3 chores and at most 5 chores. Where does this restraint fit on this bipartite graph?
I would appreciate any help! Thanks!
There is a total of 20 tasks to complete (2 each day). Each child must complete 3 of those 20, and up to 5. That means that when each child has done his minimum of tasks, 5 remains to be done.
rt (remaining tasks"), with an edge from the source to rt with a capacity of 5, and some edge from rt to each child, with a capacity of 2 (each child can only complete 2 of the 5 remaining tasks)With this setup, there is a total capacity of 20, so if all 20 tasks are completed, it is forced that each child do 3 of them.