Final Flashcards
(38 cards)
flow network
a directed graphG = (V;E) with a single source node s (no incoming
edges) and a single target node t (no outgoing edges), as well as a positive number c(e) for each edge
e 2 E, called the capacity of e.
flow
Let G be a flow network. A flow on G is given by a positive number f(e) for each edge
e in G satisfying the following two constraints:
Capacity Constraints. For each edge e, 0 <= f(e) <= c(e).
Flow Conservation. For each vertex v 2 V that is not the source or sink vertex in s = out s
residual graph
Let G be a flow network and let f be a flow on G. The residual graph of G and f,
denoted Gf , is the directed graph defined as follows. The vertices of Gf are the same as the vertices
of G. For each edge e = (u; v) in G, if f(e) < c(e) then we add the edge (u; v) to Gf , labelled with
the number c(e) f(e). If f(e) > 0, then we also add the edge (v; u) to Gf , labelled with the number
f(e).
augmenting path
is any simple path in Gf connecting s to t.
s-t cut
An s-t cut in G is a subset U V of the vertices
of G such that s in U and t not in U
delta
Let G be a flow network, let f be a flow on G, and let Gf be the residual graph. Let
be any integer. The graph Gf() is the new graph obtained from Gf by discarding all edges e in
Gf with weight strictly less than .
matching
is a set of edges E0 E such that no
pair of edges in E0 share a vertex.
bipartite
A graph G = (V;E) is bipartite if there is a partition of the vertices V into two sets
L;R such that every edge in E connects a vertex in L to a vertex in R.
vertex cover
is a set of vertices U V such that
every edge e 2 E is adjacent to a vertex in U.
flow network with demands
A flow network with demands is given by a directed graph G = (V;E) such that every
edge e has a positive number c(e) (called the capacity of e) and every node v has a number d(v) (called
the demand at v).
circulation
G = (V;E) is a function f : E -> R+
such that Capacity Constraints. For every edge e 2 E, f(e) c(e).
Demand Constraints. For every node v 2 V , in v - out v = d
A flow network with demands and lower bounds
is given by a directed graph G =
(V;E) such that every edge e has two non-negative numbers `(e) c(e) associated with it, and every
node v has a number d(v) associated with it.
circulation with lower bounds
Capacity Constraints. For every edge e 2 E, `(e) f(e) c(e).
* Demand Constraints. For every node v 2 V ,
X
e into v
f(e)
X
e leaving v
f(e) = d(v):
linear constraint
on n real-valued variables x1; : : : ; xn is a constraint of the form
a1x1 + + anxn ./ b
where a1; : : : ; an; b 2 R and ./ 2 f=; g.
open halfspace
a set of points of the form {x 2 Rn | a * x < b} for a 2 Rn
closed halfspace
set of points of the form fx 2 Rn j a x <= bg.
decision problem
subset of f0; 1g
polynomial time
if there is a constant c 0 such that for every
input string x 2 f0; 1g, A halts after O(jxjc) computation steps
poly time computable
if there is a polynomial time algorithm A such that for all x 2 f0; 1g, if
x 2 L then A(x) = Yes and if x 62 L then A(x) = No.
P
{L {0; 1}* | L is polynomial-time computable}
coNP
{L {0; 1}* | !L in NP}
NP
{L {0; 1}* | L has polynomial time verifier}
Verifier
algorithm V that receives two inputs, x input to L and y a certificate for x and satisfies the property p(x) = yes <=> there exists a y such that y < x^o(1), V(x,y) = “Yes”
polynomial-time reduction
L2 is a function f : f0; 1g ! f0; 1g such that
* x 2 L1 <=> f(x) 2 L2.
* f is computable by a polynomial-time algorithm.
