Том 18, номер 5, 2011 г., Стр. 3-10

УДК 519.718
Визинг В. Г.
Многокритериальные задачи на графах с максиминным критерием

Аннотация:
Рассматриваются r-критериальные задачи для r-взвешенных графов (r ≥ 2). Подграфы определённого вида называются допустимыми. Решение задачи состоит в выборе оптимального по Парето допустимого подграфа из полного множества альтернатив (ПМА). Основной результат состоит в следующем. Предположим, что один из критериев, обозначаемый MAXMIN, требует максимизации минимального первого веса рёбер допустимого подграфа и имеется эффективная процедура, строящая ПМА для (r − 1)-критериальной задачи без этого максиминного критерия. Тогда эффективно строится ПМА для исходной r-критериальной задачи.
Библиогр. 11.

Ключевые слова: допустимый подграф, индикатор качества подграфа, оптимальный по Парето подграф.

Визинг Вадим Георгиевич ¹
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
е-mail: vizing@paco.net

Статья поступила 17 мая 2011 г.

Литература

[1] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. — 536 c.

[2] Визинг В. Г. Об одной двухкритериальной задаче на графах // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 5. — С. 34–40.

[3] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990. — 384 с.

[4] Емеличев В. А., Перепелица В. А. Многокритериальные задачи об остовах графа // Докл. АН СССР. — 1988. — Т. 298, № 3. — С. 544–547.

[5] Емеличев В. А., Перепелица В. А. Сложность дискретных многокритериальных задач // Дискрет. математика. — 1994. — Т. 6, вып. 1. — С. 3–33.

[6] Зыков А. А. Основы теории графов. — М.: Вуз. кн., 2004. — 663 с.

[7] Кофман А. Введение в теорию нечётких множеств. — М.: Радио и связь, 1982. — 432 с.

[8] Сергиенко И. В., Перепелица В. А. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах // Кибернетика. — 1987. — № 5. — С. 85–93.

[9] Emelichev V. A., Perepeliza V. A. Complexity of vector optimization problems on graphs // Optimization. — 1991. — Vol. 22, N 6. — P. 903–918.

[10] Kruskal J. B. Jr. On the shortest spanning subtree of a graph and the traveling salesman problem // Proc. Amer. Math. Soc. — 1956. — Vol. 7, N 1. — P. 48–50.

[11] Prim R. C. Shortest connection networks and some generalizations // Bell Syst. Techn. — 1957. — Vol. 36. — P. 1389–1401.