Укладка уграфа: различия между версиями
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] | ||
Версия от 17:50, 7 февраля 2010
Укладка уграфа (Node listing) - отображение [math]\displaystyle{ F }[/math] множества целых чисел [math]\displaystyle{ \{i : 1 \leq i \leq k\} }[/math] на множество вершин [math]\displaystyle{ V }[/math] уграфа [math]\displaystyle{ G }[/math]; [math]\displaystyle{ k }[/math] называется длиной укладки.
Укладка уграфа [math]\displaystyle{ G }[/math] длины [math]\displaystyle{ \mid V \mid }[/math] называется его обходом; обход представляет собой последовательность вершин графа, перечисленных в порядке возрастания их номеров в некоторой нумерации вершин графа.
Укладка [math]\displaystyle{ F }[/math] называется сильной, если любой простой путь [math]\displaystyle{ P }[/math] по [math]\displaystyle{ G }[/math] является ее подпоследовательностью, т.е.
[math]\displaystyle{ P=(F(i_1),F(i_2), \ldots,F(i_s)) }[/math]
для некоторых [math]\displaystyle{ 1\leq i_1 \lt i_2 \lt \ldots \lt i_s \leq k }[/math].
Укладка [math]\displaystyle{ F }[/math] называется слабой, если любой такой простой путь [math]\displaystyle{ P }[/math] по [math]\displaystyle{ G }[/math], из которого нельзя удалением некоторых внутренних вершин получить другой простой путь по [math]\displaystyle{ G }[/math], является ее подпоследовательностью.
См. также
Базисная нумерация, [math]\displaystyle{ K }[/math]-нумерация, [math]\displaystyle{ L }[/math]-нумерация, [math]\displaystyle{ M }[/math]-нумерация, [math]\displaystyle{ T }[/math]-нумерация, Обход графа, Правильная нумерация, Разумная нумерация, Топологическая сортировка.
Литература
[Касьянов/88],
[Евстигнеев-Касьянов/94]