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

Материал из WikiGrapp
Перейти к:навигация, поиск

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