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

'''Укладка уграфа''' (''[[Node listing]]'') -

отображение <math>F</math> множества целых чисел

<math>\{i : 1 \leq i \leq k\}</math> на множество [[вершина|вершин]] <math>V</math> [[уграф|уграфа]] <math>G</math>; <math>k</math>

называется ''длиной'' укладки.

Укладка уграфа <math>G</math> длины

<math>\mid V \mid</math> называется его ''обходом'';

обход представляет собой последовательность вершин [[граф|графа]],

перечисленных в порядке возрастания их номеров

в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа.

Укладка <math>F</math> называется ''сильной'', если любой [[простой путь]] <math>P</math>

по <math>G</math> является ее подпоследовательностью, т.е.

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

Укладка <math>F</math> называется ''слабой'', если любой такой

простой путь <math>P</math>

по <math>G</math>, из которого нельзя удалением некоторых [[внутренняя вершина|внутренних вершин]]

получить другой простой путь по <math>G</math>, является ее

подпоследовательностью.

''[[Базисная нумерация]], [[K-Нумерация|<math>K</math>-нумерация]], [[L-Нумерация|<math>L</math>-нумерация]], [[M-Нумерация|<math>M</math>-нумерация]], [[T-Нумерация|<math>T</math>-нумерация]], [[Обход графа]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]].''

[Касьянов/88],  

[Евстигнеев-Касьянов/94]