02 Finding Cut Vertices and Bridges, Cycles and Circuits, Hamiltonian Cycles and Gray Codes

Lecture from: 25.02.2025 | Video: Homelab

Let’s revisit connectivity concepts and then explore how to efficiently find cut vertices and bridges using Depth-First Search (DFS).

Review of Connectivity

Basic Definitions

Connected Graph: A graph $G = (V, E)$ is connected if, for every pair of distinct vertices $u, v \in V$ , there exists a path from $u$ to $v$ .
k-connected (Vertex Connectivity, $κ (G)$ ): A graph $G$ is k-connected if it has at least $k + 1$ vertices and removing any fewer than $k$ vertices leaves the remaining graph connected. This measures the robustness of the graph’s connectivity in terms of vertex removal.
k-edge-connected (Edge Connectivity, $λ (G)$ ): A graph $G$ is k-edge-connected if removing any fewer than $k$ edges leaves the remaining graph connected. This measures the robustness in terms of edge removal.
Minimum Degree ( $δ (G)$ ): The minimum degree of a graph is the smallest degree (number of incident edges) of any vertex.
Relationship: $κ (G) \leq λ (G) \leq δ (G)$

Menger’s Theorem

Vertex Version: A graph is k-connected if and only if there exist at least $k$ internally vertex-disjoint paths between any two distinct vertices.
Edge Version: A graph is k-edge-connected if and only if there exist at least $k$ edge-disjoint paths between any two distinct vertices.

Special Case: k = 1

Cut Vertex (Articulation Vertex): A vertex whose removal (along with its incident edges) disconnects a connected graph.
Cut Edge (Bridge): An edge whose removal disconnects a connected graph.

Block Graph

The block graph represents the structure of a graph in terms of its blocks (maximal 2-edge-connected subgraphs) and cut vertices. If the original graph is connected, its block graph is a tree.

Finding Cut Vertices and Bridges

Our goal is to efficiently identify cut vertices and bridges. Depth-First Search (DFS) provides an elegant solution.

DFS Review (from previous semester)

Breadth-First Search (BFS) and Depth-First Search (DFS)

BFS: Uses a queue (FIFO - First-In, First-Out) to explore the graph layer by layer. It’s useful for finding shortest paths (in terms of the number of edges).
DFS: Uses recursion (implicitly a stack, LIFO - Last-In, First-Out) to explore the graph as deeply as possible along each branch before backtracking. It’s well-suited for topological sorting and, as we’ll see, finding cut vertices.

Finding Cut Vertices using DFS

DFS Traversal and DFS Numbers

We perform a DFS traversal on an undirected graph. During the traversal, we assign a DFS number (dfs[v]) to each vertex $v$ . This number indicates the order in which the vertex was first visited during the DFS. The dfs numbers follow the same order as preorder traversal numbers.

Example:

DFS Tree

We can construct a DFS tree from the DFS traversal. The edges traversed during the initial discovery of a vertex are called tree edges. These edges form a spanning tree of the connected component containing the starting vertex. We can orient the tree edges by considering the direction of traversal as in the image below.

Back Edges (Restkanten)

The remaining edges of the original graph (those not in the DFS tree) are called back edges (Restkanten). These edges connect a vertex to one of its ancestors in the DFS tree. We can add these as dotted lines with direction according to when they have initially been visited during the depth-first search.

Low Numbers

The key to finding cut vertices is the concept of low numbers (low[v]).

Definition: The low number of a vertex $v$ , low[v], is the smallest DFS number reachable from $v$ by following:

Zero or more tree edges downward in the DFS tree (following the directed tree edges).
At most one back edge.

Example:

Calculating Low Numbers

We can compute low numbers during the DFS traversal with a slight modification:

Initialization: Initialize low[v] to dfs[v] for each vertex $v$ .
Update during DFS:
- Back Edge: If we encounter a back edge $(v, w)$ during the DFS (meaning dfs[w] < dfs[v] and $w$ is an ancestor of $v$ in the DFS tree, not the direct parent), then we update low[v] as follows:
```
low[v] = min(low[v], dfs[w])
```
- Tree Edge: If we traverse a tree edge $(v, w)$ (meaning $w$ is a child of $v$ in the DFS tree), we recursively compute low[w] first. After the recursive call returns, we update low[v] as follows:
```
low[v] = min(low[v], low[w])
```

Formula:

$l o w [v] = min ⎩ ⎨ ⎧ df s [v] (v, w) \in E min {df s [w] l o w [w] if (v, w) is a back edge if (v, w) is a tree edge$

Intuition:

low[v] represents the “lowest” (earliest visited) vertex that $v$ can “reach back to” via a path in the DFS tree and potentially a single back edge.
If a child $w$ of $v$ has low[w] >= dfs[v], it means that $w$ and its descendants cannot “reach back” to any ancestor of $v$ without going through $v$ . This indicates that removing $v$ would disconnect $w$ and its descendants from the rest of the graph, making $v$ a cut vertex.
A back edge always decreases the low number because it allows reaching a vertex with a smaller DFS number.
A tree edge may or not decrease the low number, if the subtree contains a back edge to an ancestor of v.
The low number calculation essentially propagates information about back edges “up” the DFS tree.

Example:

def find_cut_vertices(graph):
    """
    Finds cut vertices in an undirected graph using DFS.
 
    Args:
        graph: A dictionary representing the graph where keys are vertices
               and values are lists of neighbors.
 
    Returns:
        A set of cut vertices.
    """
    n = len(graph)
    dfs_num = [-1] * n  # DFS discovery time (initialized to -1, meaning unvisited)
    low = [-1] * n      # Low number
    parent = [-1] * n   # Parent in the DFS tree
    cut_vertices = set()
    time = 0
    
    def dfs(u):
        nonlocal time  # Access the nonlocal 'time' variable
        nonlocal cut_vertices
        children = 0    # Count of children in the DFS tree
        dfs_num[u] = time
        low[u] = time
        time += 1
 
        for v in graph[u]:
            if dfs_num[v] == -1:  # v is unvisited (Tree Edge)
                children += 1
                parent[v] = u
                dfs(v)
 
                # Update low[u] based on low[v]
                low[u] = min(low[u], low[v])
 
                # Check for cut vertex
                if parent[u] == -1 and children > 1:  # u is root and has multiple children
                    cut_vertices.add(u)
                if parent[u] != -1 and low[v] >= dfs_num[u]:  # Non-root cut vertex condition
                    cut_vertices.add(u)
 
            elif v != parent[u]:  # Back Edge (v is not the parent of u)
                # Update low[u] based on dfs[v]
                low[u] = min(low[u], dfs_num[v])
 
    # Iterate through all vertices to handle disconnected graphs
    for u in graph:
        if dfs_num[u] == -1:
            dfs(u)
 
    return cut_vertices

Identifying Cut Vertices: Justification

Let’s justify why the low number calculation allows us to identify cut vertices.

Consider a vertex $v$ in the DFS tree. Let $u$ be a child of $v$ in the DFS tree. Since we’re performing a DFS, the subtree rooted at $u$ represents all the vertices reachable from $u$ without going back through $v$ .

No Cross Edges: There cannot be a “cross edge” from the subtree rooted at $u$ to another subtree rooted at a different child of $v$ . If such an edge existed, it would have been explored during the DFS from $u$ (or before visiting v), and the other subtree would have been part of the subtree rooted at $u$ .
Back Edges Only to Ancestors: The only possible edges from the subtree rooted at $u$ to the rest of the graph are back edges to ancestors of $v$ (including $v$ itself).

The Key Idea: If the subtree rooted at $u$ has no back edge to an ancestor of $v$ , then removing $v$ will disconnect the subtree rooted at $u$ from the rest of the graph. This is because all paths from the subtree rooted at $u$ to the rest of the graph must pass through $v$ . The low[u] value captures precisely this information.

low[u] >= dfs[v]: This condition means that the lowest DFS number reachable from the subtree rooted at $u$ (using tree edges and at most one back edge) is either dfs[v] itself or a descendant of $v$ . In other words, there’s no way to “escape” the subtree rooted at $u$ and reach an ancestor of $v$ without going through $v$ . Thus, $v$ is a cut vertex.
low[u] < dfs[v]: This condition means there is a back edge from the subtree rooted at $u$ to an ancestor of $v$ . Therefore, removing $v$ would not disconnect the subtree rooted at $u$ from the rest of the graph, because there’s an alternative path.

Two Cases for Cut Vertices:

v is not the root of the DFS tree: $v$ is a cut vertex if and only if it has a child $u$ in the DFS tree such that low[u] >= dfs[v].
v is the root of the DFS tree: The root is a special case. It’s a cut vertex if and only if it has at least two children in the DFS tree. This is because if the root has only one child, removing the root would not disconnect the remaining subtree. If there are multiple child subtrees, they form separate connected components.

Linear Time Complexity:

The modified DFS algorithm (including the low number calculation) runs in linear time, $O (∣ V ∣ + ∣ E ∣)$ , because each vertex and each edge is visited and processed a constant number of times.

Finding Bridges using DFS

We can also use the low numbers to identify bridges.

The Key Idea: An edge $(v, w)$ in the DFS tree (where $v$ is the parent and $w$ is the child) is a bridge if and only if the subtree rooted at $w$ has no back edge to a vertex that is an ancestor of $v$ (including v). If that would be the case there would be an alternative route and removing such an edge wouldn’t make the graph unconntected.

Condition for a Bridge:

Let $(v, w)$ be a tree edge in the DFS tree, with $v$ being the parent of $w$ . Then $(v, w)$ is a bridge if and only if:

low[w] > dfs[v]

Explanation:

low[w] > dfs[v] means that the lowest DFS number reachable from the subtree rooted at $w$ is strictly greater than dfs[v].
This implies that there’s no back edge from the subtree rooted at $w$ to any ancestor of $v$ (including v). If it could connect to node v, we would have low[w] == dfs[v].
Therefore, the only way to reach the subtree rooted at $w$ from the rest of the graph is through the edge $(v, w)$ . Removing $(v, w)$ will disconnect the subtree.
Back Edges are obviously not bridges.

Cycles and Circuits

Let’s explore different types of cycles and circuits (both used interchangibly) in graphs.

Definitions

Walk: A walk in a graph $G = (V, E)$ is a sequence of vertices $v_{0}, v_{1}, ..., v_{k}$ such that $(v_{i - 1}, v_{i}) \in E$ for all $1 \leq i \leq k$ . A walk can revisit vertices and edges.
Path: A path is a walk in which all vertices are distinct.
Closed Walk: A closed walk is a walk where the starting and ending vertices are the same ( $v_{0} = v_{k}$ ).
Cycle (or Circuit): A cycle (or circuit) is a closed walk where all vertices are distinct except for the starting and ending vertices, which are the same. In other words, a cycle is a path that starts and ends at the same vertex. More formally, a cycle is a sequence of vertices $v_{0}, v_{1}, ..., v_{k}$ such that:
- $(v_{i - 1}, v_{i}) \in E$ for all $1 \leq i \leq k$
- $v_{0} = v_{k}$
- $v_{i} \neq = v_{j}$ for all $0 \leq i < j < k$ (all vertices are distinct except the start/end)
- $k \geq 3$ (a cycle must have at least three vertices, to avoid trivial cases like going back and forth on a single edge).
Eulerian Tour (or Eulerian Circuit): An Eulerian tour (or Eulerian circuit) is a closed walk that traverses every edge of the graph exactly once.
Eulerian Path: An Eulerian path is a walk that traverses every edge of the graph exactly once, but it is not necessarily closed (the start and end vertices can be different).
Hamiltonian Cycle (or Hamiltonian Circuit): A Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once (and returns to the starting vertex).
Hamiltonian Path: A Hamiltonian path is a path that visits every vertex of the graph exactly once, but it does not need to return to the starting vertex.

Key Differences:

Eulerian vs. Hamiltonian: Eulerian paths/circuits focus on traversing edges, while Hamiltonian paths/cycles focus on visiting vertices.
Cycle vs. Path: A cycle is a closed path. A path is not necessarily closed.

Eulerian Tour: Characterization

Theorem: A connected undirected graph $G = (V, E)$ has an Eulerian tour (a closed walk that traverses every edge exactly once) if and only if the degree of every vertex in $G$ is even. Furthermore, if an Eulerian tour exists, it can be constructed in $O (∣ E ∣)$ time.

Algorithm (Hierholzer’s Algorithm):

The algorithm for constructing an Eulerian tour is conceptually straightforward:

Start: Begin at any vertex $v$ in the graph.
Random Walk (Cycle Finding): Perform a “random” walk, traversing edges until you return to the starting vertex $v$ . Crucially, remove each traversed edge from the graph as you go. Since every vertex has an even degree, you will eventually return to $v$ , forming a cycle $C_{1}$ .
Check for Unused Edges: If there are still unused edges in the graph, find a vertex $w$ on the cycle $C_{1}$ that is incident to an unused edge.
Second Random Walk: Starting from $w$ , perform another random walk (again removing edges as you go) until you return to $w$ , forming a cycle $C_{2}$ .
Fusion: “Fuse” the cycles $C_{1}$ and $C_{2}$ at the common vertex $w$ . This creates a larger closed walk.
Repeat: Repeat steps 3-5 until all edges have been used.

Intuition (Why it works):

Even Degree Requirement: Every time a walk enters a vertex, it must also leave it. Therefore, each vertex must have an even number of incident edges to allow a closed walk that uses all edges.
Cycle Construction: Because of the even degree property, a random walk that removes edges will always eventually return to its starting point, forming a cycle. You can’t get “stuck” at a vertex because there will always be an unused edge to leave on.
Fusion: Fusing cycles at a common vertex creates a larger closed walk that still traverses each edge exactly once.

Hamiltonian Cycle: A Harder Problem

The Hamiltonian cycle problem (finding a cycle that visits every vertex exactly once) is considerably more difficult than the Eulerian tour problem.

History: The problem is named after Sir William Rowan Hamilton, who invented the “Icosian Game” in the 19th century.

Definition: A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once and returns to the starting vertex.

The Icosian Game

The Icosian Game involved a dodecahedron (a 12-sided solid with pentagonal faces) where the vertices represented cities and the edges represented routes between them. The goal was to find a route that visited each city exactly once and returned to the starting city (a Hamiltonian cycle).

Icosahedral Graph vs. Icosahedral Die:

Icosahedral Graph: The graph formed by the vertices and edges of a dodecahedron (or, equivalently, an icosahedron). Each vertex has degree 3.
Icosahedral Die: A 20-sided die where each face is an equilateral triangle. Each face of the die has three neighboring faces. The dual graph of an icosahedron is a dodecahedron.

Petersen Graph:

The Petersen graph is another example of a graph where each vertex has degree 3. However, unlike the icosahedral graph, the Petersen graph does not have a Hamiltonian cycle.

The Difficulty of Hamiltonian Cycles:

While the icosahedral graph has a Hamiltonian cycle, the Petersen graph does not. There is no known efficient (polynomial-time) algorithm to determine whether an arbitrary graph has a Hamiltonian cycle. This is one of the most famous unsolved problems in theoretical computer science, closely related to the P versus NP problem. Finding an efficient algorithm for the Hamiltonian cycle problem, or proving that none exists, would have profound implications.

Hamiltonian Cycles in Grid Graphs

Consider a 5x5 grid graph:

Does this graph have a Hamiltonian cycle? No.

Proof (Coloring Argument):

Chessboard Pattern: Imagine superimposing a chessboard pattern on the grid. Each edge in the grid connects a “black” square to a “white” square (or vice versa).
Alternating Colors: A Hamiltonian cycle must alternate between black and white squares. Therefore, a Hamiltonian cycle must contain an equal number of black and white squares.
Unequal Colors: In a 5x5 grid, there are 13 black squares and 12 white squares (or vice versa).

Impossibility: Since the number of black and white squares is unequal, a Hamiltonian cycle is impossible.

Generalization:

Consider an $m \times n$ grid graph.

$m \times n$ is even: A Hamiltonian cycle can be constructed. You can systematically traverse the grid in a “snake-like” pattern.
$m \times n$ is odd: A Hamiltonian cycle is impossible. The coloring argument applies: In an odd-sized grid, there will always be one more square of one color than the other. A Hamiltonian cycle requires an equal number of each color, so it cannot exist.

Rotary Encoders and Gray Codes

A rotary encoder is an electromechanical device that converts the angular position or motion of a shaft or axle to a digital (or analog) code. They are used in a wide variety of applications, including robotics, industrial controls, and computer input devices (like mice).

How Rotary Encoders Work (simplified):

Rotary encoders typically use optical or magnetic sensors to detect the rotation. A common type is the optical rotary encoder. This type has a rotating disk with a pattern of transparent and opaque segments (or holes). Light sensors detect the pattern of light and dark, which corresponds to the angular position.

(Good video explanation: https://www.youtube.com/watch?v=S2BfGMqe3kQ)

The Goal: Precision and Reliability

The goal is to design an encoder that can accurately measure the angle with high precision, using a limited number of sensors ( $n$ ). We want each distinct angular position to produce a unique digital code.

The Problem: Hamming Distance and Glitches

Imagine an encoder disk where adjacent segments have binary codes that differ by more than one bit (a Hamming distance greater than 1). For example:

Segment 1: 0101010
Segment 2: 0111000

The Hamming distance between these codes is 2 (two bits differ). The problem is that, in a real-world physical system, the transitions between bits might not happen exactly simultaneously. During a slow rotation, one sensor might detect the change before another. This can lead to a momentary “glitch” where the encoder outputs an incorrect code that doesn’t correspond to either of the intended positions.

Solution: Gray Codes and Hamming Distance of 1

To avoid these glitches, we want adjacent segments to have codes that differ by only one bit (a Hamming distance of 1). This ensures that even if the sensors don’t switch simultaneously, the intermediate code will be close to the correct code, minimizing errors. This is where Gray codes come in.

Abstraction: Hamiltonian Cycles on Hypercubes

The problem of finding a sequence of binary codes with a Hamming distance of 1 can be abstracted to a graph problem:

Representations: Each n-bit binary code can be represented as a vertex in an n-dimensional hypercube ( $H_{n}$ ).
Edges: Two vertices in the hypercube are connected by an edge if and only if their corresponding binary codes differ by exactly one bit (Hamming distance of 1).
Hamiltonian Cycle: Finding a sequence of all possible n-bit codes with a Hamming distance of 1 is equivalent to finding a Hamiltonian cycle in the n-dimensional hypercube.

If we can find a Hamiltonian cycle in the hypercube, we can use the sequence of binary codes as the pattern on the encoder disk.

Constructing Gray Codes (Hamiltonian Cycles in Hypercubes):

Does an n-dimensional hypercube ( $H_{n}$ ) always have a Hamiltonian cycle? Yes! We can construct a Hamiltonian cycle (and thus a Gray code) recursively.

Base Case (d=1): $H_{1}$ is a single edge connecting vertices 0 and 1. The sequence 0, 1 is a Hamiltonian path.
Base Case (d=2): $H_{2}$ is a square. A Hamiltonian cycle is 00, 01, 11, 10.
Recursive Step: Assume we have a Hamiltonian cycle for $H_{d - 1}$ . To construct a Hamiltonian cycle for $H_{d}$ :
- Make two copies of the Hamiltonian cycle for $H_{d - 1}$ .
- In the first copy, prefix each code with a ‘0’.
- In the second copy, prefix each code with a ‘1’, and reverse the order.
- Connect the last vertex of the first copy to the first vertex of the second copy, and connect the last vertex from second copy to the first one in the first copy.

Example (d=3):

d=2 (Base): 00, 01, 11, 10
d=3 (Recursive):
- Copy 1: 000, 001, 011, 010
- Copy 2 (Reversed): 110, 111, 101, 100
- Combined: 000, 001, 011, 010, 110, 111, 101, 100

Visualization (List-Based):

Another way to visualize the construction is:

Start with the Gray code for d=2: 00, 01, 11, 10
To get the Gray code for d=3:
- Write the d=2 sequence: 00, 01, 11, 10
- Write the d=2 sequence in reverse: 10, 11, 01, 00
- Prepend ‘0’ to the first sequence: 000, 001, 011, 010
- Prepend ‘1’ to the reversed sequence: 110, 111, 101, 100
- Concatenate: 000, 001, 011, 010, 110, 111, 101, 100

Continue here: 03 Hamiltonian Cycles, Dirac’s Theorem, Complexity Theory, Traveling Salesman

CS Notes

Explorer

02 Finding Cut Vertices and Bridges, Cycles and Circuits, Hamiltonian Cycles and Gray Codes

Review of Connectivity

Basic Definitions

Menger’s Theorem

Special Case: k = 1

Block Graph

Finding Cut Vertices and Bridges

DFS Review (from previous semester)

Breadth-First Search (BFS) and Depth-First Search (DFS)

Finding Cut Vertices using DFS

DFS Traversal and DFS Numbers

DFS Tree

Back Edges (Restkanten)

Low Numbers

Calculating Low Numbers

Identifying Cut Vertices: Justification

Finding Bridges using DFS

Cycles and Circuits

Definitions

Eulerian Tour: Characterization

Hamiltonian Cycle: A Harder Problem

The Icosian Game

Hamiltonian Cycles in Grid Graphs

Rotary Encoders and Gray Codes

How Rotary Encoders Work (simplified):

The Goal: Precision and Reliability

The Problem: Hamming Distance and Glitches

Solution: Gray Codes and Hamming Distance of 1

Abstraction: Hamiltonian Cycles on Hypercubes

Constructing Gray Codes (Hamiltonian Cycles in Hypercubes):

Table of Contents

Graph View