Cтраница 1
Функционалы приоритета (1.4) и (1.5) для указанных целевых функционалов построены У. В [149] показано, в частности, что к этой задаче сводится ряд известных экстремальных задач на подстановках. TVP-трудность этой задачи ( даже при 6i н) - При dt 0, 6, t i ее решение получено С. Беллма-ном, основано на методе динамического программирования. При указанных условиях задача известна в литературе как задача 2 Xп Беллмана - Джонсона. [1]
Пусть новый функционал приоритета построен для всех перестановок длины т, 2 тп. [2]
Значение функционала приоритета, соответствующее данной метке вершины i, называем значением этой метки. [3]
Для отыскания функционала приоритета докажем предварительно одно вспомогательное утверждение. [4]
Q-3 существует его автоограниченный: функционал приоритета. [5]
Теорема 6.2. Пусть G GipG2 и функционал приоритета является автоограниченным. Для того чтобы граф G был приводимым, необходимо и достаточно, чтобы графы G. [6]
Аналогичным образом можно убедиться, что и остальные функционалы приоритета, построенные в пп. [7]
Теорема 6.3. Любой последовательно-параллельный граф G является приводимым при автоограниченном функционале приоритета. [8]
Из теоремы 6.3 следует, что D-алгоритм позволяет получать оптимальную перестановку при любом автоограниченном функционале приоритета и любом последовательно-параллельном графе G. Вместе с тем нетрудно привести примеры, в которых граф G не является последовательно-параллельным, но при данном конкретном функционале приоритета / - алгоритм переводит его в цепь. Накладывая определенные ограничения на пару функционал приоритета - граф G, можно описывать более широкие ( по сравнению с последовательно-параллельными графами) классы разрешимых ситуаций. Рассмотрим один из таких классов. [9]
Отметим, что построение для данного конкретного прио-ритето-порождающего функционала F ( n) функционала приоритета, который не был бы автоограниченным, требует определенной изобретательности. В то же время все известные функционалы приоритета ( см. § 1 данной главы) являются автоограниченными. [10]
Любая ы-цепъ определяется перестановкой номеров ее вершин, в которой вершины упорядочены по невозрастанию соответствующих им значений функционала приоритета. [11]
Лемма 6.4. Пусть G GtpG2, последовательность L преобразований I, II переводит граф G в граф G и функционал приоритета является автоограниченным. [12]
Лемма 6.5. Пусть G GipGi, последовательность L преобразований I, II переводит граф G в граф G и функционал приоритета является автоограниченным. [13]
Лемма 6.3. Пусть G GipG2, последовательность L преобразований I, II, содержащая единственное смешанное преобразование I, переводит граф G в граф G, и функционал приоритета является автоограниченным. [14]
Лемма 6.2. Пусть G GipG2, последовательность L преобразований I, II, в которой все преобразования I однородны, переводит граф G в граф G - ( N, U) и функционал приоритета является автоограниченным. [15]