p.15
Graph Traversal Algorithms: BFS and DFS
What happens during the first DFS starting at node G?
It leads nowhere, making G a singleton node component.
p.6
Graph Traversal Algorithms: BFS and DFS
What is the main method used in Depth-First Search (DFS)?
It explores as deeply as possible before backtracking.
p.4
Graph Traversal Algorithms: BFS and DFS
What is the simplest algorithm for st-connectivity?
Breadth First Search (BFS).
p.14
Strongly Connected Components in Directed Graphs
What is the definition of strong connectivity in directed graphs?
Two vertices u and v are in the same component if there is a directed path from u to v and from v to u.
p.9
Bi-Connectivity and Articulation Points
What is the only obstacle for a graph G to be bipartite?
The presence of odd cycles.
p.9
Graph Traversal Algorithms: BFS and DFS
How are nodes colored based on their level in the bipartiteness algorithm?
Nodes at level i are colored 0 if i is even and 1 if i is odd.
p.5
Graph Traversal Algorithms: BFS and DFS
What does level L_j consist of in a BFS?
All nodes at distance exactly j from the starting node s.
p.15
Graph Traversal Algorithms: BFS and DFS
What is the order of node numbering in the directed graph from largest to smallest?
G, H, J, I, B, F, C, A, D, E.
p.12
Topological Sorting of Directed Acyclic Graphs (DAGs
What does the existence of a topological ordering indicate about a graph?
It proves that the graph has no cycles.
p.6
Graph Traversal Algorithms: BFS and DFS
What is the stack implementation of DFS?
It uses a stack to keep track of nodes to explore.
p.10
Bi-Connectivity and Articulation Points
How can you check for bi-connectivity in a graph?
By removing each vertex in turn and checking if the graph remains connected using DFS or BFS.
p.3
Paths and Connectivity in Graphs
What does a path in a graph represent?
A sequence of vertices where each pair is connected by an edge.
p.14
Strongly Connected Components in Directed Graphs
Who developed the first linear time algorithm for finding strong connected components?
Hopcroft and Tarjan in the 1970s.
p.9
Graph Traversal Algorithms: BFS and DFS
How are the neighbors of vertex s colored in the bipartiteness algorithm?
All neighbors of s must be colored 1, making them the nodes of level 1.
p.8
Applications of BFS and DFS
What defines a bipartite graph G?
Its vertex set V can be partitioned into sets X and Y such that every edge has one end in X and the other in Y.
p.1
Basic Definitions of Graphs
How is a graph mathematically represented?
A graph is represented as G = (V, E), where V is the vertex set and E is the edge set.
p.11
Bi-Connectivity and Articulation Points
What is the condition for the root to be an articulation point?
The root is an articulation point if it has more than one child.
p.15
Strongly Connected Components in Directed Graphs
What is the significance of the root node x in the tree T found during the DFS?
It helps demonstrate the properties of strongly connected components.
p.4
Paths and Connectivity in Graphs
What is dead-code in program control-flow analysis?
Unreachable nodes that can be eliminated.
p.10
Bi-Connectivity and Articulation Points
How can low values of all nodes be computed?
By performing a post-order traversal of the DFS tree.
p.13
Topological Sorting of Directed Acyclic Graphs (DAGs
What is the condition for a graph to be a DAG in relation to DFS?
Any DFS forest of it contains no back edges.
p.3
Paths and Connectivity in Graphs
What is a connected component in a graph?
The set of all nodes reachable from a start node s.
p.16
Graph Traversal Algorithms: BFS and DFS
What is the significance of the recursive call order in DFS for nodes x and v?
The recursive call at v finishes before the call at x, confirming that v is a descendant of x.
p.9
Graph Traversal Algorithms: BFS and DFS
What is the time complexity for deciding the bipartiteness of a graph G?
O(m + n), where m is the number of edges and n is the number of vertices.
p.1
Basic Definitions of Graphs
What are graphs used for?
Graphs are useful models for reasoning about relations among objects and networked systems.
p.5
Paths and Connectivity in Graphs
How can we check if there is connectivity from s to t?
By checking if t belongs to the set R discovered by BFS.
p.2
Graph Representations: Adjacency Matrix and Adjacency List
What is an adjacency list?
An array of header cells pointing to linked lists of all vertices adjacent to each vertex.
p.11
Types of Graphs: Directed vs Undirected
What is the structure of an undirected graph without cycles?
Each connected component is a tree.
p.12
Topological Sorting of Directed Acyclic Graphs (DAGs
What is topological ordering?
An ordering of nodes in a graph such that for every edge (v_i, v_j), i < j.
p.4
Paths and Connectivity in Graphs
What does reachability find in garbage collection?
Memory objects accessible by the program.
p.4
Graph Traversal Algorithms: BFS and DFS
How do we define the next level L(i+1) in BFS?
Nodes not yet encountered that have an edge to some node in level L(i).
p.13
Topological Sorting of Directed Acyclic Graphs (DAGs
What happens to a vertex once it is printed in the topological sort algorithm?
It is deleted along with its outgoing edges.
p.14
Topological Sorting of Directed Acyclic Graphs (DAGs)
How are the edges of a directed graph G ordered based on DFS finish times?
All edges are directed from higher finish time to smaller finish time.
p.3
Paths and Connectivity in Graphs
What is the relationship between parent and child nodes in a rooted tree?
If u is the parent of w, then w is called a child of u.
p.16
Strongly Connected Components in Directed Graphs
What conclusion can be drawn if there is a path from v to x in graph G?
It must also imply that there is a path from x to v, completing the proof of their connectivity.
p.5
Graph Traversal Algorithms: BFS and DFS
What is produced by level by level exploration of a graph G?
A tree-like structure called the BFS tree of G.
p.1
Basic Definitions of Graphs
What are the two main components of a graph?
A set of vertices (nodes) and a set of edges.
p.5
Graph Traversal Algorithms: BFS and DFS
What is another method to discover the connected component R besides BFS?
Depth First Search (DFS).
p.7
Graph Traversal Algorithms: BFS and DFS
What is the time complexity of Depth-First Search (DFS)?
O(m + n), where n = |V| and m = |E|.
p.7
Graph Traversal Algorithms: BFS and DFS
How does the DFS tree compare to the BFS tree of a graph G?
The DFS tree looks very different from the BFS tree.
p.7
Graph Traversal Algorithms: BFS and DFS
What can be said about non-tree edges in DFS?
They connect the nodes of DFS in significant ways.
p.11
Bi-Connectivity and Articulation Points
When is a non-root node v considered an articulation point?
If it has a child w with low(w) ≥ Num(v).
p.11
Bi-Connectivity and Articulation Points
What does the low() value indicate in relation to articulation points?
If v is an articulation point, then the low() value for all explored nodes is ≥ Num(v).
p.15
Graph Traversal Algorithms: BFS and DFS
What is the outcome of the DFS at nodes D and E?
Both end with singleton components.
p.15
Strongly Connected Components in Directed Graphs
What is the purpose of the second DFS on G R?
To show that each tree found is a strongly connected component.
p.12
Topological Sorting of Directed Acyclic Graphs (DAGs
What is a Directed Acyclic Graph (DAG)?
A directed graph without cycles, commonly used in computer science.
p.12
Topological Sorting of Directed Acyclic Graphs (DAGs
How can tasks with precedence constraints be modeled?
As a directed graph where jobs are nodes and precedence relations are directed edges.
p.12
Topological Sorting of Directed Acyclic Graphs (DAGs
What is the implication if a graph G has a topological ordering?
Then G is a Directed Acyclic Graph (DAG).
p.6
Graph Traversal Algorithms: BFS and DFS
What happens when DFS reaches a dead end?
It backtracks to the nearest node with unexplored neighbors.
p.6
Graph Traversal Algorithms: BFS and DFS
What is the first step in the recursive implementation of DFS?
Mark the starting node as explored and add it to the result.
p.4
Paths and Connectivity in Graphs
What indicates an infinite loop in a program?
A node from which exit is unreachable.
p.6
Graph Traversal Algorithms: BFS and DFS
How does DFS handle unexplored neighbors?
It recursively calls DFS on each unexplored neighbor.
p.6
Graph Traversal Algorithms: BFS and DFS
What does the stack implementation do when it takes a node from the stack?
It checks if the node has been explored; if not, it marks it as explored.
p.6
Graph Traversal Algorithms: BFS and DFS
What is added to the stack in the non-recursive DFS implementation?
All unexplored neighbors of the current node.
p.4
Graph Traversal Algorithms: BFS and DFS
How do we prevent getting stuck in a loop during BFS?
By using markers to keep track of visited nodes.
p.10
Bi-Connectivity and Articulation Points
What defines a bi-connected undirected graph?
A bi-connected graph requires the deletion of at least two nodes to disconnect it, meaning no single node's removal can disconnect the graph.
p.14
Strongly Connected Components in Directed Graphs
What is the implication of having no cycles in a directed graph G during DFS?
There cannot be a back edge in a DFS of G, as a back edge would create a cycle.
p.16
Strongly Connected Components in Directed Graphs
What does the existence of directed paths from x to v and from v to x in graph G imply?
It implies that any two nodes v and w in tree T can be reached from one another through paths involving the root x.
p.14
Strongly Connected Components in Directed Graphs
What is the purpose of the second DFS in Kosaraju-Sharir's algorithm?
To output each subtree found as a strongly connected component (SCC) and remove it from the graph.
p.8
Graph Traversal Algorithms: BFS and DFS
In a DFS tree T, what can be said about two nodes x and y that have an edge between them in G but not in T?
One of x or y is an ancestor of the other.
p.5
Graph Traversal Algorithms: BFS and DFS
What is the relationship between nodes x and y in a BFS tree T if they belong to different levels?
If (x, y) is an edge of G, then |i - j| ≤ 1.
p.2
Basic Definitions of Graphs
What is the degree of a node in undirected graphs?
The degree equals the number of neighbors.
p.2
Graph Representations: Adjacency Matrix and Adjacency List
What is the space complexity of an adjacency list?
O(|E|) space, since each directed edge is stored just once.
p.10
Bi-Connectivity and Articulation Points
What is an articulation point in a graph?
An articulation point is a node whose removal disconnects the graph.
p.13
Topological Sorting of Directed Acyclic Graphs (DAGs
What is the first step in the algorithm for computing a topological ordering?
Find a vertex with zero in-degree.
p.3
Paths and Connectivity in Graphs
What is a weakly connected graph?
An underlying graph that is connected, but the directed graph may not have directed paths between all pairs.
p.16
Strongly Connected Components in Directed Graphs
How is the path from v to x established in graph G?
Node v is a descendant of x in tree T, indicating a directed path from x to v in the reverse graph G R.
p.9
Graph Traversal Algorithms: BFS and DFS
What is the initial step in the algorithm to check if G is bipartite?
Pick any arbitrary vertex s and color it 0.
p.8
Graph Traversal Algorithms: BFS and DFS
What is the relationship between connected components of any two nodes s and t in G?
Their connected components are either identical or disjoint.
p.2
Basic Definitions of Graphs
What are the two types of degrees in directed graphs?
Out-degree and in-degree.
p.10
Bi-Connectivity and Articulation Points
What is the Hopcroft-Tarjan algorithm used for?
It checks for bi-connectivity and finds all bi-connected components of a graph in O(n + m) time.
p.3
Paths and Connectivity in Graphs
What is the definition of a simple path?
A path with no repeated vertices, except the first and last can be the same (forming a cycle).
p.16
Graph Traversal Algorithms: BFS and DFS
What does the finish time of nodes in DFS indicate about their relationship?
If x has a larger finish time than v, it indicates that v is a descendant of x in the DFS of graph G.
p.9
Bi-Connectivity and Articulation Points
What is checked at the end of the bipartiteness algorithm?
Whether the endpoints of each edge of G are colored differently.
p.8
Applications of BFS and DFS
How are the sets X and Y often represented in bipartite graphs?
Using colors red and blue (or 0 and 1).
p.5
Bi-Connectivity and Articulation Points
What does the set of nodes discovered by BFS represent?
The connected component of G containing s.
p.2
Graph Representations: Adjacency Matrix and Adjacency List
What is an adjacency matrix?
A 2-dimensional array V × V where A[u, v] = 1 for an edge (u, v).
p.10
Bi-Connectivity and Articulation Points
What information is maintained for each vertex during DFS in the context of bi-connectivity?
Num(v) for the visit order and low(v) for the lowest-numbered vertex reachable from v.
p.13
Topological Sorting of Directed Acyclic Graphs (DAGs
What does the second algorithm for topological sorting use?
Depth-First Search (DFS).
p.14
Strongly Connected Components in Directed Graphs
What is the structure of the simpler algorithm by Kosaraju-Sharir for finding strong connected components?
1. Perform a DFS on G. 2. Number vertices in post-order. 3. Construct the reverse graph G R. 4. Perform a second DFS on G R starting from the highest numbered vertex.
p.9
Bi-Connectivity and Articulation Points
What does it indicate if an edge (x, y) has endpoints of the same color?
It indicates the presence of an odd cycle.
p.5
Paths and Connectivity in Graphs
When is there a path from s to t in a BFS?
If s appears in some level of BFS from s.
p.1
Basic Definitions of Graphs
What does an edge (u, v) represent in a graph?
It joins two nodes u and v.
p.1
Real-life Applications of Graph Theory
How can graph theory be beneficial in problem-solving?
Proper application of graph theory ideas can drastically reduce the solution time for important problems.
p.10
Bi-Connectivity and Articulation Points
How is low(v) defined?
low(v) is the minimum of Num(v), the lowest Num(w) among back edges (u, w), and the smallest low(w) among all children w of v.
p.3
Paths and Connectivity in Graphs
What characterizes a connected undirected graph?
There is a path between any two vertices.
p.3
Paths and Connectivity in Graphs
What is the st-connectivity problem?
Determining if there is a path joining two nodes s and t in a graph.
p.9
Graph Traversal Algorithms: BFS and DFS
How can one determine if a graph G is bipartite?
By using BFS to either discover the sets X and Y or detect an odd cycle.
p.8
Graph Traversal Algorithms: BFS and DFS
What does a recursive call DF S (u) mark as explored?
All nodes that are descendants of u in the DFS tree T.
p.2
Types of Graphs: Directed vs Undirected
What distinguishes a directed graph from an undirected graph?
In a directed graph, the pair (u, v) is distinct from (v, u); in an undirected graph, they are the same.
p.2
Basic Definitions of Graphs
What is a loop in graph theory?
An edge with both endpoints being the same.
p.2
Graph Representations: Adjacency Matrix and Adjacency List
What is a disadvantage of using an adjacency matrix?
It takes |V|² space even if the graph has very few edges.
p.2
Basic Definitions of Graphs
What is meant by 'adjacent' in graph terminology?
If (u, v) is an edge, then v is adjacent to (or a neighbor of) u.
p.1
Real-life Applications of Graph Theory
What is an example of an information network?
The World Wide Web, where web pages are nodes and hyperlinks are edges.
p.1
Real-life Applications of Graph Theory
What do nodes and edges represent in a communication network?
Nodes are computers and edges are physical links.
p.4
Graph Traversal Algorithms: BFS and DFS
How is Level L1 defined in BFS?
It consists of all neighbors of the starting node s.
p.13
Topological Sorting of Directed Acyclic Graphs (DAGs
What contradiction arises when assuming every vertex in a DAG has at least one incoming edge?
It leads to the existence of a cycle.
p.3
Paths and Connectivity in Graphs
What is a strongly connected directed graph?
A directed graph where there is a directed path between any two vertices.
p.9
Bi-Connectivity and Articulation Points
What is a key characteristic of a triangle in relation to bipartiteness?
A triangle is not bipartite because any partition will contain two nodes on the same side with an edge between them.
p.9
Bi-Connectivity and Articulation Points
What assumption can be made about graph G when checking for bipartiteness?
It can be assumed that G is connected; otherwise, the algorithm can be applied to each connected component separately.
p.8
Graph Traversal Algorithms: BFS and DFS
What happens when the edge (x, y) is examined during the execution of DF S (x) if y is marked Explored?
The edge is not added to T because y was discovered during the recursive call.
p.2
Types of Graphs: Directed vs Undirected
How can an undirected graph be converted to a directed graph?
By duplicating edges and orienting them both ways.
p.1
Real-life Applications of Graph Theory
Give an example of a transportation network graph.
The map of routes served by an airline carrier, where nodes are airports and edges represent non-stop flights.
p.2
Paths and Connectivity in Graphs
What is one fundamental operation in graphs?
Traversing a sequence of nodes (and edges).
