GR1 Flashcards

1
Q

A DAG has at least one ____ and one ____.

A

source, sink

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

In a topological ordering, which vertex comes first?

A

The vertex with the highest post order number

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

In a topological ordering, which vertex comes last?

A

The vertex with the lowest post order number.

So you order vertices by descending post order #.

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

Alternative method of topological ordering

A
  1. Find a sink, output it, and delete it.

2. Repeat step 1 until the graph is empty

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

Vertices V and W are ‘strongly connected’ if…

A

there is a path V –> W and W –> V

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

Undirected graphs have connected components, while directed graphs have ____.

A

strongly connected components

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

Definition of strongly connected component

A

maximal set of strongly connected vertices

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

Key property of metagraph of SCC

A

There are no cycles. => It’s a DAG!

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

Every directed graph is a …

A

DAG of its strongly connected components

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

In a general directed graph, the vertex with the ____ post # always lies in a ____ SCC.

A

highest, source

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

How do you find a sink vertex in a directed graph?

A

You construct a reverse graph and run DFS on it. The highest post number, which is a ‘source’ of the reverse graph, is the ‘sink’ for the original graph.

We take this mapping of ‘source’ vertices from the reversed graph and operate on them as ‘sink’ vertices on the original input graph.

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

After you find the ‘sink’ vertex, how do you find SCC?

A

From the sink vertex, you run DFS on it. Whatever vertices it touches are part of the component. Since it lies in a ‘sink’ SCC, we don’t have to worry about it going outside of its own SCC.

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

A graphs has a cycle iff it’s DFS tree has a ___

A

back edge

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

A graphs has a cycle iff it’s DFS tree has a ___

A

back edge

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