Block-cutvertex tree, block-cutpoint graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Block-cutvertex tree, block-cutpoint graph''' --- дерево (граф) блоков и точек сочленения. The '''block-cutvertex tree''' of a c…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 12:26, 20 апреля 2012
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.