Фрагмент уграфа: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Фрагмент''' (''Fragment'') - любая часть уграфа. Фрагмент <math>C</math> является ''подф...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Фрагмент''' (''Fragment'') - | '''Фрагмент''' (''[[Fragment]]'') - | ||
любая часть уграфа. Фрагмент <math>C</math> является | любая часть [[уграф|уграфа]]. Фрагмент <math>C</math> является | ||
''подфрагментом'' фрагмента <math>S</math>, если <math>C</math> | ''[[подфрагмент|подфрагментом]]'' фрагмента <math>S</math>, если <math>C</math> - часть <math>S</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>. | ||
Фрагмент называется ''правильным'', если он имеет в точности две | Фрагмент называется ''[[правильный фрагмент|правильным]]'', если он имеет в точности две | ||
граничные вершины, одна из которых | граничные вершины, одна из которых - стартовая, а вторая - | ||
финишная. Правильный фрагмент называется ''простым'', если он | финишная. Правильный фрагмент называется ''[[простой фрагмент|простым]]'', если он | ||
содержит одну дугу. | содержит одну дугу. | ||
Правильный фрагмент, не являющийся простым, называется | Правильный фрагмент, не являющийся простым, называется | ||
''первичным'', если все его собственные правильные подфрагменты | ''[[первичный фрагмент|первичным]]'', если все его собственные правильные подфрагменты | ||
являются простыми. | являются простыми. | ||
См. также ''Альт, Гамак, Зона, Интервал, Линейная компонента, Линейный участок, Луч.'' | ==См. также == | ||
''[[Альт]], [[Гамак]], [[Зона]], [[Интервал]], [[Линейная компонента]], [[Линейный участок]], [[Луч]].'' | |||
==Литература== | ==Литература== | ||
[Касьянов/88], | [Касьянов/88], | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||
Версия от 12:50, 22 марта 2010
Фрагмент (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].
Фрагмент называется правильным, если он имеет в точности две
граничные вершины, одна из которых - стартовая, а вторая -
финишная. Правильный фрагмент называется простым, если он
содержит одну дугу.
Правильный фрагмент, не являющийся простым, называется первичным, если все его собственные правильные подфрагменты являются простыми.
См. также
Альт, Гамак, Зона, Интервал, Линейная компонента, Линейный участок, Луч.
Литература
[Касьянов/88],
[Евстигнеев-Касьянов/94]