Фрагмент: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Фрагмент''' (''Fragment'') - любая часть уграфа. Фрагмент <math>C</math> является ''подф...)
 
Нет описания правки
Строка 1: Строка 1:
'''Фрагмент''' (''Fragment'') -  
'''Фрагмент''' (''[[Fragment]]'') -  
любая часть уграфа. Фрагмент <math>C</math> является  
любая часть [[уграф|уграфа]]. Фрагмент <math>C</math> является  
''подфрагментом'' фрагмента <math>S</math>, если <math>C</math> --- часть <math>S</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]

Навигация