DFS Trees in Graph Theory

A DFS tree is formed during a depth-first search traversal of a graph or tree structure. Starting from a root vertex, the algorithm explores as far as possible along each branch before backtracking. In this process, edges traversed to unvisited nodes become tree edges, while edges leading to already visited nodes are classified as back edges.

For undirected graphs, DFS trees are straightforward. In directed graphs, connectivity may not be guaranteed from a single root, often resulting in a forest of trees.

Edge Classification in Directed Graphs

In directed DFS trees, non-tree edges are categorized as:

• Forward edges: From an ancestor to a descendant.
• Back edges: From a descendant to an ancestor.
• Cross edges: Between nodes with no ancestor-descendant relationship.

Properties of DFS Trees

1. In the generated tree, back edges always connect a vertex to its descendant.
2. A tree edge (u, v) is a bridge if and only if no back edge connects ancestors of u to descendants of v.

Connectivity in Undirected Graphs

Articulation Points and Bridges

Definitions:

• An articulation point (cut vertex) is a vertex whose removal increases the number of connected components.
• A bridge (cut edge) is an edge whose removal increases the number of connected components.
• Vertex contraction reduces a connected component to a single vertex, with edges connecting contracted components.
• A necessary vertex lies on all paths between two specific vertices.
• Two vertices are edge-biconnected if they reside in the same edge-biconnected component, and vertex-biconnected if in the same vertex-biconnected component.

Properties of Biconnected Components

Edge-biconnected components:

1. All bridges between two vertices are necessary edges for those vertices.
2. Contracting edge-biconnected or vertex-biconnected components yields a tree; contracting strongly connected components produces a directed acyclic graph.
3. Adding a new edge (u, v) merges the edge-biconnected components along the simple path between u and v into a larger component, demonstrating transitivity.
4. Two vertices are edge-biconnected if and only if no bridge exists between them.
5. For any edge (u, v) within an edge-biconnected component, removing it leaves u and v connected via an alternative path, ensuring a cycle through (u, v).

Vertex-biconnected components:

1. Removing an articulation point disconnects vertices that require it on all paths between them, making it a necessary vertex for those pairs.
2. Vertex-biconnected components may overlap, lacking transitivity.
3. Overlapping vertex-biconnected components intersect at articulation points.
4. Articulation points connect vertex-biconnected components, analogous to bridges connecting edge-biconnected components. Representing each component as a node and connecting them via articulation points forms a block-cut tree.
5. For a vertex-biconnected component with n > 3 vertices, every vertex lies on a simple cycle.

Menger's Theorem

• Edge version: In a finite graph, the maximum number of edge-disjoint paths between vertices u and v equals the minimum number of edges whose removal disconnects u from v.
• Vertex version: For non-adjacent vertices u and v in an undirected graph, the minimum number of vertices whose removal disconnects u and v equals the maximum number of vertex-disjoint paths between them.

Finding Articulation Points

Construct a DFS tree for the graph. To determine if vertex x is an articulation point:

• Let T(x) be the subtree rooted at x, and T'(x) be the rest of the graph.
• If removing x disconnects any vertex y in T(x) from T'(x), then x is an articulation point.
• This occurs when no back edge connects a descendant of x to an ancestor of x.

Define low[x] as the minimum discovery time reachable from x via tree edges and back edges. For non-root vertcies, x is an articulation point if there exists a child u such that low[u] >= dfn[x]. For root vertices, articulation occurs if the root has atleast two children.

Implementation:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_NODES = 100010;
vector<int> graph[MAX_NODES];
int discovery[MAX_NODES], low[MAX_NODES];
bool is_articulation[MAX_NODES];
int timer = 0;

void dfs_find_articulations(int node, int parent) {
    discovery[node] = low[node] = ++timer;
    int child_count = 0;
    
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        
        if (!discovery[neighbor]) {
            child_count++;
            dfs_find_articulations(neighbor, node);
            low[node] = min(low[node], low[neighbor]);
            
            if (low[neighbor] >= discovery[node] && parent != -1) {
                is_articulation[node] = true;
            }
        } else {
            low[node] = min(low[node], discovery[neighbor]);
        }
    }
    
    if (parent == -1 && child_count >= 2) {
        is_articulation[node] = true;
    }
}

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    for (int i = 0; i < edges; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    for (int i = 1; i <= vertices; i++) {
        if (!discovery[i]) {
            dfs_find_articulations(i, -1);
        }
    }
    
    int articulation_count = 0;
    for (int i = 1; i <= vertices; i++) {
        if (is_articulation[i]) articulation_count++;
    }
    
    cout << articulation_count << endl;
    for (int i = 1; i <= vertices; i++) {
        if (is_articulation[i]) cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

Finding Bridges

Bridges are always tree edges, never back edges. For a tree edge (u, v) where u is an ancestor of v, it is a bridge if low[v] > discovery[u].

Implementation with edge indexing:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_NODES = 1000010;
typedef pair<int, int> Edge;
vector<Edge> graph[MAX_NODES];
int discovery[MAX_NODES], low[MAX_NODES];
stack<int> node_stack;
vector<int> components[MAX_NODES];
int timer = 0, component_count = 0;

void form_component(int stop_node) {
    component_count++;
    int current;
    do {
        current = node_stack.top();
        node_stack.pop();
        components[component_count].push_back(current);
    } while (current != stop_node);
}

void dfs_find_bridges(int node, int incoming_edge) {
    discovery[node] = low[node] = ++timer;
    node_stack.push(node);
    
    for (Edge e : graph[node]) {
        int neighbor = e.first;
        int edge_id = e.second;
        
        if (edge_id == incoming_edge) continue;
        
        if (!discovery[neighbor]) {
            dfs_find_bridges(neighbor, edge_id);
            low[node] = min(low[node], low[neighbor]);
            
            if (discovery[node] < low[neighbor]) {
                form_component(neighbor);
            }
        } else {
            low[node] = min(low[node], discovery[neighbor]);
        }
    }
}

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    for (int i = 1; i <= edges; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back({v, i});
        graph[v].push_back({u, i});
    }
    
    for (int i = 1; i <= vertices; i++) {
        if (!discovery[i]) {
            dfs_find_bridges(i, 0);
            if (!node_stack.empty()) form_component(i);
        }
    }
    
    cout << component_count << endl;
    for (int i = 1; i <= component_count; i++) {
        cout << components[i].size() << " ";
        for (int v : components[i]) cout << v << " ";
        cout << endl;
    }
    
    return 0;
}

Connectivity in Directed Graphs

Strong Connectivity

Definitions:

• Two vertices u and v are strongly connected if there exists a directed path from u to v and from v to u.
• A strongly connected graph has all vertex pairs strongly connected.
• A strongly connected component (SCC) is a maximal subgraph where every vertex pair is strongly connected.

Properties and Tarjan's Algorithm for SCCs

In directed DFS trees, back edges and cross edges point to vertices with earlier discovery times, while forward edges do not. Key properties:

1. If u and v are strongly connected, all vertices on the tree path between them are also strongly connected.
2. Let f[x] be the minimum discovery time reachable from x via back or cross edges. A vertex x is a key vertex (root of an SCC) if f[x] >= discovery[x].

Tarjan's algorithm uses a stack to track vertices. When a key vertex is found (f[x] == discovery[x]), vertices are popped from the stack to form an SCC.

Implementation:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_NODES = 100010;
vector<int> graph[MAX_NODES];
int discovery[MAX_NODES], low[MAX_NODES];
bool on_stack[MAX_NODES];
stack<int> vertex_stack;
vector<vector<int>> scc_list;
int timer = 0;

void dfs_find_scc(int node) {
    discovery[node] = low[node] = ++timer;
    vertex_stack.push(node);
    on_stack[node] = true;
    
    for (int neighbor : graph[node]) {
        if (!discovery[neighbor]) {
            dfs_find_scc(neighbor);
            low[node] = min(low[node], low[neighbor]);
        } else if (on_stack[neighbor]) {
            low[node] = min(low[node], discovery[neighbor]);
        }
    }
    
    if (low[node] == discovery[node]) {
        vector<int> component;
        int current;
        do {
            current = vertex_stack.top();
            vertex_stack.pop();
            on_stack[current] = false;
            component.push_back(current);
        } while (current != node);
        scc_list.push_back(component);
    }
}

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    for (int i = 0; i < edges; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    
    for (int i = 1; i <= vertices; i++) {
        if (!discovery[i]) {
            dfs_find_scc(i);
        }
    }
    
    cout << "Number of SCCs: " << scc_list.size() << endl;
    for (const auto& component : scc_list) {
        for (int v : component) cout << v << " ";
        cout << endl;
    }
    
    return 0;
}

After contracting SCCs, the resulting graph is a directed acyclic graph (DAG), with vertices in reverse topological order.

Advanced Applications of DFS Trees

Using Difference Arrays for Bridge Detection

A tree edge (u, v) is a bridge if no back edge crosses it. This can be determined by marking ancestors and descendants during DFS and using difference arrays to track edge crossings.

Converting Undirected Graphs to Strongly Connected Graphs

An undirected graph can be oriented to become strongly connected if and only if it contains no bridges. In an edge-biconnected component, every vertex lies on a cycle, allowing orientation to ensure strong connectivity.