Укладка уграфа

Укладка уграфа (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.