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

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

См. также

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

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.