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

Материал из WikiGrapp
Версия от 12:14, 4 сентября 2019; KVN (обсуждение | вклад) (См. также)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Запрещенный подграф (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. Отсутствие в уграфе запрещенного подграфа равносильно регуляризуемости уграфа.

Forbidden subgraph1.png

См. также

Литература

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