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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Укладка уграфа''' (''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]

Навигация