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

'''Разборный граф''' (''[[Collapsible graph]]'') — ''[[уграф]]'' <math>\,G</math>,  который может

быть преобразован в [[тривиальный граф|тривиальный]] итеративным применением следующих двух преобразований: <math>\,T1</math> — ''[[удаление ребра|удаление петли]]'' и <math>\,T2</math> — ''[[слияние двух вершин]]''. Преобразование <math>\,T1</math> определено для любой [[вершина|вершины]] <math>\,p</math> уграфа <math>\,G</math> и состоит в удалении [[дуга|дуги]] <math>\,(p,p)</math> из <math>\,G</math>. Преобразование <math>\,T2</math> определено только для такой пары вершин <math>\,p</math> и <math>\,q</math>, что <math>\,p</math> — единственный

[[предшественник вершины|предшественник]] <math>\,q</math>; оно удаляет <math>\,p</math> и <math>\,(p,q)</math> из <math>\,G</math> и заменяет в нем дуги, заходящие в <math>\,p</math>, на дуги, заходящие в <math>\,q</math>.

* ''[[Аранжируемый граф]],''

* ''[[Запрещенный подграф]],''

* ''[[Одновходовый граф]],''

* ''[[Регуляризуемый граф]],''

* ''[[Сводимый управляющий граф]].''

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

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