# Exam 2 Flashcards

## Study for exam 2

1
Q

What must be present if there’s a back edge?

A

There must be a cycle in the graph if the DFS tree has a back edge

2
Q

What is a DAG and what are its characteristics?

A

directed acyclic graphs

every vertex u where there is an edge to vertex v has one direction

has no cycles in the graph

Can be topologically sorted

Must have one or more source vertex

Must have one or more sink vertex

3
Q

What is an alternative topological sorting algorithm?

A

Alternative topological sorting:
Find a sink vertex, output it, and then delete
Repeath this first step until the graph is empty

4
Q

How do we find a sink vertex in a DAG?

A

Find the lowest postorder number vertex in a DAG

5
Q

What is the pseudocode for the SCC algorithm?

A
• construct a reverse G of the original input graph G
• run DFS on G reverse
• order V by decreasing post order number
• run undirected connected components alg on G
6
Q

What are the types of edges in a graph?

A

forward edge - is a forward edge if it points from a vertex to one of its descendants in the DFS tree, but is not a tree edge
- pre(u) < pre(v)
- post(u) > post(v)
-

back edge - an edge u-v is a back edge if it points from a vertex to one of its ancestors in the DFS tree
- creates a cycle in the DFS tree
- pre(u) > pre(v)
- post(v) > post(u) (only one where this is the case)

tree edge - edge u-v is a tree edge if v is a direct descendent of u in a DFS tree
- part of the DFS tree
- pre(u) < pre(v)

cross edge - edge u-v is a cross edge if it connects two vertices that are neither in a direct ancestor-descendant relationship nor part of the same DFS tree
- pre(u) and pre(v) have no distinct relationship
- the finish time of u and v also have no distinctive relationship
-

7
Q

How do you find connected components in an undirected graph G? What is the runtime for doing this? What is the pseudocode?

A

Run DFS and keep track of component numbers #

O(n+m)

Psuedocode:
- Running explore from vertex
- Store z as visited because its the first time visiting
- Also store z in the current count for the connected components
- Now explore neighbors of z
If w or neighbor hasn’t been visited, the we call explore on that neighbor (recursively)

8
Q

How can we use DFS to find a path between 2 vertices?

A

Run DFS and populate the previous values for each vertex in a previous array

We then have the previous array and use this to find a path between the pair of connected vertices

9
Q

How do we find connectivity info on a directed graph?

A

We run DFS on the directed graph and add pre/post order numbers

Specifically:
We use clock values to track the pre and post orders

When first visiting vertex z, we store the preorder number

After visiting / exploring vertex z, we store the postorder number

10
Q

What is required for there to be a cycle in a DFS tree?

A

There must be a back edge

11
Q

Does a DAG have cycles or back edges

A

No cycles, no back edges

12
Q

What happens when we topologically sort a DAG? Can there be more than one topological orderings?

A

Topological sort -> ordering from vertices from lower numbers to higher numbers

All edges should go from higher postorder number to lower postorder number

Thus, we order vertices by decreasing post order number

All post order numbers range between 1 and 2n

Therefore, we make an array of size 2n and insert each vertex in to the array in the appropriate place based on their post order number. We then iterate from highest to smallest and output the vertices. This step takes linear time

Yes, there can be more than one topological orderings

13
Q

What are the source and sink vertices? How many do a DAG have?

A

Source = no incoming vertices; highest post order #

Sink = no outgoing edges; lowest post order #

Every DAG has one or more sink vertices

14
Q

Vertices u and v are strongly connected if …

A

and only if there is a path u to v and v to u

15
Q

How are SCC’s for an undirected graph found?

A

We find the SCC components in topological order

We visit any vertex from the sink vertex and visit nothing else
Then we find the strongly connected component

This even works for vertices like A where there are no other vertices in the SCC and they reach the whole graph

But once we find a sink vertex, we can run explore and get all parts of the SCC

16
Q

What does BFS do? What is it’s runtime?

A

BFS explores graph in layers
- Specify start vertex as an input
- Returns the distance of every vertex from the start vertex
- O(n+m)

17
Q

What does Dijkstra’s algorithm do? What is it’s runtime?

A

Dijkstra’ algorithm:
- More sophisticated version of BFS
= We are given a weights/length for every edge (needs to be positive)
- Output: shortest path from S to V
- Uses min-heap
- Runtime: O((n + m) * log n)

18
Q

What is the general SCC algorithm? What does it do and what is it’s runtime?

A

input: directed graph G in adj list

Steps:
- construct a reverse graph Gr
- run DFS on the reverse graph Gr
- order the vertices by post order number by decreasing post order number
- run undirected connected components algorithm on the graph

Overall runtime: O(n+m)

19
Q

Every directed graph is a …

A

DAG of its SCC’s

20
Q

What is a satisfiability problem? What is the k-SAT problem? k-SAT is np-complete for all k values?

A

input: CNF formula with n variables and m clauses

output: assignment (T or F) to the variables satisfying each of the clauses if one exists

For the k-SAT problem:
input: CNF formula with n variables and m clauses (each of size <= k)

output: assignment (T or F) to the variables satisfying each of the clauses if one exists (no if none exists)

The K-sat problem is NP-complete for k >= 3

21
Q

Solve this satisfiability problem:
(x2) ^ (xbar3 v x4) ^ (x3 v xbar5 v xbar1 v x2) ^ (xbar2 v xbar1)

A

Answer:
X1 = F
X2 = T
X3 = F

22
Q

How can an input to the satisfiability problem be simplified?

A

Simplify:
- take any unit clause with 1 literal:
- satisfy it the single literal
- remove clauses containing that same literal and drop the bar of the literal (opossite)
- let f’ be the resulting formula

Thus, f formula input is satisfiable if f’ is satisfiable

Can assume this for all cases where size = 2

23
Q

How is a graph related to a satisfiability problem? How is an SCC used?

A

Directed graphs to map out the implications for setting a given value to T or F indicating what you must set the next var to T or F

ex)
Take f with all clauses of size 2 with n variables and m clauses

2n vertices corresponding to the variables
2m edges corresponding to 2 “implications” per clause

If a literal var and its negation are in the same SCC, then f is not satisfiable

Its also true that any literal and its negation are in different SCCs, then there is a satisfying assignment

24
Q

What is the algorithm for the satisfiability problem? Pseudocode? Runtime?

A

2-SAT problem (for k = 2)

Based on:
- if for all i, if xi and xbari are in different SCC
then S is a sink SCC <=> Sbar is a source SCC

Algorithm:
- construct a graph G for f
- Take a sink SCC S
- set S=T (and Sbar = F)
- remove S and Sbar
- repeat until empty

O(n + m) runtime

25
Q

What is the MST problem? What are 2 algorithms for solving the MST problem?

A

input: given an undirected graph with weights

output: find the minimal size connected subgraph
- or minimum spanning tree of minimum weight

Both Kruskal’s algorithm works and Prim’s algorithm works for MST

26
Q

What are the properties of a tree?

A

n vertices, n-1 edges

exactly one path between every pair of vertices

Any connected graph G (V,E) with |E| = |V| - 1
is a tree

27
Q

How does Kruskal’s algorithm work? pseudocode/steps, runtime

A

input: undirected graph G (V,E) with weights

• sort each edge E by increasing weight (merge sort)
• set x != 0
• for each edge in the graph (in order):
• if x U e does not have a cycle:
x = x U E

return x

Total runtime: O(m log n )

28
Q

What are cuts and what is the cut property? What algorithm takes advantage of the cut property?

A

Cuts are edges where one point is in S and the other is in S bar - they are the edges crossing between S and S bar

for any undirected graph:
you partition portions of the graph as S and Sbar

`cut(S, Sbar) = edge crossing from S to Sbar`

The cut property:

We are building a partial solution X we are building up

The green edges part of the MST T

We take subset S and look at cut between S and S bar

At of all the cut edges between S and S bar in purple, I want to find the minimum weight edge - this is e star

Any edge that’s a minimum across a cut is going to be part of some MST

Prim’s algorithm and Kruskal’s algorithm uses the cut property
Kruskal’s Algorithm: Considers edges in increasing order and uses the cut property to decide if an edge should be added to the MST.

Prim’s Algorithm: Grows the MST by adding the smallest edge crossing the cut that separates the MST from the rest of the graph

29
Q

What is the max-flow problem?

A

Input: directed graph G (V,E) with s and t input vertices and capacities for each edge

Output: find the max flow for each edge where the capacity constraint is met and conservation of the flow is maintained (flow into v = flow out of v)

Fe is set for each edge in the input graph

Capacity Constraint: we need to have fe less than ce

Conservation of flow constraint: for all vertices minus s to t:
Flow in to v must be conserved or must equal the flow out of v

Flow into v:
Sum of the edges over w to v of the flow along this edge

Flow out of v:
Sum of the edges v to z of the flow along that edge

We are to find the valid flow of maximum size

30
Q

Is it okay to have a cycle in the graph for a max-flow problem?

A

Yes

31
Q

How do anti-parallel edges come into play in the max flow problem?

A

Simplification of the input network

We add edge capacities and now we find an equivalent flow network and the new network should not have anti parallel edges

We split the path from b to a into a 2 part path - b to f and f to a

32
Q

What is the Ford-Fulkerson algorithm, runtime, and steps/pseudocode?

A

Steps:
Considering the residual network we build it first
We look for path from s to t
If there’s no path, then output f
If we find the path, we donate it as p
Given p, the min capacity along p is Gf is c(p)
We augment the current flow by c(p) units along P
We repeat from step 2 until no such st-path

Runtime: O(mc)

33
Q

How does the Edmonds-Karp algorithm work? Runtime? Steps/pseudocode?

A

It uses Breadth-First Search (BFS) to find the shortest augmenting paths in terms of the number of edges. This guarantees that the algorithm runs in polynomial time

Steps:
- Construct the residual graph Gf based on the original capacities and current flows. Initially, it is the same as the original graph with capacities c(e)
- find the augmenting graph using BFS
- Update the flows in the following steps:
- determine the residual capacity of the augmenting graph
- increase the flow along the path P - for each edge in the path:
- update the flow by adding f(u,v)

f(u,v)=f(u,v)+cf (P)

cf(u,v)=c(u,v)−f(u,v)

Also update the reverse flow f(v, u) and the reverse residual capacity cf(v,u)

f(v,u)=f(v,u)−cf(P)

cf(v,u)=c(v,u)−f(v,u)

Repeat the process until no more augmenting paths can be found from s to t in the residual graph.

Runtime: O(VE^2) or O(m^2n)

34
Q

What is the max-flow / min-s-t cut theorem?

A

A cut is a partition of the L U R

s-t cut is a cut where S E L, t E R

capacity(L,R) = sum Cvw = capacity from L to R

for any flow f and any S-T cut (L,R)

size f <= capacity(L,R)

max size f <= minimal capacity(L,R)

claim is size(f) = f(out) L - f(in) L

we want a size(f) <= capacity(L,R)
max-flow <= min s-t cut capacity

35
Q

What is the residual network for the Ford Fulkerson algorith?

A

Residual network Gf

For the flow of flow graph G with edge capacities ce, for each edge in the graph and flow in the graph fe:
- if vw edge in and flow of wv edge are less than the capacity of vw edge, then add vw edge to the residual network graph Gf with capacity cvw - fvw

• if vw edge in and flow of wv edge are greater than 0, then add wv edge to the capacity Gf with capacity fvw
36
Q

What is the main difference between Ford-Fulkerson and Edmond’s-Karp?

A
• Edmond’s-Karp uses BFS while Ford-Fulkerson uses BFS or DFS or other approaches
• Edmond’s-Karp uses BFS to ensure that the shortest path is found in each iteration. This guarantees that the number of augmenting steps is minimized
• Edmonds-Karp is O(m^2n) while the Ford-Fulkerson time complexity depends on whether DFS or BFS is used (Edmonds-Karp provides a predictable runtime)
37
Q

You are given an unweighted, undirected graph G=(V, E) where V is a list of vertices and E is an adjacency list of edges. You are also given a vertex x and a value k such that you want to avoid x and any vertex within k distance of x. Lastly you are asked to find a shortest path from a given s to t. Assume that there is a path from s to t such that you can avoid x and vertices within k distance of x

Select the algorithm that is considered correct and optimal for this class. What is the runtime?

a.
We first run BFS from x such that we get shortest path costs to all other vertices. We then modify BFS such that if when we would visit a v in V that has a dist ≤ k from x, we avoid it instead of following that path. Run G through the modified BFS from s and return the shortest path from s to t.

b. We first run BFS from x such that we get shortest path costs to all other vertices. We then remove all v in V such that the dist from x is ≤ k. Run the updated G’ through BFS from s and return the shortest path from s to t.

c. dist = BFS(G, x).dist
G’ = G
for v in V:
if dist[v] ≤ k:
G’.remove(v)
prev = BFS(G’, s).prev
path_list = t
v = t
while prev[v] not null:
v = prev[v]
path_list = v + path_list
return path_list

d. Assuming all edges have a cost of 1, we first run Dijkstra’s from x such that we get shortest path costs to all other vertices. From all v in V that has dist to x ≤ k, set edges touching v to a cost of infinite. Run the updated G’ through Dijkstra’s from s and return the shortest path from s to t.

A

Correct answer b

By modifying the graph to remove any unwanted vertices, we create shortest paths that do not use the vertices we cannot travel through. BFS will find the shortest path for s to t.

runtime: The first BFS has a known runtime of O(n+m). Removing unwanted vertices and its edges is O(n+m). The second BFS is also O(n+m). This gives us a final runtime of O(n+m).