# Graphs Flashcards

1
Q

What is the possible range of edges in a map, given the number of vertices (|V|)?

A

Between 0 and |V|^2 - |V|

2
Q

When a graph considered complete?

A

If it has all possible (|V|^2 - |V|) edges.

3
Q

What’s a digraph?

A

A directed graph.

4
Q

What are weighted graphs?

A

Graphs whose edges have weights.

5
Q

Edges may be incident to only one vertex.

A

False (minus edge-to-self graphs).

6
Q

When is a subgraph maximally connected?

A

If none of its vertices connect to any vertices of its parent graph (which it doesn’t already contain).

7
Q

Can a maximally connected subgraph have disconnected components?

A

No.

8
Q

The maximally connected subgraphs of an directed graph are called connected components.

A

False - this is true for undirected graphs, whereas directed graphs call them strongly connected components.

9
Q

Can an instance of a simple cycle also be a simple path?

A

No - due to the duplicate vertex (start and end).

10
Q

What is the minimum number of vertices in a cycle?

A

3.

11
Q

What determines the length of a path?

A

The number of edges (or vertices - 1).

12
Q

What’s a DAG?

A

Directed Acyclic Graphs

13
Q

Can a free tree be directed?

A

False.

14
Q

Can a free tree have non-simple cycles?

A

Can’t have cycles at all.

15
Q

Given a graph, what are the dimensions of its adjacency matrix?

A

|V| x |V|

16
Q

When is an adjacency matrix an efficient representation?

A

When the graph is dense, and undirected.

17
Q

What is the space complexity of an adjacency matrix for an undirected graph?

A

Still theta(|V|^2).

18
Q

What is the space complexity of an adjacency list for an undirected graph?

A

theta(|V| + |E|).

19
Q

What is the space complexity of an adjacency list for a directed graph?

A

theta(|E|)

20
Q

What is the space complexity of an adjacency list for a sparse graph?

A

theta(|V|)

21
Q

What is the space complexity of an adjacency list for a dense graph?

A

theta(|V|^2)

22
Q

Mark-bits solve what 2 problematic cases when traversing trees?

A

Cyclic graphs and disconnected graphs.

23
Q

What are previsit and postvisit operations in tree traversal?

A

Previsit operations are performed when a node is first visited, and a postvisit operation is performed after a node’s children have traversed.

24
Q

What is the cost of depth first search?

A

Θ(|V| + |E|), as each vertex must be visited once, but only once.

25
Q

When performing a topological sort, which traversal must be performed and which print operation type?

A

DFS, using post order print.

26
Q

Can topological sort be performed with a queue instead of a stack?

A

Yes.