Graphs

Question 1

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

Answer 1

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

Question 2

When a graph considered complete?

Answer 2

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

Question 3

What’s a digraph?

Answer 3

A directed graph.

Question 4

What are weighted graphs?

Answer 4

Graphs whose edges have weights.

Question 5

Edges may be incident to only one vertex.

Answer 5

False (minus edge-to-self graphs).

Question 6

When is a subgraph maximally connected?

Answer 6

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

Question 7

Can a maximally connected subgraph have disconnected components?

Answer 7

No.

Question 8

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

Answer 8

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

Question 9

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

Answer 9

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

Question 10

What is the minimum number of vertices in a cycle?

Answer 10

3.

Question 11

What determines the length of a path?

Answer 11

The number of edges (or vertices - 1).

Question 12

What’s a DAG?

Answer 12

Directed Acyclic Graphs

Question 13

Can a free tree be directed?

Answer 13

False.

Question 14

Can a free tree have non-simple cycles?

Answer 14

Can’t have cycles at all.

Question 15

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

Answer 15

|V| x |V|

Question 16

When is an adjacency matrix an efficient representation?

Answer 16

When the graph is dense, and undirected.

Question 17

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

Answer 17

Still theta(|V|^2).

Question 18

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

Answer 18

theta(|V| + |E|).

Question 19

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

Answer 19

theta(|E|)

Question 20

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

Answer 20

theta(|V|)

Question 21

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

Answer 21

theta(|V|^2)

Question 22

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

Answer 22

Cyclic graphs and disconnected graphs.

Question 23

What are previsit and postvisit operations in tree traversal?

Answer 23

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

Question 24

What is the cost of depth first search?

Answer 24

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

Question 25

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

Answer 25

DFS, using post order print.

Question 26

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

Answer 26

Yes.