Consider a series of islands with bridges between them. A group of people are trying to move from island \(v_0\) to island \(v_5\text{.}\) Due to the length/width of the bridges, only but so many people can move between a pair of islands in a minute, and these are labeled. The bridges, represented by arrows below, also only allow movement in one direction.
If you could increase the capacity of a single bridge to increase the number of people who can travel to \(v_5\) in a minute, which would it be and by how much?
A directed graph or network is a pair \(D=(V, E)\) where \(V\) is a set of vertices and \(E\) is a set of ordered pairs of distinct elements of \(V\) called edges.
A network is capacitated if for each edge \((v_i, v_j)\in E\) we assign a nonnegative capacity \(c_{ij}\text{.}\) (If there is no edge from \(v_i\) to \(v_j\text{,}\) we may equivalently say that \(c_{ij}=0\text{.}\))
A flow assigned to a capacitated network is an assignment to each edge \((v_i, v_j)\in E\) a value \(x_{ij}\) such that \(0\leq x_{ij}\leq c_{ij}\text{.}\) (If there is no edge from \(v_i\) to \(v_j\text{,}\) what must \(x_{ij}\) be?)
Graph theory is a rich, complex and deep area of study. Graph Theorists study a variety of graphs or objects called graphs, with a wide range of conventions. For the purposes of this chapter, graphs are directed, there is at most two edges between graphs (one in each direction), and loops are disallowed. Note that in general some or any of these conventions can be modified or removed.
Add two vertices to this network: \(v_s, v_t\text{,}\) and two edges from \(v_s\) to two vertices, and two edges to \(v_t\) from two different vertices, each with infinite capacity, and extend the above flow to those edges so that this flow has a unique source and sink.
To be able to address the sort of questions we wish to ask, we will restrict ourselves to networks with a unique fixed source or sink, with no edges from the sink or to the source. In light of Activity 7.1.8, this is not really much of a restriction.
For each edge \((v_i, v_j)\text{,}\) there is a natural inequality constraint for the decision variables associated with this edge. What is this inequality?
For each vertex \(v_j\) not our source or sink, there is an equality constraint for the decision variables associated with this vertex. Which is this equality?
Let \(\mu_i\) denote the dual variable for Exploration 7.1.1 associated with vertex \(i\) and let \(y_{ij}\) denote the dual variable associated with edge \((v_i, v_j)\text{.}\)