Week 2

In this third week of classses, we finished Konig's theorem and went on to introduce networks and what they can do for us.

I began by giving a picture summary of how you should remember the proof of Konig's theorem (see Week 2).

We then went on to introduce the next big theorem in the course: the min-cut/max-flow theorem for networks. To introduce this problem, I gave a little historic context
In the mid-50's two US air force researchers, Harris and Ross drew up a plan of the rail network linking the Soviet Union to its satelite countries (consisting of 44 major train hubs and 105 major train routes).
They were interested in figuring out how sophisticated thhis networkw was and if any vulnaribilities could be found and exploited.

Using trial and error, they figured out two key bits of information:
  • the total amount of goods that could be transported on the network
  • The minimal effort needed to disrupt the network, i.e. the lightest trains (in terms of goods they could carry) they needed to blow for the network to be disconnected.
  • 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
    1. the flow is smaller than the capacity along any edge: \(f(u\rightarrow v)\le c(u\rightarrow v)\)
    2. 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
    1. Find a clever way to turn the graph into a network
    2. a flow having value \(k\) should then correspond the existence of a set of \(k\) edges with property \(P\)
    3. A set of \(k\) vertices having property \(Q\) in turn should correspond to a cut of capacity \(k\)
    4. The theorem now allows you to conclude that the there exists a flow of value \(k\) rprovded any cut has capacity at least \(k\)
    5. Retranslating, you have proven the result
    In week 5, we will see two important results which are easily proven using this method