Том 16, номер 5, 2009 г., Стр. 34-40
УДК 519.718
В. Г. Визинг
Об одной двухкритериальной задаче на графах
Аннотация:
Предполагается, что каждое ребро графа имеет две числовые характеристики — длину и ширину. Длиной подграфа называется сумма длин его рёбер, шириной подграфа — минимальная ширина его ребра. Длина подграфа является негативной характеристикой, ширина — позитивной. Подграфы определённого вида называются допустимыми. Рассматривается двухкритериальная задача отыскания оптимального по Парето допустимого подграфа.
Библиогр. 5.
Ключевые слова: допустимый подграф, индикатор качества подграфа, оптимальный по Парето подграф.
Визинг Вадим Георгиевич 1
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
е-mail: vizing@paco.net
Статья поступила 23 апреля 2009 г.
