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

Материал из WikiGrapp
Версия от 11:13, 22 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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