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

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

Литература

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

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