Chapter 7 Digraphs Flashcards
Defn/ A directed uv path in a digraph is:
is a series of arcs (digraph equiv. of edges) uu.1,u.1u.2,u.2u.3,…u.n-1v which don’t repeat vertices
Defn/ A digraph is strongly connected (diconnected) if
for any pair of vertices u,v there exists a u-v directed path
Defn/ Graph is orientable if:
if it is possible to assign directions s.t. the resulting digraph is strongly connected.
Thm/ (Robbins) A graph is orientable IFF it has no bridges
Graph can have directions assigned s.t. it is strongly connected IFF it doesn’t have any bridge edges
Defn/ If uv is an arc, we say: (adjacent)
We say that v is adjacent FROM u. Because direction matters.
Defn/ A tournament T is a digraph w/ the property:
if u,v in V(T), then either uv or vu is an arc
Defn/ The outdegree of v (OD v) is:
the number of vertices adjacent from v
Defn/ The indegree of v (ID v) is:
the number of vertices that v is adjacent to
Defn/ In a digraph, if ID v = 0, OD v > 0, (everything is going OUT), then it is called a:
called a transmitter
Defn/ In a digraph, if OD v = 0, ID v > 0, (everything is going OUT), then it is called a:
called a receiver
Defn/ The length of a directed path is:
the length of a dipath is the number of arcs contained in the path.
Defn/ The distance from u to v d(u,v) is:
is the length of the shortest directed path from u to v
Thm/ In a tournament T, let u have maximum OD, then the distance from u to any other vertex is:
the distance to any other vertex is either 1 or 2.
PF/ v has max OD n. Has u1….u.p-n+1 going INTO it, n v.1…v.n going out. Want those v.i to connect back to u.i. Suppose for u.i, no v.i connects to it. Then, it goes out to each of those v.i (bc tournament) so it has n+1 (1 comes from connecting to v), so contradicts that v has max OD.
Defn/ A hamiltonian path in a digraph is:
is a directed path containing all vertices.
Thm/ Every tournament contains a Ham. path.
Pf/ induct on order. Works order=2.
Draw a picture of straight line Ham. path without new vert. v, then place vert v below. Easy to add to path unless arrows go v.1 to v to v.n, but then you have to have the arrows connecting to the vert.s swap at some point. Check picture if this is confusing.
Thm/ In a digraph D, there is a directed path of length Chi-1 (chi is the chromatic number).
Pf/ wack proof
Defn/ A digraph D is transitive if:
whenever (u,v),(v,w) are arcs, then (u,w) is also an arc
Lemma/ If u.1,u.2,…u.p is a Ham path in a transitive tournament T, then:
Then (u.i,u.j) is an arc only when i<j. AKA a lower ranked person always loses to a higher ranked person
Pf/ Let j>i. Since (u.i,u.i+1),(u.i+1,u.i+2) are arcs, so is (u.i,u.i+1) by trans.
By induction, (u.i,u.i+k) is an arc bc prev is. Thus taking k=j, (u.i,u.j) is an arc.
Thm/ A tournament is transitive IFF it has a unique Hamiltonian path.
pf/ (tr+> unique)
BWOC, assume 2 diff ham paths. Then, H2 path must have 2 vert in different order, but by trans., we know they can only be arcs if i<j, which would not be the case since they’re in a diff. order in H1.
(unique=> trans)
Induct on order, then by prev. lemma, we know that the new vert added to the ham path can only go in one place and cannot move
Defn/ A directed network is:
is a digraph N together with a capacity function C: A(N) -> [0,/inf) whose vertices are a disjoint union of X,I,Y (X inputs, I intermediates, Y outputs)
Defn/ A flow f in a network is:
is a function f: A(N) -> [0,/inf) s.t.
1. 0<=f(a)<=C(a)
2. f+(v) = f-(v) for all V in I
Defn/ For S in V(N), the resultant flow out of S with respect to f is:
resultant flow = f+(S) - f-(S)
(total out minus total in)
Prop/ Resultant flow is equal to: (broken down into SUMMATION)
is {V in S}SUM f+(v) - f-(v)
Prop/ The resultant flow out of (regarding X,Y):
X is the resultant flow into Y
pf/ using that resultant flow is 0 for vert. in I
Defn/ The value of a flow is:
is valF = f+(X) - f-(X)
Prop/ Given flow network N, flow f, there exists a network N’, flow f’, w/ X’ = {x}, Y’ = {y}, valf = valf’
not sure exactly what this is saying. Thoughts?
Defn/ Let P be an undirected path (any path). AKA path in the underlying graph. then, the increment on P is:
i(P) = [a in A(P)]min i(a), where
i(a) = {C(a) - f(a) if a forward
{f(a) if a backward
Def/ Path P is f-saturated if:
if i(P) = 0, otherwise is unsaturated
Defn/ If path P is path from x to y, and P is unsaturated, then P is:
f-incrementing AKA we can run an increment on it to increase valf.
Alg/ Max flow algorithm
Given initial flow f.
1. Let T = {x} (source)
2. If arc a in (V(T), V(T)^C) AKA potential arc not in tree T going out from vert in T
AND f(a)<C(a) AKA not maxxed, then add a to T.
3. If a in (V(T)^C, V(T)) AKA it goes into the tree AND f(a)>0, add a to T b/c it has some backflow
4. Once you hit y, the sink node, then you have an incrementing path, so you can increment and repeat.
5. Keep making these trees until you can’t find an incrementing path
Defn/ A cut in flow network N is:
a cut is a set of arcs (S, S^C), where S subet of V(N), x in S, y in S^C.
Defn/ The capacity of a cut K:
capK = [a in K]SUM C(a), so the total capacity going from S to S^C.
Lemma/ valF = f+(S) - f-(S) for any cut (S, S^C)
pf/ f+(V) - f-(v) = 0 if in I, or valf is v=x source vertex.
Sum over S, and since x is in S, then we get that flow out of S is valf.
Thm/ For any flow f, cut K, then
1. valf <= capK by prev.
2. If all arcs in (S, S^C) have f(a) = C(a), and if all arcs in (S^C, S) have f(a) = 0, equality of 1. holds
3. If valf = capK for some f, K, then:
f(a) = {C9A0, a in (S, S^C)}
{0, a in (S^C, S) }
and f is a max flow, and K is a min. cut.
Pf of 3./
valf = capK, so that function necessarily holds. If any backflow, then we’d have to increase beyond capacity.
For any max flow f’, min cut K’,
valf <= valf’ <= capK’ <= capK.
Since valf = capK, these are all equal
Thm/ If T is a tree containing x, and f is a flow with
f(a) = {C(a), a in (T, T^C)}
{0, a in (T^C, T) }
then f is a max flow.
Pf/ Observe K = (V(T), V(T)^C) has capK = valf, so by prev, f is a max.
