Core Traversal Mechanism Graph connectivity problems frequently rely on a single Depth-First Search (DFS) traversal. During the traversal, two primary values are maintained for every vertex u: Discovery Time (disc[u]): A monotonically increasing timestamp assigned when u is first visited. Low-Link V...
Introduction to Strongly Connected Components A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph where every vertex is reachable from every other vertex. In simpler terms, for any two nodes \(u\) and \(v\) with in the same SCC, there exists a path from \(u\) to \(v\) and...
Fundamental Definitions In graph theory, certain vertices and edges play a critical role in maintaining connectivity. This article explores four key concepts that help analyze network robustness. Articulation Points (Cut Vertices) An articulation point is a vertex whose removal (including all incide...