Затраты на поиск и графы интервалов

Рассматривается задача поиска на графах убегающего командой преследователей. В статье определяется новый критерий оптимальности поиска – затраты на поиск. Доказывается, что для всякого графа $G$ затраты на поиск равны числу ребер в наименьшем (по числу ребер) графе интервалов, содержащем $G$ в качестве подграфа. Библиогр. 17.