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

Материал из WikiGrapp
Перейти к:навигация, поиск
 
Строка 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.

Текущая версия на 11:13, 22 сентября 2011

Укладка уграфа (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, является ее подпоследовательностью.

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.