# Networks And Flows Flashcards

1

Q

For a directed graph, a capacity on G is?

A

A map- c:E -> **R**_{>=0}

2

Q

On a directed graph, the capacity of an edge is?

A

c(e) , where c:E -> **R**_{>=0}

3

Q

e_{+}

A

the end/sink/target of the edge e

4

Q

e_{-}

A

The start/source/origin of an edge e

5

Q

Directed path?

A

<=> aligned path: a path W where each edge is a forward edge

6

Q

Forward edge

A

e_{i}=v_{i}->v_{i+1}

7

Q

A network ?

A

N=(G,c,s,t)

Source = s

Sink = t

s,t € V

8

Q

Criteria for A flow?

A

**R** _{>=0} which satisfies

1) for all e€E, 0<= f(e) <= c(e)

2) for al v€V{s,t} ,

9

Q

In a flow, f(e) = c(e) ?

A

e is saturated

10

Q

In a flow, f(e) = 0 ?

A

e is void

11

Q

Prove

A

12

Q

Value of flow f?

A

w(f) =

13

Q

f is maximal if,

A

14

Q

A cut?

A

For a network N;

Denoted (S,T)

15

Q

Capacity of a cut?

A

Quantity given