Directed Graphs and Network Flow

Section 7.1 Directed Graphs and Network Flow

In this section, we introduce capacitated networks and flows.

Exploration 7.1.1.

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 labled. The bridges also only allow movement in one direction.

$A Network Flow depicting several islands with bridges and carrying capacity.$

(a)

Conjecture a solution to the maximum number of people that can arrive at $v_5$ in a minute.

(b)

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?

Definition 7.1.2.

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\text{.}$

A network is capacitated if for each edge $(v_i, v_j)\in E$ we assign a non negative 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\text{,}$ 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?)

Note 7.1.3.

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.

Definition 7.1.4.

For any vertex $v_j\text{,}$ the net input flow at vertex $v_j$ is $\varphi(v_j)=\displaystyle \sum_{i} x_{ij} - \sum_{i} x_{ji}$

If $\varphi(v_j)\lt 0$ then we say $v_j$ is called a source.

If $\varphi(v_j) > 0$ then we say $v_j$ is called a sink.

If $\varphi(v_j) = 0$ then we say $v_j$ is called an intermediary vertex.

Activity 7.1.5.

For the network in Exploration 7.1.1, find three different flows, including one you believe is an “optimal” flow.

(a)

For each flow you found: identify the sources, sinks, and intermediary vertices.

(b)

For each flow you found, compute the sum $\displaystyle\sum_{j} \varphi(v_j)\text{.}$

Theorem 7.1.6. Conservation of Flow.

For a capacited network $N\text{,}$ $\displaystyle\sum_{i} \varphi(v_i)=0\text{.}$

Activity 7.1.7.

Prove Theorem 7.1.6.

Activity 7.1.8.

Consider the network:

$A network with multiple sources and sinks.$

(a)

Find a (not necessarily optimal!) flow through this network with exactly two sources and exactly two sinks.

(b)

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.

Observation 7.1.9.

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.

Subsection 7.1.1 Max Flow

Activity 7.1.10.

Suppose we have a capacitated network with a unique fixed source $v_s$ and sink $v_d\text{.}$

We wish to define a maximization linear optimization problem with decision variables $x_{ij}, v_i, v_j\in V\text{.}$

(a)

Define the objective function both in terms of variables $x_{sj}$ and $x_{id}\text{.}$ Explain why these are equivalent (can you prove it?).

(b)

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?

(c)

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?

$\displaystyle \displaystyle \sum_{i}x_{ji} - \sum_{i}x_{sj}=0.$
$\displaystyle \displaystyle \sum_{i}x_{ij} - \sum_{i}x_{jd}=0.$
$\displaystyle \displaystyle \sum_{i}x_{ij}=0.$
$\displaystyle \displaystyle \sum_{i}x_{ji}=0.$
$\displaystyle \displaystyle \sum_{i}x_{ij} - \sum_{i}x_{ji}=0.$
$\displaystyle \displaystyle \sum_{i}x_{ij} + \sum_{i}x_{ji}=0.$

(d)

There is an additional type of inequality for this problem, what is it?

(e)

Write out the primal max problem for Exploration 7.1.1 as a non-canonical Tucker Tableau.

(f)

Solve this problem:

(g)

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{.}$

Describe the dual min problem.

Prev Top Next