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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 2: Строка 2:
''[[орграф]]'', который может быть преобразован в [[тривиальный граф|тривиальный]]
''[[орграф]]'', который может быть преобразован в [[тривиальный граф|тривиальный]]
некоторой последовательностью следующих трансформаций:
некоторой последовательностью следующих трансформаций:
[[Файл:Collapsible graph.png|500px]]


(1) удаление [[дуга|дуги]] <math>(x,y)</math> и вершины <math>y</math>, если
(1) удаление [[дуга|дуги]] <math>(x,y)</math> и вершины <math>y</math>, если

Версия от 13:22, 11 июня 2010

Складной граф (Collapsible graph) - орграф, который может быть преобразован в тривиальный некоторой последовательностью следующих трансформаций:

Collapsible graph.png

(1) удаление дуги [math]\displaystyle{ (x,y) }[/math] и вершины [math]\displaystyle{ y }[/math], если [math]\displaystyle{ y }[/math] --- висячая вершина с одной заходящей дугой;

(2) замена дуг [math]\displaystyle{ (x,y) }[/math], [math]\displaystyle{ (y,z) }[/math] и вершины [math]\displaystyle{ q }[/math] на новую дугу [math]\displaystyle{ (x,z) }[/math], если [math]\displaystyle{ y }[/math] - вершина с одной заходящей дугой и одной исходящей;

(3) удаление одной из двух кратных дуг.

Без трансформации 1 получаем определение последовательно-параллельных графов, введенных Риорданом и Шенноном. Одна трансформация 1 определяет деревья.

Литература

[Евстигнеев-Касьянов/95]