Chapter 7 Digraphs

Question 1

Defn/ A directed uv path in a digraph is:

Answer 1

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

Question 2

Defn/ A digraph is strongly connected (diconnected) if

Answer 2

for any pair of vertices u,v there exists a u-v directed path

Question 3

Defn/ Graph is orientable if:

Answer 3

if it is possible to assign directions s.t. the resulting digraph is strongly connected.

Question 4

Thm/ (Robbins) A graph is orientable IFF it has no bridges

Answer 4

Graph can have directions assigned s.t. it is strongly connected IFF it doesn’t have any bridge edges

Question 5

Defn/ If uv is an arc, we say: (adjacent)

Answer 5

We say that v is adjacent FROM u. Because direction matters.

Question 6

Defn/ A tournament T is a digraph w/ the property:

Answer 6

if u,v in V(T), then either uv or vu is an arc

Question 7

Defn/ The outdegree of v (OD v) is:

Answer 7

the number of vertices adjacent from v

Question 8

Defn/ The indegree of v (ID v) is:

Answer 8

the number of vertices that v is adjacent to

Question 9

Defn/ In a digraph, if ID v = 0, OD v > 0, (everything is going OUT), then it is called a:

Answer 9

called a transmitter

Question 10

Defn/ In a digraph, if OD v = 0, ID v > 0, (everything is going OUT), then it is called a:

Answer 10

called a receiver

Question 11

Defn/ The length of a directed path is:

Answer 11

the length of a dipath is the number of arcs contained in the path.

Question 12

Defn/ The distance from u to v d(u,v) is:

Answer 12

is the length of the shortest directed path from u to v

Question 13

Thm/ In a tournament T, let u have maximum OD, then the distance from u to any other vertex is:

Answer 13

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.

Question 14

Defn/ A hamiltonian path in a digraph is:

Answer 14

is a directed path containing all vertices.

Question 15

Thm/ Every tournament contains a Ham. path.

Answer 15

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.

Question 16

Thm/ In a digraph D, there is a directed path of length Chi-1 (chi is the chromatic number).

Answer 16

Pf/ wack proof

Question 17

Defn/ A digraph D is transitive if:

Answer 17

whenever (u,v),(v,w) are arcs, then (u,w) is also an arc

Question 18

Lemma/ If u.1,u.2,…u.p is a Ham path in a transitive tournament T, then:

Answer 18

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.

Question 19

Thm/ A tournament is transitive IFF it has a unique Hamiltonian path.

Answer 19

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

Question 20

Defn/ A directed network is:

Answer 20

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)

Question 21

Defn/ A flow f in a network is:

Answer 21

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

Question 22

Defn/ For S in V(N), the resultant flow out of S with respect to f is:

Answer 22

resultant flow = f+(S) - f-(S)
(total out minus total in)

Question 23

Prop/ Resultant flow is equal to: (broken down into SUMMATION)

Answer 23

is {V in S}SUM f+(v) - f-(v)

Question 24

Prop/ The resultant flow out of (regarding X,Y):

Answer 24

X is the resultant flow into Y
pf/ using that resultant flow is 0 for vert. in I

Question 25

Defn/ The value of a flow is:

Answer 25

is valF = f+(X) - f-(X)

Question 26

Prop/ Given flow network N, flow f, there exists a network N’, flow f’, w/ X’ = {x}, Y’ = {y}, valf = valf’

Answer 26

not sure exactly what this is saying. Thoughts?

Question 27

Defn/ Let P be an undirected path (any path). AKA path in the underlying graph. then, the increment on P is:

Answer 27

i(P) = [a in A(P)]min i(a), where
i(a) = {C(a) - f(a) if a forward
{f(a) if a backward

Question 28

Def/ Path P is f-saturated if:

Answer 28

if i(P) = 0, otherwise is unsaturated

Question 29

Defn/ If path P is path from x to y, and P is unsaturated, then P is:

Answer 29

f-incrementing AKA we can run an increment on it to increase valf.

Question 30

Alg/ Max flow algorithm

Answer 30

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

Question 31

Defn/ A cut in flow network N is:

Answer 31

a cut is a set of arcs (S, S^C), where S subet of V(N), x in S, y in S^C.

Question 32

Defn/ The capacity of a cut K:

Answer 32

capK = [a in K]SUM C(a), so the total capacity going from S to S^C.

Question 33

Lemma/ valF = f+(S) - f-(S) for any cut (S, S^C)

Answer 33

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.

Question 34

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.

Answer 34

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

Question 35

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.

Answer 35

Pf/ Observe K = (V(T), V(T)^C) has capK = valf, so by prev, f is a max.