Graphs Flashcards
What is the possible range of edges in a map, given the number of vertices (|V|)?
Between 0 and |V|^2 - |V|
When a graph considered complete?
If it has all possible (|V|^2 - |V|) edges.
What’s a digraph?
A directed graph.
What are weighted graphs?
Graphs whose edges have weights.
Edges may be incident to only one vertex.
False (minus edge-to-self graphs).
When is a subgraph maximally connected?
If none of its vertices connect to any vertices of its parent graph (which it doesn’t already contain).
Can a maximally connected subgraph have disconnected components?
No.
The maximally connected subgraphs of an directed graph are called connected components.
False - this is true for undirected graphs, whereas directed graphs call them strongly connected components.
Can an instance of a simple cycle also be a simple path?
No - due to the duplicate vertex (start and end).
What is the minimum number of vertices in a cycle?
3.
What determines the length of a path?
The number of edges (or vertices - 1).
What’s a DAG?
Directed Acyclic Graphs
Can a free tree be directed?
False.
Can a free tree have non-simple cycles?
Can’t have cycles at all.
Given a graph, what are the dimensions of its adjacency matrix?
|V| x |V|
When is an adjacency matrix an efficient representation?
When the graph is dense, and undirected.
What is the space complexity of an adjacency matrix for an undirected graph?
Still theta(|V|^2).
What is the space complexity of an adjacency list for an undirected graph?
theta(|V| + |E|).
What is the space complexity of an adjacency list for a directed graph?
theta(|E|)
What is the space complexity of an adjacency list for a sparse graph?
theta(|V|)
What is the space complexity of an adjacency list for a dense graph?
theta(|V|^2)
Mark-bits solve what 2 problematic cases when traversing trees?
Cyclic graphs and disconnected graphs.
What are previsit and postvisit operations in tree traversal?
Previsit operations are performed when a node is first visited, and a postvisit operation is performed after a node’s children have traversed.
What is the cost of depth first search?
Θ(|V| + |E|), as each vertex must be visited once, but only once.
When performing a topological sort, which traversal must be performed and which print operation type?
DFS, using post order print.
Can topological sort be performed with a queue instead of a stack?
Yes.
