Block-cutvertex tree, block-cutpoint graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Block-cutvertex tree, block-cutpoint graph''' --- дерево (граф) блоков и точек сочленения. The '''block-cutvertex tree''' of a c…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Block-cutvertex tree, block-cutpoint graph''' --- дерево (граф)
'''Block-cutvertex tree, block-cutpoint graph''' — ''[[дерево блоков и точек сочленения|дерево (граф) блоков и точек сочленения]].''
блоков и точек сочленения.  


The '''block-cutvertex tree''' of a connected graph <math>G</math> has a <math>B</math>-node for each block
The '''block-cutvertex tree''' of a [[connected graph]] <math>G</math> has a [[N-node|<math>B</math>-node]] for each [[block]]
(biconnected component) of <math>G</math>, and a <math>C</math>-node for each ''cutvertex'' of <math>G</math>. There is an edge between a <math>C</math>-node <math>u</math> and a
([[biconnected component]]) of <math>G</math>, and a <math>C</math>-node for each ''[[cutvertex]]'' of <math>G</math>. There is an [[edge]] between a <math>C</math>-node <math>u</math> and a
<math>B</math>-node <math>b</math> if and only if <math>u</math> belongs to the corresponding block of
<math>B</math>-node <math>b</math> if and only if <math>u</math> belongs to the corresponding block of
<math>b</math> in <math>G</math>. The '''block-cutvertex tree''' can be constructed in linear time.
<math>b</math> in <math>G</math>. The '''block-cutvertex tree''' can be constructed in linear time.
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 16:31, 23 октября 2018

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.