4625
правок
Укладка уграфа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Укладка уграфа''' (''Node listing'') - отображение <math>F</math> множества целых чисел <ma...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Укладка уграфа''' (''Node listing'') - | '''Укладка уграфа''' (''[[Node listing]]'') - | ||
отображение <math>F</math> множества целых чисел | отображение <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> | ||
называется ''длиной'' укладки. | называется ''длиной'' укладки. | ||
Укладка уграфа <math>G</math> длины | Укладка уграфа <math>G</math> длины | ||
<math>\mid V \mid</math> называется его ''обходом''; | <math>\mid V \mid</math> называется его ''обходом''; | ||
обход представляет собой последовательность вершин графа, | обход представляет собой последовательность вершин [[граф|графа]], | ||
перечисленных в порядке возрастания их номеров | перечисленных в порядке возрастания их номеров | ||
в некоторой ''нумерации вершин'' графа. | в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа. | ||
Укладка <math>F</math> называется ''сильной'', если любой простой путь <math>P</math> | Укладка <math>F</math> называется ''сильной'', если любой [[простой путь]] <math>P</math> | ||
по <math>G</math> является ее подпоследовательностью, т.е. | по <math>G</math> является ее подпоследовательностью, т.е. | ||
| Строка 20: | Строка 20: | ||
Укладка <math>F</math> называется ''слабой'', если любой такой | Укладка <math>F</math> называется ''слабой'', если любой такой | ||
простой путь <math>P</math> | простой путь <math>P</math> | ||
по <math>G</math>, из которого нельзя удалением некоторых внутренних вершин | по <math>G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]] | ||
получить другой простой путь по <math>G</math>, является ее | получить другой простой путь по <math>G</math>, является ее | ||
подпоследовательностью. | подпоследовательностью. | ||
См. также ''Базисная нумерация, <math>K</math>-нумерация, <math>L</math>-нумерация, <math>M</math>-нумерация, <math>T</math>-нумерация, Обход графа, Правильная нумерация, Разумная нумерация, Топологическая сортировка.'' | ==См. также == | ||
''[[Базисная нумерация]], [[K-Нумерация|<math>K</math>-нумерация]], [[L-Нумерация|<math>L</math>-нумерация]], [[M-Нумерация|<math>M</math>-нумерация]], [[T-Нумерация|<math>T</math>-нумерация]], [[Обход графа]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]].'' | |||
==Литература== | ==Литература== | ||
[Касьянов/88], | [Касьянов/88], | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||