Том 5, серия 1, номер 3, 1998 г., Стр. 70-79
УДК 519.717
Ф. В. Фомин
Затраты на поиск и графы интервалов
Аннотация:
Рассматривается задача поиска на графах убегающего командой преследователей. В статье определяется новый критерий оптимальности поиска – затраты на поиск. Доказывается, что для всякого графа$G$ затраты на поиск равны числу ребер в наименьшем (по числу ребер) графе интервалов, содержащем$G$ в качестве подграфа.
Библиогр. 17.
Фомин Ф. В. 1
1. Санкт-Петербургский государственный университет, мех.-мат. факультет,
Библиотечная пл., 2, 198904 Санкт-Петербург, Россия
е-mail: fomin@gamma.math.spbu.ru
Статья поступила 6 февраля 1998 г.
