Block-cutvertex tree, block-cutpoint graph

Block-cutvertex tree, block-cutpoint graph — дерево (граф) блоков и точек сочленения.

The block-cutvertex tree of a connected graph [math]\displaystyle{ G }[/math] has a [math]\displaystyle{ B }[/math]-node for each block (biconnected component) of [math]\displaystyle{ G }[/math], and a [math]\displaystyle{ C }[/math]-node for each cutvertex of [math]\displaystyle{ G }[/math]. There is an edge between a [math]\displaystyle{ C }[/math]-node [math]\displaystyle{ u }[/math] and a [math]\displaystyle{ B }[/math]-node [math]\displaystyle{ b }[/math] if and only if [math]\displaystyle{ u }[/math] belongs to the corresponding block of [math]\displaystyle{ b }[/math] in [math]\displaystyle{ G }[/math]. The block-cutvertex tree can be constructed in linear time.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.