4625
правок
Складной граф: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Складной граф''' (''Collapsible graph'') - ''орграф'', который может быть преобразован ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Складной граф''' (''Collapsible graph'') - | '''Складной граф''' (''[[Collapsible graph]]'') - | ||
''орграф'', который может быть преобразован в тривиальный | ''[[орграф]]'', который может быть преобразован в [[тривиальный граф|тривиальный]] | ||
некоторой последовательностью следующих трансформаций: | некоторой последовательностью следующих трансформаций: | ||
(1) удаление дуги <math>(x,y)</math> и вершины <math>y</math>, если | (1) удаление [[дуга|дуги]] <math>(x,y)</math> и вершины <math>y</math>, если | ||
<math>y</math> --- висячая вершина с одной заходящей дугой; | <math>y</math> --- [[висячая вершина]] с одной [[заходящая дуга|заходящей дугой]]; | ||
(2) замена дуг <math>(x,y)</math>, <math>(y,z)</math> | (2) замена дуг <math>(x,y)</math>, <math>(y,z)</math> | ||
и вершины <math>q</math> на новую дугу <math>(x,z)</math>, если | и вершины <math>q</math> на новую дугу <math>(x,z)</math>, если | ||
<math>y</math> - | <math>y</math> - [[вершина]] с одной заходящей дугой и одной [[исходящая дуга|исходящей]]; | ||
(3) удаление одной из двух кратных дуг. | (3) удаление одной из двух [[кратные дуги|кратных дуг]]. | ||
Без трансформации 1 получаем определение | Без трансформации 1 получаем определение | ||
''последовательно-параллельных'' графов, введенных | ''последовательно-параллельных'' графов, введенных | ||
Риорданом и Шенноном. Одна трансформация 1 определяет ''деревья''. | Риорданом и Шенноном. Одна трансформация 1 определяет ''[[дерево|деревья]]''. | ||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/95] | [Евстигнеев-Касьянов/95] | ||
