Lagmental Vicfred

Strong Components Form an Acyclic Condensation by Vicfred

tags: mathematics, connectivity, bridges, Menger theorem

Contracting every strongly connected component of a directed graph produces a DAG. I want the notation, the mechanism, and the failure mode visible at the same time.

Objects and notation

Connectivity asks how many vertices or edges must be removed to disconnect a graph \(G\). Depth-first search timestamps \(\operatorname{tin}(v)\) and low-link values \(\operatorname{low}(v)\) expose local cut structure.

$$ u\sim v\Longleftrightarrow u\rightsquigarrow v\ \text{and}\ v\rightsquigarrow u $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ \operatorname{cond}(G)=G/{\sim}\ \text{is acyclic} $$

Push the symbols

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ C_1\to C_2\to\cdots\to C_k\to C_1\Longrightarrow C_1=\cdots=C_k\quad\text{by mutual reachability} $$

Structural reading

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad u\sim v\Longleftrightarrow u\rightsquigarrow v\ \text{and}\ v\rightsquigarrow u,\\[5pt] \mathsf{C}\;&:\quad \operatorname{cond}(G)=G/{\sim}\ \text{is acyclic}. \end{aligned} $$

A hypothesis worth keeping

Bridge and articulation criteria depend on DFS-tree relationships. Applying them to an arbitrary spanning tree gives false positives.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{cond}(G)=G/{\sim}\ \text{is acyclic} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Tue 07 April 2020. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.