Chapter 9 (Graph algorithms) Flashcards
If a graph is not biconnected, the vertices whose removal would disconnect the graph are called ____
Articulation points
What is the running time of a topological sort?
O(|V|^2)
What is a DAG?
Directed acyclic graph
T/F Any connected graph, all of whose vertices have even degree, must have an Euler circuit
T
What is the main difference between Prim’s and Dijkstra’s algorithms?
The update rule
Max flow = ____
Min cut
T/F Prim’s algorithm is a greedy algorithm
T
When is a connected undirected graph considered to be biconnected?
When there is no vertex whose removal would disconnect the graph
Explain Prim’s algorithm
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.
When is a directed graph considered weakly connected?
Its undirected representation is connected
What is a Euler Path?
Visits each edge exactly once
What is a graph with no cycles called?
Acyclic
How can you keep track of each vertex as it is visited in an unweighted shortest path problem?
Table
If a graph is acyclic, how can Dijkstra’s algorithm be improved?
Choosing vertices in topological order
T/F Dijkstra’s algorithm works with negative edges
F
In a maximum flow problem, what does Gr tell you?
How much more flow an edge can handle
T/F Prim’s and Dijkstra’s algorithm have the same running time
T
When is a directed graph considered strongly connected?
Path between all vertices
T/F A graph cannot be represented as a 2D array
F, it can
If a graph is sparse, what is a better solution?
Adjacency list
T/F In a simple path, the first and last vertex cannot be the same
F, they can be
What is the running time of the Dijkstra algorithm if a linear scan is required to find the cheapest vertex?
O(|E| + |V|^2)
What is a problem with the maximum flow algorithm?
The first path chosen may result in having no other paths from s to t
What is an edge to a visited node called?
Back edge
In a directed graph, is u-v-u a cycle?
Yes since the u-v and v-u are different edges
What is the running time of a depth first search?
O(|E|+|V|)
What is a Euler Circuit?
Find a cycle that begins and ends at the same point that visits each edge exactly once
What is an edge to an unvisited node called?
Tree edge
When do we know if a graph has a Euler Path?
If the graph has no more than two vertices with odd degree
What is the running time of Prim’s algorithm?
O(|E| log|V|)
When is a vertex an articulation point?
When a child’s low is >= the parents num
How does Krustal’s algorithm work?
Build the tree by starting with the cheapest edge between vertices and repeat. Reject any edge that will cause a cycle.
What is the running time of the Dijkstra algorithm if a priority queue is used to find the cheapest vertex?
O(|E| log|V|)
A depth-first search of a graph can produce a ____
Depth-first spanning tree
T/F Euler circuits can be found using a series of depth-first searches
T
In an undirected graph, is u-v-u a cycle?
No, the edges must be unique
How can the maximum flow algorithm be improved?
Have a reverse flow so decision can be reversed if needed
A depth-first search is a generalization of a ____ to apply to graphs
Preorder traversal
When is a graph complete?
Edges between every pair of vertices
Why might a 2D array not be good to represent a graph?
It can be a poor use of space if the graph is sparse
What is the space requirement of an adjacency list?
O(|E|+|V|)
What type of tree is a minimum spanning tree?
Acyclic
How can you solve an unweighted shortest path problem?
Treat all edges as having a weight of 1
What type of heap does Prim’s algorithm use?
Binary heap
When is the root an articulation point?
When it has more than one child
