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

Материал из 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, является ее подпоследовательностью.

См. также

Литература

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