Фрагмент: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Фрагмент''' (''Fragment'') - любая часть уграфа. Фрагмент <math>C</math> является ''подф...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Фрагмент''' (''Fragment'') | '''Фрагмент''' (''[[Fragment]]'') — любая часть [[уграф|уграфа]]. Фрагмент <math>C</math> является ''[[подфрагмент|подфрагментом]]'' фрагмента <math>S</math>, если <math>C</math> — часть <math>S</math>. | ||
любая часть уграфа. Фрагмент <math>C</math> является | |||
''подфрагментом'' фрагмента <math>S</math>, если <math>C</math> | |||
Подфрагмент <math>C</math> фрагмента <math>S</math>, отличный от <math>S</math>, называется | Подфрагмент <math>C</math> фрагмента <math>S</math>, отличный от <math>S</math>, называется | ||
''собственным'' подфрагментом. | [[собственный подфрагмент|''собственным'' подфрагментом]]. | ||
Вершина <math>p</math> фрагмента <math>C</math> называется ''начальной'' | [[Вершина]] <math>p</math> фрагмента <math>C</math> называется ''[[начальная вершина|начальной]]'' | ||
(соответственно ''выходной''), если либо <math>p</math> | (соответственно ''[[выходная вершина фрагмента|выходной]]''), если либо <math>p</math> — начальная | ||
(соответственно конечная) вершина уграфа, либо в <math>p</math> заходит | (соответственно [[конечная вершина|конечная]]) вершина уграфа, либо в <math>p</math> заходит | ||
(соответственно из <math>p</math> исходит) дуга уграфа, не | (соответственно из <math>p</math> исходит) [[дуга]] уграфа, не | ||
принадлежащая <math>C</math>. Вершина <math>p</math> фрагмента <math>C</math> называется | принадлежащая <math>C</math>. Вершина <math>p</math> фрагмента <math>C</math> называется | ||
''входной'' (или ''входом''), если существует путь по уграфу | ''[[входная вершина фрагмента|входной]]'' (или ''[[вход|входом]]''), если существует путь по уграфу | ||
от его начальной вершины до <math>p</math>, не содержащий дуг <math>C</math>. | от его начальной вершины до <math>p</math>, не содержащий дуг <math>C</math>. | ||
Вершина <math>p</math> называется конечной для фрагмента <math>C</math>, если она | Вершина <math>p</math> называется конечной для фрагмента <math>C</math>, если она | ||
не принадлежит <math>C</math> и является преемником хотя бы одной его | не принадлежит <math>C</math> и является [[преемник вершины|преемником]] хотя бы одной его | ||
вершины. | вершины. | ||
Вершина <math>p</math> фрагмента <math>C</math>, отличная от начальной и конечной | Вершина <math>p</math> фрагмента <math>C</math>, отличная от начальной и конечной | ||
вершин уграфа, называется ''граничной'' вершиной <math>C</math>, если | вершин уграфа, называется ''[[граничная вершина фрагмента|граничной]]'' вершиной <math>C</math>, если | ||
<math>p</math> является начальной или выходной вершиной <math>C</math>. Граничная | <math>p</math> является начальной или выходной вершиной <math>C</math>. Граничная | ||
вершина <math>p</math> фрагмента <math>C</math> называется ''стартовой'', если в | вершина <math>p</math> фрагмента <math>C</math> называется ''[[стартовая вершина|стартовой]]'', если в | ||
нее не заходят дуги фрагмента <math>C</math> или из нее не исходят | нее не заходят дуги фрагмента <math>C</math> или из нее не исходят | ||
дуги, не принадлежащие <math>C</math>, и ''финишной'', если в нее | дуги, не принадлежащие <math>C</math>, и ''[[финишная вершина|финишной]]'', если в нее | ||
заходят лишь дуги фрагмента <math>C</math> или из нее не исходят дуги, | заходят лишь дуги фрагмента <math>C</math> или из нее не исходят дуги, | ||
принадлежащие <math>C</math>. | принадлежащие <math>C</math>. | ||
Фрагмент называется ''правильным'', если он имеет в точности две | [[Файл:Fragment.gif|700px]] | ||
граничные вершины, одна из которых | |||
финишная. Правильный фрагмент называется ''простым'', если он | |||
Фрагмент называется ''[[правильный фрагмент|правильным]]'', если он имеет в точности две | |||
граничные вершины, одна из которых — стартовая, а вторая — | |||
финишная. Правильный фрагмент называется ''[[простой фрагмент|простым]]'', если он | |||
содержит одну дугу. | содержит одну дугу. | ||
Правильный фрагмент, не являющийся простым, называется | Правильный фрагмент, не являющийся простым, называется | ||
''первичным'', если все его собственные правильные подфрагменты | ''[[первичный фрагмент|первичным]]'', если все его собственные правильные подфрагменты | ||
являются простыми. | являются простыми. | ||
См. также ''Альт, Гамак, Зона, Интервал, Линейная компонента, Линейный участок, Луч.'' | ==См. также == | ||
* ''[[Альт]],'' | |||
* ''[[Гамак]],'' | |||
* ''[[Зона]],'' | |||
* ''[[Интервал]],'' | |||
* ''[[Линейная компонента]],'' | |||
* ''[[Линейный участок]],'' | |||
* ''[[Луч]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
Текущая версия от 12:16, 29 сентября 2011
Фрагмент (Fragment) — любая часть уграфа. Фрагмент [math]\displaystyle{ C }[/math] является подфрагментом фрагмента [math]\displaystyle{ S }[/math], если [math]\displaystyle{ C }[/math] — часть [math]\displaystyle{ S }[/math]. Подфрагмент [math]\displaystyle{ C }[/math] фрагмента [math]\displaystyle{ S }[/math], отличный от [math]\displaystyle{ S }[/math], называется собственным подфрагментом.
Вершина [math]\displaystyle{ p }[/math] фрагмента [math]\displaystyle{ C }[/math] называется начальной (соответственно выходной), если либо [math]\displaystyle{ p }[/math] — начальная (соответственно конечная) вершина уграфа, либо в [math]\displaystyle{ p }[/math] заходит (соответственно из [math]\displaystyle{ p }[/math] исходит) дуга уграфа, не принадлежащая [math]\displaystyle{ C }[/math]. Вершина [math]\displaystyle{ p }[/math] фрагмента [math]\displaystyle{ C }[/math] называется входной (или входом), если существует путь по уграфу от его начальной вершины до [math]\displaystyle{ p }[/math], не содержащий дуг [math]\displaystyle{ C }[/math]. Вершина [math]\displaystyle{ p }[/math] называется конечной для фрагмента [math]\displaystyle{ C }[/math], если она не принадлежит [math]\displaystyle{ C }[/math] и является преемником хотя бы одной его вершины.
Вершина [math]\displaystyle{ p }[/math] фрагмента [math]\displaystyle{ C }[/math], отличная от начальной и конечной вершин уграфа, называется граничной вершиной [math]\displaystyle{ C }[/math], если [math]\displaystyle{ p }[/math] является начальной или выходной вершиной [math]\displaystyle{ C }[/math]. Граничная вершина [math]\displaystyle{ p }[/math] фрагмента [math]\displaystyle{ C }[/math] называется стартовой, если в нее не заходят дуги фрагмента [math]\displaystyle{ C }[/math] или из нее не исходят дуги, не принадлежащие [math]\displaystyle{ C }[/math], и финишной, если в нее заходят лишь дуги фрагмента [math]\displaystyle{ C }[/math] или из нее не исходят дуги, принадлежащие [math]\displaystyle{ C }[/math].
Фрагмент называется правильным, если он имеет в точности две
граничные вершины, одна из которых — стартовая, а вторая —
финишная. Правильный фрагмент называется простым, если он
содержит одну дугу.
Правильный фрагмент, не являющийся простым, называется первичным, если все его собственные правильные подфрагменты являются простыми.
См. также
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.