4624
правки
Фрагмент уграфа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> исходит) [[дуга]] уграфа, не | ||
| Строка 30: | Строка 28: | ||
Фрагмент называется ''[[правильный фрагмент|правильным]]'', если он имеет в точности две | Фрагмент называется ''[[правильный фрагмент|правильным]]'', если он имеет в точности две | ||
граничные вершины, одна из которых | граничные вершины, одна из которых — стартовая, а вторая — | ||
финишная. Правильный фрагмент называется ''[[простой фрагмент|простым]]'', если он | финишная. Правильный фрагмент называется ''[[простой фрагмент|простым]]'', если он | ||
содержит одну дугу. | содержит одну дугу. | ||
| Строка 39: | Строка 37: | ||
==См. также == | ==См. также == | ||
''[[Альт]], [[Гамак]], [[Зона]], [[Интервал]], [[Линейная компонента]], [[Линейный участок]], [[Луч]].'' | * ''[[Альт]],'' | ||
* ''[[Гамак]],'' | |||
* ''[[Зона]],'' | |||
* ''[[Интервал]],'' | |||
* ''[[Линейная компонента]],'' | |||
* ''[[Линейный участок]],'' | |||
* ''[[Луч]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||