Укладка уграфа: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Укладка уграфа''' (''Node listing'') - отображение <math>F</math> множества целых чисел <ma...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 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>, является ее | |||
подпоследовательностью. | |||
См. также ''Базисная нумерация, <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>-нумерация]],'' | |||
* ''[[Обход графа]],'' | |||
* ''[[Правильная нумерация]],'' | |||
* ''[[Разумная нумерация]],'' | |||
* ''[[Топологическая сортировка]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. |
Текущая версия от 11:13, 22 сентября 2011
Укладка уграфа (Node listing) — отображение [math]\displaystyle{ \,F }[/math] множества целых чисел [math]\displaystyle{ \{i : 1 \leq i \leq k\} }[/math] на множество вершин [math]\displaystyle{ \,V }[/math] уграфа [math]\displaystyle{ \,G }[/math]; [math]\displaystyle{ \,k }[/math] называется длиной укладки.
Укладка уграфа [math]\displaystyle{ \,G }[/math] длины [math]\displaystyle{ \mid V \mid }[/math] называется его обходом; обход представляет собой последовательность вершин графа, перечисленных в порядке возрастания их номеров в некоторой нумерации вершин графа.
Укладка [math]\displaystyle{ \,F }[/math] называется сильной, если любой простой путь [math]\displaystyle{ \,P }[/math] по [math]\displaystyle{ \,G }[/math] является ее подпоследовательностью, т.е.
- [math]\displaystyle{ P=(F(i_1),F(i_2), \ldots,F(i_s)) }[/math]
для некоторых [math]\displaystyle{ 1\leq i_1 \lt i_2 \lt \ldots \lt i_s \leq k }[/math].
Укладка [math]\displaystyle{ \,F }[/math] называется слабой, если любой такой простой путь [math]\displaystyle{ \,P }[/math] по [math]\displaystyle{ \,G }[/math], из которого нельзя удалением некоторых внутренних вершин получить другой простой путь по [math]\displaystyle{ \,G }[/math], является ее подпоследовательностью.
См. также
- Базисная нумерация,
- [math]\displaystyle{ K }[/math]-нумерация,
- [math]\displaystyle{ L }[/math]-нумерация,
- [math]\displaystyle{ M }[/math]-нумерация,
- [math]\displaystyle{ T }[/math]-нумерация,
- Обход графа,
- Правильная нумерация,
- Разумная нумерация,
- Топологическая сортировка.
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.