Фрагмент уграфа

Фрагмент (Fragment) — любая часть уграфа. Фрагмент $C$ является подфрагментом фрагмента $S$, если $C$ — часть $S$. Подфрагмент $C$ фрагмента $S$, отличный от $S$, называется собственным подфрагментом.

Вершина $p$ фрагмента $C$ называется начальной (соответственно выходной), если либо $p$ — начальная (соответственно конечная) вершина уграфа, либо в $p$ заходит (соответственно из $p$ исходит) дуга уграфа, не принадлежащая $C$. Вершина $p$ фрагмента $C$ называется входной (или входом), если существует путь по уграфу от его начальной вершины до $p$, не содержащий дуг $C$. Вершина $p$ называется конечной для фрагмента $C$, если она не принадлежит $C$ и является преемником хотя бы одной его вершины.

Вершина $p$ фрагмента $C$, отличная от начальной и конечной вершин уграфа, называется граничной вершиной $C$, если $p$ является начальной или выходной вершиной $C$. Граничная вершина $p$ фрагмента $C$ называется стартовой, если в нее не заходят дуги фрагмента $C$ или из нее не исходят дуги, не принадлежащие $C$, и финишной, если в нее заходят лишь дуги фрагмента $C$ или из нее не исходят дуги, принадлежащие $C$.

Фрагмент называется правильным, если он имеет в точности две граничные вершины, одна из которых — стартовая, а вторая — финишная. Правильный фрагмент называется простым, если он содержит одну дугу.

Правильный фрагмент, не являющийся простым, называется первичным, если все его собственные правильные подфрагменты являются простыми.

См. также

• Альт,
• Гамак,
• Зона,
• Интервал,
• Линейная компонента,
• Линейный участок,
• Луч.

Литература

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