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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''Укладка уграфа''' (''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) - отображение F множества целых чисел \{i : 1 \leq i \leq k\} на множество вершин V уграфа G; k называется длиной укладки.

Укладка уграфа G длины \mid V \mid называется его обходом; обход представляет собой последовательность вершин графа, перечисленных в порядке возрастания их номеров в некоторой нумерации вершин графа.

Укладка F называется сильной, если любой простой путь P по G является ее подпоследовательностью, т.е.

P=(F(i_1),F(i_2), \ldots,F(i_s))

для некоторых 1\leq i_1 < i_2 < \ldots < i_s \leq k.

Укладка F называется слабой, если любой такой простой путь P по G, из которого нельзя удалением некоторых внутренних вершин получить другой простой путь по G, является ее подпоследовательностью.

См. также

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

Литература

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

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