Я пытаюсь решить вопрос ниже от tardos.Будем благодарны за любые предложения или помощь.
Вы были вызваны, чтобы помочь некоторым сетевым администраторам диагностировать степень сбоя в их сети.Сеть предназначена для передачи трафика от назначенного исходного узла s к назначенному целевому узлу t, поэтому мы будем моделировать его как ориентированный граф G = (V, E), в котором емкость каждого ребра равна 1, и в которомкаждый узел лежит хотя бы на одном пути от s до t.
Теперь, когда в сети все работает гладко, максимальный st-поток в G имеет значение k.Однако текущая ситуация - и причина, по которой вы здесь - состоит в том, что злоумышленник уничтожил некоторые ребра в сети, так что теперь нет пути от s до t с использованием оставшихся (выживших) ребер.По причинам, которые мы не будем здесь вдаваться, они считают, что атакующий уничтожил только k ребер, минимальное количество, необходимое для отделения s от t (т. Е. Размер минимального st-разреза);и мы будем считать, что они верят в это.Сетевые администраторы запускают пул мониторинга на узле s, который имеет следующее поведение: если вы введете команду ping (v) для данного узла v, он сообщит вам, существует ли в настоящее время путь от s до v. (Таким образом, pint (t) сообщает, что в настоящее время пути не существует, с другой стороны, ping (s) всегда сообщает путь от s к себе.) Поскольку не практично выходить на улицу и проверять каждый край сети, они хотели быопределить степень сбоя с помощью этого инструмента мониторинга с помощью разумного использования команды ping.Итак, вот проблема, с которой вы столкнулись: дать алгоритм, который выдает последовательность команд ping различным узлам в сети, а затем сообщает полный набор узлов, которые в настоящее время недоступны из s.Конечно, вы могли бы сделать это, пропингуя каждый узел в сети, но вы хотели бы сделать это, используя намного меньше пингов (учитывая предположение, что были удалены только k ребер).Выпуская эту последовательность, ваш алгоритм может решить, какой узел пинговать дальше, на основе результатов предыдущих операций пинга.Приведите алгоритм, который выполняет эту задачу, используя только O (k log n) пингов.