lowlinkvärden

Lowlink values are a concept used in graph theory, particularly in algorithms for finding bridges and articulation points. A lowlink value, often denoted as low[u] for a vertex u, represents the smallest discovery time reachable from vertex u (including u itself) through the depth-first search (DFS) tree, potentially followed by at most one back-edge. Discovery time is the order in which a vertex is first visited during a DFS traversal.

During a DFS traversal, each vertex is assigned a discovery time. When exploring from a vertex u to an adjacent vertex v: if v has not been visited, it is a tree edge, and we recursively call DFS on v. After returning from the recursive call, we update low[u] to be the minimum of its current value and low[v]. This means that if v can reach an ancestor of u (or u itself) with a smaller discovery time, then u can also reach it. If v has already been visited and is not the immediate parent of u in the DFS tree, then (u, v) is a back-edge. In this case, we update low[u] to be the minimum of its current value and the discovery time of v.

Lowlink values are crucial for identifying bridges and articulation points. A bridge is an edge whose removal increases the number of connected components. An articulation point (or cut vertex) is a vertex whose removal increases the number of connected components. Specifically, for a non-root vertex u, if there exists a child v such that low[v] >= disc[u] (where disc[u] is the discovery time of u), then u is an articulation point. For the root of the DFS tree, it is an articulation point if it has more than one child in the DFS tree. Similarly, an edge (u, v) where v is a child of u in the DFS tree is a bridge if low[v] > disc[u].