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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Укладка уграфа''' (''[[Node listing]]'') — отображение <math>\,F</math> множества целых чисел
'''Укладка уграфа''' (''[[Node listing]]'', ''[[Node seguence]]'') — отображение <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> называется ''длиной'' укладки.


Строка 5: Строка 5:
обход представляет собой последовательность вершин [[граф|графа]], перечисленных в порядке возрастания их номеров в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа.
обход представляет собой последовательность вершин [[граф|графа]], перечисленных в порядке возрастания их номеров в некоторой ''[[нумерация вершин|нумерации вершин]]'' графа.


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


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


Строка 30: Строка 30:


* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
<nowiki>[[Категория:Потоковый анализ программ]]</nowiki>

Версия от 08:45, 5 ноября 2024

Укладка уграфа (Node listing, Node seguence) — отображение [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], является ее подпоследовательностью.

См. также

Литература

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


[[Категория:Потоковый анализ программ]]