Аноним

Складной граф: различия между версиями

Материал из WikiGrapp
нет описания правки
(Создана новая страница размером '''Складной граф''' (''Collapsible graph'') - ''орграф'', который может быть преобразован ...)
 
Нет описания правки
Строка 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]