1184
правки
Укладка уграфа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Укладка уграфа''' (''[[Node listing]]'') — отображение <math>\,F</math> множества целых чисел | '''Укладка уграфа''' (''[[Node listing]]'', ''[[Node seguence]]'') — отображение <math>\,F</math> множества целых чисел | ||
<math>\{i : 1 \leq i \leq k\}</math> на множество [[вершина|вершин]] <math>\,V</math> [[уграф|уграфа]] <math>\,G</math>; <math>\,k</math> называется ''длиной'' укладки. | <math>\{i : 1 \leq i \leq k\}</math> на множество [[вершина|вершин]] <math>\,V</math> [[уграф|уграфа]] <math>\,G</math>; <math>\,k</math> называется ''длиной'' укладки. | ||
| Строка 5: | Строка 5: | ||
обход представляет собой последовательность вершин [[граф|графа]], перечисленных в порядке возрастания их номеров в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа. | обход представляет собой последовательность вершин [[граф|графа]], перечисленных в порядке возрастания их номеров в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа. | ||
Укладка <math>\,F</math> называется ''сильной'', если любой [[простой путь]] <math>\,P</math> | Укладка <math>\,F</math> называется ''[[Сильная укладка графа|сильной]]'', если любой [[простой путь]] <math>\,P</math> | ||
по <math>\,G</math> является ее подпоследовательностью, т.е. | по <math>\,G</math> является ее подпоследовательностью, т.е. | ||
| Строка 13: | Строка 13: | ||
<math>1\leq i_1 < i_2 < \ldots < i_s \leq k</math>. | <math>1\leq i_1 < i_2 < \ldots < i_s \leq k</math>. | ||
Укладка <math>\,F</math> называется ''слабой'', если любой такой простой путь <math>\,P</math> | Укладка <math>\,F</math> называется ''[[Слабая укладка графа|слабой]]'', если любой такой простой путь <math>\,P</math> | ||
по <math>\,G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]] получить другой простой путь по <math>\,G</math>, является ее подпоследовательностью. | по <math>\,G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]] получить другой простой путь по <math>\,G</math>, является ее подпоследовательностью. | ||
| Строка 30: | Строка 30: | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | * Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | ||
<nowiki>[[Категория:Потоковый анализ программ]]</nowiki> | |||