Складной граф

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

(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 определяет деревья.

Литература

• Евстигнеев В.А., Касьянов В.Н. Базисные алгоритмы обработки бесконтурных графов. — Новосибирск: ИСИ СО РАН, 1995.