Фрагмент

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

Фрагмент (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.


Fragment.gif


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

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

См. также

Литература

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