4624
правки
Фрагмент уграфа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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] | ||