Chapter 9 (Graph algorithms)

Question 1

If a graph is not biconnected, the vertices whose removal would disconnect the graph are called ____

Answer 1

Articulation points

Question 2

What is the running time of a topological sort?

Answer 2

O(|V|^2)

Question 3

What is a DAG?

Answer 3

Directed acyclic graph

Question 4

T/F Any connected graph, all of whose vertices have even degree, must have an Euler circuit

Answer 4

T

Question 5

What is the main difference between Prim’s and Dijkstra’s algorithms?

Answer 5

The update rule

Question 6

Max flow = ____

Answer 6

Min cut

Question 7

T/F Prim’s algorithm is a greedy algorithm

Answer 7

T

Question 8

When is a connected undirected graph considered to be biconnected?

Answer 8

When there is no vertex whose removal would disconnect the graph

Question 9

Explain Prim’s algorithm

Answer 9

Choose any vertex, then choose the edge with the lowest cost from this vertex and add it to the tree. We then choose the least edge between vertices in the tree and those not in the tree and add it.

Question 10

When is a directed graph considered weakly connected?

Answer 10

Its undirected representation is connected

Question 11

What is a Euler Path?

Answer 11

Visits each edge exactly once

Question 12

What is a graph with no cycles called?

Answer 12

Acyclic

Question 13

How can you keep track of each vertex as it is visited in an unweighted shortest path problem?

Answer 13

Table

Question 14

If a graph is acyclic, how can Dijkstra’s algorithm be improved?

Answer 14

Choosing vertices in topological order

Question 15

T/F Dijkstra’s algorithm works with negative edges

Answer 15

F

Question 16

In a maximum flow problem, what does Gr tell you?

Answer 16

How much more flow an edge can handle

Question 17

T/F Prim’s and Dijkstra’s algorithm have the same running time

Answer 17

T

Question 18

When is a directed graph considered strongly connected?

Answer 18

Path between all vertices

Question 19

T/F A graph cannot be represented as a 2D array

Answer 19

F, it can

Question 20

If a graph is sparse, what is a better solution?

Answer 20

Adjacency list

Question 21

T/F In a simple path, the first and last vertex cannot be the same

Answer 21

F, they can be

Question 22

What is the running time of the Dijkstra algorithm if a linear scan is required to find the cheapest vertex?

Answer 22

O(|E| + |V|^2)

Question 23

What is a problem with the maximum flow algorithm?

Answer 23

The first path chosen may result in having no other paths from s to t

Question 24

What is an edge to a visited node called?

Answer 24

Back edge

Question 25

In a directed graph, is u-v-u a cycle?

Answer 25

Yes since the u-v and v-u are different edges

Question 26

What is the running time of a depth first search?

Answer 26

O(|E|+|V|)

Question 27

What is a Euler Circuit?

Answer 27

Find a cycle that begins and ends at the same point that visits each edge exactly once

Question 28

What is an edge to an unvisited node called?

Answer 28

Tree edge

Question 29

When do we know if a graph has a Euler Path?

Answer 29

If the graph has no more than two vertices with odd degree

Question 30

What is the running time of Prim’s algorithm?

Answer 30

O(|E| log|V|)

Question 31

When is a vertex an articulation point?

Answer 31

When a child’s low is >= the parents num

Question 32

How does Krustal’s algorithm work?

Answer 32

Build the tree by starting with the cheapest edge between vertices and repeat. Reject any edge that will cause a cycle.

Question 33

What is the running time of the Dijkstra algorithm if a priority queue is used to find the cheapest vertex?

Answer 33

O(|E| log|V|)

Question 34

A depth-first search of a graph can produce a ____

Answer 34

Depth-first spanning tree

Question 35

T/F Euler circuits can be found using a series of depth-first searches

Answer 35

T

Question 36

In an undirected graph, is u-v-u a cycle?

Answer 36

No, the edges must be unique

Question 37

How can the maximum flow algorithm be improved?

Answer 37

Have a reverse flow so decision can be reversed if needed

Question 38

A depth-first search is a generalization of a ____ to apply to graphs

Answer 38

Preorder traversal

Question 39

When is a graph complete?

Answer 39

Edges between every pair of vertices

Question 40

Why might a 2D array not be good to represent a graph?

Answer 40

It can be a poor use of space if the graph is sparse

Question 41

What is the space requirement of an adjacency list?

Answer 41

O(|E|+|V|)

Question 42

What type of tree is a minimum spanning tree?

Answer 42

Acyclic

Question 43

How can you solve an unweighted shortest path problem?

Answer 43

Treat all edges as having a weight of 1

Question 44

What type of heap does Prim’s algorithm use?

Answer 44

Binary heap

Question 45

When is the root an articulation point?

Answer 45

When it has more than one child