Разборный граф

Разборный граф (Collapsible graph) — уграф $G$, который может быть преобразован в тривиальный итеративным применением следующих двух преобразований: $T1$ — удаление петли и $T2$ — слияние двух вершин. Преобразование $T1$ определено для любой вершины $p$ уграфа $G$ и состоит в удалении дуги $(p,p)$ из $G$. Преобразование $T2$ определено только для такой пары вершин $p$ и $q$, что $p$ — единственный предшественник $q$; оно удаляет $q$ и $(p,q)$ из $G$ и заменяет в нем дуги, исходящие из $q$, на дуги, исходящие из $p$.

См. также

• Аранжируемый граф,
• Запрещенный подграф,
• Каркас уграфа,
• Одновходовый граф,
• Регуляризуемый граф,
• Сводимый управляющий граф.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
• Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.