Exercise "Applying Maximum Flow"

Task 1

Like in the "Cities by Train" exercise, one could split each node $u$ into an $u_{in}$ and $u_{out}$ node, with an edge $(u_{in},u_{out})$ with capacity $c(u)$.

All edges went to $u$ need to go to $u_{in}$, and all edges that went from $u$ need to go from $u_{out}$ 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 $G=(V,E)$ will consist of the following nodes:

• a source node $s$
• a sink node $s^{\prime }$
• a vertex node $e$ ($e_{in},e_{out}$) for each employee with
  • $e_{in}\to e_{out}$ capacity $1$
• a "double" vertex node $t$ ($t_d,t_c,t^{\prime }$) for each truck with
  • $t_d\to t^{\prime }$ capacity 1 for the driver slot
  • $t_c\to t^{\prime }$ capacity 1 for the collector slot

These will be the other edges (every one with capacity $1$):

• $s\to e_{in}$ for each employee
• $e_{out}\to t_d$ from each driver to every truck the driver can operate
• $e_{out}\to t_c$ from each collector to every truck he can operate
• $t^{\prime }\to s^{\prime }$ 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.