This problem can easily be modelled using graph theory, and it was proven that the above situation really was an example of a more general result, called the the max-flow,min-cut theorem.
To describe how graph theory was used to formalize the train-model, I described a network as follows:
A simple directed graph (i.e. at most one arrow going from one vertex to another), together with two explicit vertices: the source \s\) and sink \(t\) and a capcity \(c:E(G)\longrightarrow \mathbb{R}_{\ge 0}\)
To make things easier, I extended the capacity to \(V\times V\) by defining it as 0 if there is no edge from the first to the second vertex, and denote \(u\rightarrow v\), the edge from \(u\) to \(v\).
The idea of exactly how much goods can be carried accros the network is in turn formalized in the form of a network:
A flow is a function \(E(G)\longrightarrow \mathbb{R}_{\ge 0}\) such that
- the flow is smaller than the capacity along any edge: \(f(u\rightarrow v)\le c(u\rightarrow v)\)
- for each vertex \(v \neq s,t\) the net flow satisfies \[\partial f(v)=f^+(v)-f^-(v)=\sum_{u \in V} f(v\rightarrow u)-\sum_{w \in V} f(w\rightarrow v )=0 \]
An example of a flow is given below:
To model the idea of disrupting the network, we make the following:
An \(S,T\)-cut of a network is a partition \(V=S\coprod T\) such that \(s \in S,t \in T\)
Below is an example of such a cut:
What we are interested in is how tow specific numbers relate
The value if a flow is given by \(\vert f\vert =\partial f(s)\), we say a flow is maximal if for any other flow \(\vert f'vert \) on \(G \), we have\(\vert f \vert \\ge \vert f'\vert \).
The capacity of a cut \((S,T)\) is the number \(\vert \vert (S,T)\vert\vert =\sum_{u\in S,v \in T} c(u\rightarrow v)\). It is minimal if for any other cut \(S,T\), we have \(\vert \vert (S,T)\vert \ ert \le \vert \vert (S,,T,\vert \vert)\)
In the above example, we have \(10=\vert f\vert \le \vert \vert (S,T)\vert \vert =10\)
One very profound theorem iin the theory of networks, (which the US air force managed to check ad hoc) is the following:
For any network, the value of a maximal flow equals the capacity of a minimal cut.
For example, the network above predicts that the maximal flow or capacity of the minimal cut, implying this number must be somewhere between 10 and 15...
This theorem is rather profound and has some powerfu applications: let's say you want to prove a statement of the following form:
There exists a set of \(k\) edges with a certain property \(P\) as long as any set of vertices with a certain property \(Q\) is bounded by \(k\)
You would prove this as follows
- Find a clever way to turn the graph into a network
- a flow having value \(k\) should then correspond the existence of a set of \(k\) edges with property \(P\)
- A set of \(k\) vertices having property \(Q\) in turn should correspond to a cut of capacity \(k\)
- The theorem now allows you to conclude that the there exists a flow of value \(k\) rprovded any cut has capacity at least \(k\)
- Retranslating, you have proven the result
In week 5, we will see two important results which are easily proven using this method