Укладка уграфа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Укладка уграфа''' (''Node listing'') - отображение <math>F</math> множества целых чисел <ma...)
 
Нет описания правки
Строка 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]