Exercise “Applying Maximum Flow”
Task 1
Like in the “Cities by Train” exercise, one could split each node into an and node, with an edge with capacity .
All edges went to need to go to , and all edges that went from need to go from now, e.g instead of
graph LR; w --> u --> v
the graph looks like this:
graph LR subgraph w w_in --> w_out end subgraph u u_in --> u_out end subgraph v v_in --> v_out end w_out --> u_in u_out --> v_in
Task 2
The graph will consist of the following nodes:
- a source node
- a sink node
- a vertex node () for each employee with
- capacity
- a “double” vertex node () for each truck with
- capacity 1 for the driver slot
- capacity 1 for the collector slot
These will be the other edges (every one with capacity ):
- for each employee
- from each driver to every truck the driver can operate
- from each collector to every truck he can operate
- to connect every truck to the sink (with capacity 2)
Each employee can only be assigned once, because of the capacity of the vertex. The trucks also can only be operated by two persons.
The only problem, which I don’t know how to solve, is how to prevent the assignment of a single person to a truck.