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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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> является ее подпоследовательностью, т.е.


<math>P=(F(i_1),F(i_2), \ldots,F(i_s))</math>  
:::::<math>P=(F(i_1),F(i_2), \ldots,F(i_s))</math>  


для некоторых
для некоторых
<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>\,F</math> называется ''слабой'', если любой такой простой путь <math>\,P</math>
простой путь <math>P</math>
по <math>\,G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]] получить другой простой путь по <math>\,G</math>, является ее подпоследовательностью.
по <math>G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]]
получить другой простой путь по <math>G</math>, является ее
подпоследовательностью.


==См. также ==
==См. также ==
''[[Базисная нумерация]], [[K-Нумерация|<math>K</math>-нумерация]], [[L-Нумерация|<math>L</math>-нумерация]], [[M-Нумерация|<math>M</math>-нумерация]], [[T-Нумерация|<math>T</math>-нумерация]], [[Обход графа]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]].''
* ''[[Базисная нумерация]],''
* ''[[K-Нумерация|<math>K</math>-нумерация]],''
* ''[[L-Нумерация|<math>L</math>-нумерация]],''
* ''[[M-Нумерация|<math>M</math>-нумерация]],''
* ''[[T-Нумерация|<math>T</math>-нумерация]],''
* ''[[Обход графа]],''
* ''[[Правильная нумерация]],''
* ''[[Разумная нумерация]],''
* ''[[Топологическая сортировка]].''
==Литература==
==Литература==
[Касьянов/88],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

Навигация