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

Разборный граф (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.