4624
правки
Фрагмент: различия между версиями
Материал из WikiGrapp
нет описания правки
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. | |||
