Линейная компонента

Материал из WikiGrapp
Перейти к:навигация, поиск
Linear component.png

Линейная компонента (Linear component) — гамак C управляющего графа G, обладающий следующими свойствами: начальная и конечная (если она есть) вершины C принадлежат каждому пути из входа G в его выход; из конечной вершины гамака C не достижима в G начальная вершина гамака C; C не содержит собственного подграфа, который был бы гамаком и обладал бы первыми двумя свойствами.


Литература

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