In this episode, Charlie suggests using directed network flows to analize the murdered women's routine. Let us first review the needed definitions.
A directed network flow is a directed
graph with the following conditions:
In real life, directed network flows are used to model distribution
systems, as follows: Suppose Company Y delivers TV to XAL-MART. For
this, Company Y has a distribution network that looks like
directed graph above, where s represents
the storage facility, t represents XAL-MART, and u and v are intermediate facilities. The
edge capacities represent the maximum number of TV sets that can be
sent between two points. For instance, the edge (u,v) has capacity 1, and so
facility u is able to
send one TV set to v. What is
the maximum number of TV sets that Company Y can deliver to XAL-MART?
What would the flow be?
Suppose you have to get some amount of material X from the
distribution center s to a
retailer located at point t.
The directed edges represent the routes between different points, and
the capacities represent the
There
exists an algorithm to compute the maximum flow of a network known as
the Ford-Fulkerson
algorithm. The basic idea behind the algorithm is that if there
exists a path from s to t that has available capacity,
then send some flow along that path. Later improvements consisted in
selecting a "good" available path.
A very common application of network flows is to perfect matchings. For
this, we recall that a bipartite graph is a graph (collection of
vertices and edges connecting some of the vertices) where the
vertices can be divided into two sets L and R (which stand for left and
right) in such a way that no two vertices in L (or in R) share an edge.
The following picture illustrates this concept
The maximum matching problem
consists
of finding a set of edges M as large as possible so that any vertex in
the graph is an endpoint of at most one edge in M.
The perfect matching problem ask something about an undirected
graph. So in order to use directed network flows, we need to construct
a directed graph. We proceed as follows: Given a bipartite graph with L
and R having the same number of elements, construct a directed network
as described below.
(*) Construct two new vertices: one labeled s to the left of L and one labeled
t to the right of R.
(*) Construct a directed edge from s
to any vertex in L.
(*) Construct a directed edge from any vertex in R to t.
(*) Direct the edges from the bipartite graph from L to R.
(*) Assign 1 as the capacity to all the directed edges constructed.
Suppose that you are an assistant at your school's library. Your supervisor has given you the following assignment: There are n students in the need to write a paper on civil wars in Latin America for their history class. Unfortunately, they procrastinated and have only one week write their papers, but the library only owns m books on the topic. Due tho this constraints, you supervisor asked each person to submit a list with with the titles of at most two books. Since the students are picky, any of them who cannot obtain all the books requested, she will ask for an extension. Your job is to allocate the m books to guarantee that the largest number of people are able to obtain the books they requested (and thus, to the teacher's contempt, the number of students asking for an extension is minimum). How can you do this?