Блог пользователя tomcat

Electricity
Автор tomcat, 13 лет назад, По-русски

Однажды у нас на тренировке была такая задача: дан ориентированный граф без циклов, задается множество ребер, у которых нужно поменять направление. Известно, что если у всех этих ребер поменять направление, то сохранится ацикличность. Нужно так выбрать порядок изменения направлений, чтобы ни на каком шаге не появился цикл. Вершин до 1000, ребер до 10000.

Буду признателен тому, кто подскажет идею решения. Сам пока додумался только до того, что на каждом шаге имеет смысл менять направление только у того ребра, у которого нужно его поменять в итоге.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Я придумал просто реализуемое решение за O(NM) (N - количество вершин, M - количество ребер).

Алгоритм следующий.
1. Рассмотрим любую топологическую сортировку исходного графа. (У каждой вершины есть какой-то номер в этой сортировке.)
2. Рассмотрим то ребро (из тех, у которых надо поменять направление), у которого разность номеров вершин в топологической сортировке минимальна.
3. Развернем это ребро, также поменяем эти две вершины местами в текущей топологической сортировке.
4. Пока остались ребра, которые надо развернуть, повторим шаг 2 (для уже новой топологической сортировки).

Нужно только доказать, что после шага 3 топологическая сортировка остается корректной. Это можно доказать от противного.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Допустим у нас есть граф: { (1, 2), (1,4), (2,3), (2,4) } и нам нужно развернуть всего одно ребро: (2,4). Следуя пункту 3, после его разворота мы должны поменять и номера вершин. После этого из вершины 4 будет идти ребро в вершину 3, т.е. топологическая сортировка не сохранится.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мда. Нужно было изложить свое доказательство от противного и найти в нем баг :)
      Сейчас попробую что-нибудь исправить.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Ну если подобная последовательность всегда существует, тогда можно просто на каждом шагу менять ребро так, чтобы инвариант ацикличности сохранился. Если же этого не сказано в условии, то надо либо доказать это, либо думать над другим решением :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Ну, для этого нужно еще найти ребро, у которого можно изменить направление. Собственно, в моем решении критерий - минимальная разность номеров в топологической сортировке.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Про существование решения ничего не сказано. Мне кажется, что решения не существует только в том случае, когда есть два кратных ребра одного направления и их направления надо поменять.

    Мне не понятно, как быстро на каждом шаге выбирать ребро, при изменении направления у которого не появится цикл.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

      Вроде можно доказать, что если нет двух кратных ребер, которые нужно развернуть, то решение существует.

      Схема доказательства (наверное можно проще):
      Отсортируем ребра, которые нужно развернуть (например, по их номеру) и каждый раз будем разворачивать первое неразвернутое ребро. Для очередного ребра возможны 2 случая:

      1) После его разворота цикл не образуется. Тогда просто разворачиваем его и идем дальше.
      2) После его разворота образуется цикл. Очевидно, что в таком случае в цикле есть ребро, которое находится не в своем конечном состоянии (т.е. еще должно быть развернуто). Рекурсивно повторим алгоритм для этого ребра, а только потом изменим текущее. Так как длина цикла больше 2, то при развороте этого ребра (и всех рекурсивных вызовах из него) мы не получим этот же самый цикл, если рекурсивно не придем к этому же самому начальному ребру.

      Но если мы к нему придем, тогда взяв последовательность ребер в рекурсии и объединив циклы, которые образуются при их развороте мы получим один цикл, который не содержит ни одного из них, что значит что в изначальном графе был цикл.

      Отсюда получаем, что каждое ребро будет разворачиваться ровно один раз, т.е. количество шагов конечно.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Вот я плюсанул, но меня всё равно что-то в этом доказательстве как-то коробило. Думал-думал и понял, что именно. Дело в том, что если мы вдруг в рекурсии приходим к какому-то ребру, на которое уже смотрели, и потом объединяем все получавшиеся циклы (в смысле, как я понял, с вычёркиванием совсем тех рёбер, которые в k циклов входят в одном положении и в k же - в перевёрнутом), то неочевидно, почему вдруг не может получиться "цикл" из нуля рёбер. А это значит, неочевидно, что цикл длины два является особым случаем.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Цикл длины 2 является особым, так как мы сразу же вернемся в него, не заходя в другие циклы.

          Насчет цикла из нуля ребер. Мы рассматриваем самый первый раз, когда вернулись из какого-то ребра в него же. Ребра мы рассматриваем изначальные, т.е. пока мы никаких разворотов не делали. Получившийся цикл можно явно выписать.

          Первая вершина цикла - это начало нашего ребра из которого мы стартовали. Вторая - это начало ребра, принадлежащего циклу, который образуется при развороте начальной в которое мы перейдем рекурсивно. И так далее.

          Этот цикл будет нулевой длины только в случае, если все начальные вершины таких ребер совпадают. Но тогда у них не совпадают конечные вершины (циклов длины 2 же нет), а они тоже образуют цикл.
          → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        ignore
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

          Не вижу цикла, который образуется при развороте левого горизонтального черного ребра.

          А насчет цикличности - так я как раз показал, что ее не будет.

          UPD: относится к предыдущей правке.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, действительно, моя ошибка, похоже Вы правы и доказательство верно.
            → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ну, это очевидно, что она существует не всегда. Вот, например, граф из двух вершин и двух ребёр, оба ребра направлены от одной вершины к другой, а надо их оба перевернуть. А никак. А если такого случая быть не может, то пускай топикстартер поточнее сформулирует условие - тогда подумаем, есть ли контрпримеры без кратных рёбер.
    P.S. А, ну, собственно, он сам меня уже и опередил :)
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Собственно реализация алгоритма, описанного в первом комментарии, за ассимптотику O(NM) тривиальна. Посчитаем разности номеров для всех ребер, запомним минимальную разность. При обмене двух вершин нужно обновить разности не более 2N ребер, минимальная разность при этом может измениться.
→ Ответить