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

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 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 .

🔗

A network is capacitated if for each edge

(v_{i}, v_{j}) \in E

we assign a non negative capacity

c_{i j} .

(If there is no edge from

v_{i}

v_{j},

we may equivalently say that

c_{i j} = 0 .

)

🔗

A flow assigned to a capacitated network is an assignment to each edge

(v_{i}, v_{j}) \in E,

a value

x_{i j}

such that

0 \leq x_{i j} \leq c_{i j} .

(If there is no edge from

v_{i}

v_{j},

what must

x_{i j}

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},

the net input flow at vertex

v_{j}

φ (v_{j}) = \sum_{i} x_{i j} - \sum_{i} x_{j i}

🔗

φ (v_{j}) < 0

then we say

v_{j}

is called a source.

🔗

φ (v_{j}) > 0

then we say

v_{j}

is called a sink.

🔗

φ (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

\sum_{j} φ (v_{j}) .

🔗

Theorem 7.1.6. Conservation of Flow.

For a capacitated network

N,

\sum_{i} φ (v_{i}) = 0 .

🔗

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},

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

🔗

We wish to define a maximization linear optimization problem with decision variables

x_{i j}, v_{i}, v_{j} \in V .

🔗

(a)

Define the objective function both in terms of variables

x_{s j}

and

x_{i d} .

Explain why these are equivalent (can you prove it?).

🔗

(b)

For each edge

(v_{i}, v_{j}),

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?

🔗

$\sum_{i} x_{j i} - \sum_{i} x_{s j} = 0.$
$\sum_{i} x_{i j} - \sum_{i} x_{j d} = 0.$
$\sum_{i} x_{i j} = 0.$
$\sum_{i} x_{j i} = 0.$
$\sum_{i} x_{i j} - \sum_{i} x_{j i} = 0.$
$\sum_{i} x_{i j} + \sum_{i} x_{j i} = 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:

🔗

xxxxxxxxxx
 
%display typeset
A = (FIXME)
b = (FIXME)
c = (FIXME)
P = InteractiveLPProblem(A, b, c,
 [FIXME], 
 constraint_type = [FIXME],
 variable_type = [FIXME],
 problem_type = FIXME)
P

xxxxxxxxxx
 
print(P.optimal_solution())
print(P.optimal_value())

🔗

(g)

Let

μ_{i}

denote the dual variable for Exploration 7.1.1 associated with vertex

i

and let

y_{i j}

denote the dual variable associated with edge

(v_{i}, v_{j}) .

🔗

Describe the dual min problem.

🔗

Prev Top Next