Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

GA EXAM 2 > Exam2 Algo-Combined > Flashcards

Exam2 Algo-Combined Flashcards

RSA/Graph Theory

1
Q

Undirected Graph

Depth First Search

Purpose, Input, Output, Runtime

A

Purpose: Perform a depth first search on an undirected graph G.

Input: Undirected Graph G = (V, E)

Output: 4 arrays: prev, pre, post each of length n

  1. Prev[z] The parent index of vertex Z in the DFS visition
  2. pre[z] the pre number of vertex z in the DFS visitation
  3. post[z] the post number of the vertex z in the DFS visitation
  4. (Optional) ccnum[z] the connected component number, if stored after SCC algorithm run on graph.

Runtime: O(n + m)

AKA:O(|V| + (|E|)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Directed Graph

Depth First Search

Input, Output, Runtime

A

Purpose: Perform a depth first search on a directed graph G

Input: Directed Graph G=(V, E)

Output: 3 arrays, prev, pre, post, each of length n

  1. prev[z]: The parent index of vertex Z in the DFS visitation
  2. pre[z]: the pre order number of vertex Z
  3. post[z]: the post order number of vertex Z.

Runtime: O(n + m)

AKA: O(|V| + |E|)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Topographial Sort Directed

Purpose, input, output, runtime.

A

Purpose: Sort the verticies of an input graph in topological order. (Following left to right on resulting list means all preconditions will be done in order)

Input: directed acyclic graph G = (V, E)

Output: array topo length n

  1. topo[i]: The vertex number of the i’th vertex in topological order from left to right (in descending post order)

Runtime: O(n + m) no need to do sort after DFS, we know post order numbers and their ranges.

AKA: O(|V| + |E|)

Sink: Node with smallest post order

Source: Node with highest post order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Find Directed Strongly Connected Components

Purpose, input, output, runtime

A

Purpose: Find the strongly conencted components in a directed graph G.

Input: Directed Graph G=(V,E)

Output: Array ccnum of length n, array topo length t, where t is the number of SCCs, a directed acyclic metagraph Ga = Va, Ea

  1. ccnum[z]: The connected component numer of vertex z for z in V.
  2. topo[i] the SCC number for the ith SCC in topological order from left to right.
  3. Ga = the SCC acyclic metagraph.

Runtime: O(n + m)

AKA: O(|V| + |E|)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

BFS_Explore

Purpose, Input, Output, Runtime, Note

A

Purpose: Explore a graph G (directed or undirected) from a given vertex s using the breath-frist strategy.

Input: a graph G = (V, E) (directed or undirected) and a “source” vertex s in V

Output: an array dist such that dist[u] = distantce (in terms of #edges crossed from vertex s to vertex u

Runtime: O(n + m). AKA: O(|V| + |E|)

note: dist[u] = +inf if the vertex u is not reachable from s, and BFS doesn’t account for edge weights, it can only find the shortest path from s to u in terms of edge count.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

dfs_explore

Purpose, input, output, runtime

A

Purpose: Explore a graph G (directed or undirected) from a given vertex v

Input: G=(V, E), v in Vertexes

Output: (For reachable nodes, -1 for the rest)

  1. prev[z]
  2. pre[z]
  3. post[z]

Runtime: O(m) AKA O(E), only iterating over edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Reverse Directed Graph

(Considered housekeeping not need to be black boxed)

Purpose, Input, output, runtime

A

Purpose: Reverse a given directed graph G

input: A driected Graph G=(V,E)
output: A reversed graph Gr = (Vr, Er)
runtime: O(n + m) AKA O(|V| + |E|)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

KruskalMST

Purpose, Input, Output, Runtime

+Note

A

Purpose: Finds the minimum spanning tree over an input undirected connected graph. (Sorts edges and selects edges not traversing graph)

Input: an undirected graph G = (V,E) and a weight function w such that w(u,v) = weight of edge.

Output: a set of edges X, which is the minimum spannign tree of G.

Runtime: O(m log n) AKA: O(E log (v))

Note:If the graph is not connected, we get a minimum spanning forest.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Prim MST

Purpose, input, output, runtime, note

A

Purpose: Finds the minimum spanning tree G over an input undirected connected graph.

Input: An undirected graph G=(V,E) and a weight function w such that w(u,v) = weight of edge.

Ouptut: an array prev where prev[n] is the parent vertex number of vertex v. prev[root] = null by def.

runtime: O(m log(n)) AKA: O(E log (V))

Note: PRIM expects a connected graph. This is similar to dikjstra’s only instead of using the weight of the full path in the priority tree, it uses the weight of the solitary edge to build up on the frontier.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Dijkstra’s Single Source Shortest Path

Purpose, input, output, runtime, note

A

Purpose: Finds the shortest path to all nodes from a source s in a weighted graph G (directed or undirected) with non-negative weights.

Input: A graph G=(V,E) directed or undirected, a source vertex and edge weights.

Output: dist[v] shortest distance from s to v, and prev[v] = prev of v in the shortest path from s to v.

Runtime: O((n + m) log(n))

Note: if the graph is connected, M dominates n+m and our time is O(mlog(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Directed Acyclic Graph Single Shorted Path

Purpose, Input, output, runtime, note

A

Purpose: Find the shortest path and its length from the given source vertex s to all vertices v in V, in a directed acyclic weighted graph G=(V,E)

“Same as depth first search, topological sorting”

Input: a DAG G=(V,E), a source vertex s in V, and weights

Output: dist[v] the shortest distance from s to v and prev[v] = the prev of v in the shortest path from s to v.

Runtime: O(n + m)

Note: If it is not possible to reach a vertex u from s, then dist[u] = inf, and negative edges are allowed in this algorithm.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

BellmanFord Single Source Shortest Path

Purpose, Input, Output, Runtime, Note

A

Purpose: Find the shortest path to all nodes from a source s in a weight graph. With postiive or negative weights. (CAPABLE OF FINDING SHORTEST PATHS WITH NEGATIVE WEIGHTS)

Input: A graph G=(V,E), a source vertex s in v, and edge weights

Output: Dist[v] shortest distance from s to v, prev[v] previous vertex in shortest path from s to v.

Runtime: O(nm)

Note: Normally runs in V-1 cycles, however runnin gone more cycle can help detect negative weighted cycles. Also only cycles reachable from s can be detected.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

FloydWarshall All Point Shortest Path

Purpose, input, output, runtime, note

A

Purpose: Finds the shortest path for all pairs, with positive or negative edge weights.

Input: A graph G(V,E) directed or undirected and edge weights.

Output: dist[s,t]: the shortest distance from s to t. (dist is an nxn array

Runtime O(n3)

Can detect any negative cycles by checking distance from node to itself, if it is less than zero, there is a negative weight cycle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Ford-Fulkerson (max flow/min cut)

Purpose, Input, output, runtime

A

Purpose: Finds the maximum st-flow in a flow network

Input: Flow Network G=(V,E) with capacities and source sink s & t

Output: Flow fe for e in Edges

Runtime: O(mC) where C is the size of the maximium flow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Edmonds-Karp (max flow/min-cut)

purpose, input, output, runtime, note

A

Purpose: Finds the maximium st-flow in a flow network (a directed graph G=(V,E) with capacities

Input: Flow network G=(V,E) with capacties, a source, and a sink

Ouput: Flow fe for edges

Runtime: O(m2n)

Note: Same as F-F, but uses a BFS to find augmenting paths to give a runtime without the C.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a Valid Flow?

What is a Maximum Flow?

A

A Valid flow in a flow network is a flow in g that satisfies all capacity constraints for the edges. (E.g. fe <= C(E)

A Maximum flow is a flow of maximum value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.

Suppose that the capacity of a single edge (u, v) ∈ E is increased by 1. Give an O(V + E) time algorithm to update the maximum flow.

A

Compose the residual graph on the original flow. Add a positive 1 capacity on the edge that has been increased. Using BFS, search for an augmenting path; if the path exists, we can update the flow, otherwise, the flow is unchanged. We only need to do this once, as the augmenting path, if it exists, increases the flow by 1, which is the maximum increase possible.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.

Suppose that the capacity of a single edge (u, v) ∈ E is decreased by 1. Give an O(V + E) time algorithm to update the maximum flow.

A

Again, compose the residual graph on the original flow. If the decreased edge was not at capacity (that is, it still has positive residual capacity), then we can decrease the edge capacity by one without affecting the maximum flow. If not, then we add one to the negative capacity on the edge, and look for an augmenting path in reverse (going from t to s instead of from s to t) which includes the decreased edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.

A

First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Using Fermats Little Theorem how can we avoid testing every number 1 to P

A

for a single number

Prob that flt returns yes when N is prime is 1

Prob that flt returns yes when N is not prime is <= 1/2

So depending on the amount of certainty we pick k different a values, which gives us

1/2k as the probability flt returns yes when it is not prime.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What theorem would you use to solve:

wx - yx divisible by N

if

  1. N can be factored into two primes
  2. GCD(w,N) = 1 and GCD(y,N) = 1
A

Euler’s Theorem:

If N is the product of 2 prime numbers and GCD(a,n) = 1

Then A(p-1)(q-1) === 1 mod N

E.g. Is 41536 - 94824 divisible by 35

35 is product of 5 & 7 (two primes)

gcd(4,35) = 1

gcd(9,35) = 1

(p-1)(q-1) = (5-1) * (7-1) = 24

Z24 = 1 mod 35

1536/24 = 64 so 4(24*64) equals 1 mod 35

4824/24 = 201 so 9(24)(201) equals 1 mod 35

1 mod 35 = 1, 1 mod 35 = 1

1 -1 = 0, there is no left over so yes it is divisible!!!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the substitution rule for x and y

in modulo arithmetic in terms of x’ and y’

A

if

x = x’ (mod n) and y = y’ (mod n)

then

x + y === x’ + y’ (mod n)

and

xy === x’y’ (mod n)

10 * 15 (mod 4) =>

(10 (mod 4) * 15) (mod 4) -or-

(10 * 15 (mod 4)) (mod 4)-or-

(10 (mod 4) * 15 (mod4)) (mod 4)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Can you prove that if a mod b has an inverse then b mod a must also have an inverse?

A

Yes, a (mod b) only has an inverse if gcd (a,b) = 1

so the formula b (mod a) only has an inverse if gcd(b,a) = 1

gcd(a,b) and gcd(b,a) are the same formula.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Euler’s Theorem

A

For N = pq where p & q are prime,

For any Z where gcd(Z, N) = 1

Then Z(p-1)(q-1) is equivliant to 1 mod N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Multiply Algorithm

Time O(n2)

A

Multiply(x,y):

if y == 0: return 0

z = multiply(x, floor(y/2))

if y is even:

return 2z

else

return x + 2z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How can we use Fermats Little Theorem to prove a number is prime.

A

Fermat’s little theorem says:

If p is prime, then for every 1 <=a

a(p-1) === 1 (mod p)

So if we have a number P that we want to test for primality, then calculate

a(p-1) for every value a between 1 and p.

If they all equal 1 mod p, then it is prime.

(Note: There are some charmichael numbers like 561 which pass the test, but aren’t prime.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Euclid’s Rule

A

if x & y are positive integers x >= y,

then gcd(x,y) = gcd(x mod y, y)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

How are keys created for RSA

A
  1. Pick two large prime numbers p and q
  2. calculate n = pq. (n is the modulus for pub and priv)
  3. Calculate totient of n .. (p-1)(q-1)
  4. Choose e (the public key exponent) so that the gcd(e, totient(n)) = 1. (can be small like 3, 5, 35)
  5. Calculate d to be the inverse of e mod totient(n)
    1. Use Extended-Euclid (e,n)
    2. The number that returns as the multiple (x) for e is the inverse.
    3. if it’s negative you need to mod it. (Basically add N to it until it is positive.)
    4. This number alone not (x * e) but the x is the inverse x Mod N.

Public Key = (n, e)

Private key = (d)

Note if you get a decryption key of 1, then your selection of e was not gcd 1 with totn.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

ModExp Algorithm

Time O(n3)

A

ModExp(x, y, N):

if y = 0: return 1

Z = modexp(x, floor(y/2), N)

if y is even:

return z2 mod N

else

return x * z2 mod N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is Euclid’s Algorithm for GCD

Time O(n3)

A

Euclid(a,b):

// a and b with a >= b >= 0

if b = 0: return a

return Euclid(b, a mod b)

b, a mod b =>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

if x & y are positive

x >= y

then

gcd(x,y) is equal to

A

gcd(y, x mod y)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

p is prime, q is prime:

N = pq

What is totient(N)

A

(p-1)(q-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Big O time for modulo

Addition

Multiplication

Division

A

Addition => O(n)

Multiplication => O(n2)

Division => O(n3)

34
Q

What is multiplicative inverse for modulo numbers?

A

x is the multiplicative inverse of a (mod n)

if a*x (mod n) = 1

Sometimes one doesn’t exist. if gcd(a, N) > 1, it can never exist. E.g. a=2, N=6

When gcd(a, N) = 1 (we say a and N are relatively prime), the extended Euclid algorithm gives us integers x and y such that ax + N y = 1, which means that ax ≡ 1 (mod N). Thus x is a’s sought inverse.

35
Q

Divide Algorithm

Time O(n2)

A

Divide(x,y):

if x = 0: return (q,r) = (0,0)

(q,r) = divide(floor(x/2), y)

q = 2 * q, r = 2 * r

if x is odd:

r = r + 1

if r >= y:

r= r - y

q = q + 1

return (q, r)

36
Q

What is Eculid’s Extended Algorithm

(and what can you tell with it)

A

To check if a number d is the gcd of a and b. Then the extension says:

if d divides both a and b, and d = ax + by for some integers x and y then necessarily d = gcd (a,b)

extended-euclid(a,b):

input a,b with a>=b>=0

output: x, y, d such that d = gcd(a,b) and ax + by = d

if b = 0: return (1,0,a)

(x’, y’, d) = extended-Euclid(b, a mod b)

return (y’, x’ - floor(a/b)y’, d)

37
Q

Euler’s Totient Function

A

For prime P, Totient(P) = P - 1;

When N = pq, Totient(N) = (p-1)(q-1)

38
Q

How can you reduce 2345 (mod 31)

using the substitution rules and associativity, commutativity and distributivity

A

Taken together with the substitution rule, it is legal to reduce intermediate results modulo N at any stage. So simplifications can be made like:

2345 (mod 31) ==>

(25)69 (mod 31) ==>

3269 (mod 31) ==>

169 (mod 31) ==>

1 (mod 31)

39
Q

What theorem would you use to solve

a mod N

if N is prime.

A

Fermats Little Theorem

(If N is prime, than for 1 <= a < n)

a(n-1) = 1 mod N

199 (mod 5)

19(5-1) => 194 = 1 mod 5

Divide exponent by N-1:

9/4 = 2 R 1

This means 198 = 1 mod 5

Substiution leaves

198 (mod 5) * 191 (mod 5) => 1 (mod 5) * 19 mod 5

1 * 4 = 4

40
Q

How is RSA performed using:

N, e -> public key

d -> private key

A

Encrypt x:

y = xe mod N

Decrypt y:

x = yd mod N

41
Q

Fermat’s Little Theorem

A

If p is prime, then for every 1 <=a < p

ap-1 = 1 (mod p)

e.g: is 2^2 = 1 mod 3

p = 3 and is prime

2^(3-1) = 2^2 = 1 mod 3

1 mod 3

42
Q

How do you get a prime number?

A

Select a random n bit number

Run it through flt

if passes it is prime, otherwise try again

Probability of hitting a prime in n but numbers is 1/n so we expect this to only take n guesses at most.

43
Q

What are the 3 main steps to Kruskal’s Algorithm

Time: O(mlogn)

m = edges

n = verticies

A

Input: Undireted graph G(v,e) with weights w(e)

  1. Sort E by increasing weight
  2. Set x to the empty set.
  3. For each edge in our sorted list of edges, if adding edge into x does not create a cycle, then add the edge.
  4. Return x
44
Q

What are cut edges

Undirected G=(v,e)

Partition V = S union ~S

A

Cut(S,~S) = {(v,w) in E: v in S, w in ~s}

This says cut edges are the edges that

cross between S and ~S.

45
Q

2 Takeaway’s from MST proof

A

1) I can take a tree, add in e* and that creates a cycle. I can then remove any edge from that cycle and get a new tree T’
2) A minimum weight edge across the cut is part of a mst.

46
Q

What is topological order in an acyclic graph

A

The order based on decreasing post number.

47
Q

Cut Property

A

In building a minimum spanning tree, if we connect two minimum spanning trees using the lightest edge between the two of them, the result is a new minimum spanning tree.

48
Q

BFS

A

G = (V,E) - Directed or Undirected

vertex s in V

returns dist[u], prev[z]

O(n+m)

49
Q

Dijkstra

A

G = (V,E) - Directed or Undirected; vertex s in V; w

returns dist[u], prev[z],

O((n+m) log n)

50
Q

DFS

A

G = (V,E) directed or undirected

Output: prev, pre, post, ccnum

O(n+m)

51
Q

Explore

A

G(V,E) Directed or undirected

visited[], O(m)

52
Q

Kruskal’s

A

FInd MST defined bt Emst

G=(V,E) connected, undirected

O(m log n)

53
Q

Prim’s

A

FInd MST defined by prev[]

G=(V,E) connected, undirected

O(m log n)

54
Q

Bellman-Ford

A

Single source shorted path, allows negative edge weights.

O(nm)

55
Q

Floyd-Warshall

A

All paths shorted path

O(n^3)

56
Q

Ford Fulkerson

A

FInd max flow

Integers

O(mC)

57
Q

Edmonds-Karp

A

Find Max Flow

O(nm^2)

58
Q

What does V represent?

A

Set of vertices

59
Q

What does E represent?

A

Set of edges

60
Q

What does n = |V| represent?

A

Number of vertices

61
Q

What does m = |E| represent?

A

Number of edges

62
Q

What does s represent?

A

The source vertex

63
Q

What does t represent?

A

The sink vertex

64
Q

What is Breadth-first Search (BFS) algorithm used for?

A

To find unweighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Runtime is O(n+m)

65
Q

What is Dijkstra’s algorithm used for?

A

To find weighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Understand that when weights are involved, the runtime increases to O((n+m) log n)

66
Q

What is Depth-first Search (DFS) algorithm used for?

A

It behaves differently for directed and undirected graphs; In a directed graph, the pre/post numbers give information on how a graph COULD be explored; In an undirected graph, the pre/post numbers give information on how a graph WOULD be explored given a starting point; Runtime is O(n+m)

67
Q

What is the Explore algorithm used for?

A

This is a subroutine of DFS and does most of the work in DFS, it runs on all edges and vertices that are reachable from the provided v, can be used with a visited array to will set to true for all nodes u that are reachable from v; Runtime is O(n+m) if run by itself

68
Q

What is the Topological Sort algorithm used for?

A

This algorithm works by running DFS on the DAG (directed acyclic graph - it has no cycles) and using the post order number to sort the vertices from highest post number to lowest post number, when a DAG is ordered from source to sink, then all edges go from left to right; Runtime is O(n+m)

69
Q

What is the Strongly Connected Components (SCC) algorithm used for?

A

It takes a directed graph and runs DFS twice, running once with pre/post order numbering on the reverse graph of G and sorting V in descending post order numbers, giving sink to source; It then runs again on G with V sorted, the output will have ccnum representing each SCC with highest = source, and lowest = sink, the ccnum can be used to gather up vertices that belong to each SCC; Runtime is O(n+m)

70
Q

What is Kruskal’s Minimum Spanning Tree (MST) algorithm use for?

A

The algorithm sorts edges by weight of a connected and undirected graph, G = (V,E), and weights w, it grabs the lightest available edge that will not create a cycle when added to the MST, another way to look at this is to never add edges of vertices in the same component in the MST, this continues until all edges that will not create a cycle are added, this happens at exactly n-1 edges; Runtime is O(m log n)

71
Q

What is a source vertex?

A

It has no incoming edges and has the highest post number

72
Q

What is a sink vertex?

A

It has no outgoing edges and has the lowest post number

73
Q

Vertices are strongly connected if?

A

There is a path from v -> w and w -> v

74
Q

In Conjunctive Normal Form (CNF), AND is represented by?

A

^ looks like an A

75
Q

In Conjunctive Normal Form (CNF), OR is represented by?

A

V looks like a V

76
Q

What inputs are taken to a max-flow algorithm?

A

G(V,E), s, t, c where s a source vertex, t is a sink vertex, and c is capacities; This set of inputs is also known as a Flow Network

77
Q

What are the steps involved in obtaining the max-flow of a graph?

A

Build a residual network of the graph that shows the capacities along edges; Check for any path in the residual network from s to t using DFS or BFS - if none is found, we’re done; If found, get the minimum capacity along the path; Augment the path by capacitive units along the path, forward edges are increased and backwards edges are decreased; Runtime is O(n+m)

78
Q

Describe the Ford-Fulkerson algorithm.

A

Assumes all capacities are positive integers, runs in rounds by increasing the flow >= 1 per round so there are C rounds where C is the size of max flow; Runtime is O(mC)

79
Q

Describe the Edmonds-Karp algorithm.

A

Very similar to Ford-Fulkerson except it uses BFS to determine the shortest path rather than “any path”; Runtime is O(nm^2)

80
Q

Does an MST contain cycles?

A

No, they are acyclic graphs (no cycles)

81
Q

What does the max flow - min-cut theorem state?

A

The size of the max flow equals the size of the minimum st-cut

GA EXAM 2 (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions