Запрещенный подграф

Запрещенный подграф (Forbidden subgraph) — Говорят, что уграф содержит запрещенный подграф, если в нем существуют различные вершины $p_1$, $p_2$ и $p_3$, что найдутся непересекающиеся по внутренним вершинам простые пути $P_{0,1}$, $P_{1,2}$, $P_{1,3}$, $P_{2,3}$, $P_{3,2}$, где $P_{i,j}$ обозначает путь от вершины $p_i$ до $p_j$. Отсутствие в уграфе запрещенного подграфа равносильно регуляризуемости уграфа.

См. также

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

Литература

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