Demonstration Exercise 6

In this demonstration exercise, you'll encounter yet another area of graph theory, flow networks, and gain experience in exploring mathematical definitions with examples.

Problem 1: Exploring Flow Networks

An important specialization of graphs are flow networks:

The prototypical real-life example of a flow network is a network of pipes that carry water. Each edge corresponds to a pipe and the pipes are connected at joints, represented by vertices. Flow in this context is literal water flow where the capacity represents how much water each pipe can hold.

In this formulation, we represent the flow through a network as a separate flow function:

Finally, it is common when discussing flow networks to distinguish two nodes, a source and sink node, $s,t\in V$, respectively. We think of them as the entry and exit points of flow in our network, whatever that means for the domain in question. We then define the flow value of the network as the flow going into the sink (and thus, out of the network!):

Give two additional real-world examples of flow networks, explicitly describing what each of the components of the network:

• Vertices $V$,
• Edges $E$,
• The capacity function $c$,
• The flow function $f$,
• The source $s$ and sink $t$, and
• The flow value $|f|$.

Represent in each example.

Problem 2: Feasible Flows

Next, come up with an artificial example of a complete flow network with at least five vertices. Make sure to formally specify all the components of the network!

Note that to avoid cluttering our definitions, we make several assumptions about the shape of a flow network:

• We assume (but do not specify) symmetric edges, i.e., if $(u,v)\in E$ then $(v,u)\in E$.
• If an edge $(u,v)\notin E$ then we assume it is present (again, with explicit specifying this fact). However, we also assume that $f(uv)=c(uv)=0$.

Using your artificial example, explore these three critical conditions under which a flow function is considered valid or feasible. All three conditions are specified in terms of a flow network with components as described above:

If your artificial example does not meet these conditions, change it so it does!

For each condition:

• Describe in a sentence or two what the condition is enforcing about flow in a flow network.
• For each of your real-world examples from the previous part, describe what the condition means in the concrete context of the example. (Note: the real-world instantiation of each condition may be quite similar to your general description. That is fine!)

Problem 3: The max flow-min cut theorem

Recall from the reading that a cut of a graph is a partition of the graph into two sets of vertices:

In the context of flow networks, we define a $s$-$t$ cut to be a cut where $s$ is in one partition and $t$ is in the other.

A critical theorem of flow networks is the max-flow min-cut theorem:

The capacity of a $s$-$t$ cut is simply the sum of the capacities the edges that connect vertices across the two partitions induced by the cut.

1. Create an artificial example of a flow network and show that this theorem holds of your example. Make sure to identify precisely:
   • The feasible flow function that produces the maximum flow value.
   • The $s$-$t$ cut that produces the minimum capacity. You may either use your artificial example from the previous section or a new example.
2. Go back to your real-world examples and for each example, describe in a sentence or two what the max-flow min-cut theorem means for that example's particular context. Try to avoid using the terms "flow" and "cut" in your descriptions.
3. Finally, in a few sentences, describe why this theorem holds. You do not need to prove this claim formally, but your explanation should appeal directly to nature of a cut and what it does to the capacity and/or flow of the network.