Гамак: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) (Создана новая страница размером '''Гамак''' (Hammock) --- альт, множество ''конечных'' вершин ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
'''Гамак''' ([[Hammock]]) | [[Файл:Hammock.png|300px|right]] | ||
и не являющейся [[Предшественник| | '''Гамак''' (''[[Hammock]]'') — [[альт]], множество [[Конечная вершина Фрагмента|конечных]] вершин которого либо пусто, либо состоит из единственной вершины, являющейся преемником каждой [[Выходная вершина Фрагмента|выходной]] вершины [[Альт|альта]] и не являющейся [[Предшественник вершины|предшественником]] | ||
его [[Начальная вершина| | его [[Начальная вершина Фрагмента|начальной]] вершины. | ||
Гамак называется [[Разложимый гамак |''разложимым'']], если его можно представить как | Гамак называется [[Разложимый гамак |''разложимым'']], если его можно представить как | ||
| Строка 8: | Строка 8: | ||
называется [[Составной гамак |''составным'']]. | называется [[Составной гамак |''составным'']]. | ||
См. также [[Иерархия вложенных альтов]]. | |||
== См. также == | |||
* [[Иерархия вложенных альтов]]. | |||
== Литература == | == Литература == | ||
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
Текущая версия от 12:56, 2 декабря 2010
Гамак (Hammock) — альт, множество конечных вершин которого либо пусто, либо состоит из единственной вершины, являющейся преемником каждой выходной вершины альта и не являющейся предшественником его начальной вершины.
Гамак называется разложимым, если его можно представить как объединение двух непересекающихся гамаков, и неразложимым (или простым) в противном случае. Максимальный разложимый гамак называется составным.
См. также
Литература
- Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.