Block-cutvertex tree, block-cutpoint graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Литература

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