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

Количество простых цепей в полном графе
Автор birne, 11 лет назад, По-русски

Добрый день! Возникли проблемы с решением следующей задачи. Пусть задан полный граф, в котором содержится n вершин. Найти количество простых цепей длины 1, 2, ..., n — 1 между парой вершин в этом графе. Наверняка какое-то квадратное ДП, но пока ничего придумать не смог. Заранее спасибо!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если под цепью понимается путь, то это NP-сложная задача. Может быть имеются в виду любые пути, а не только простые? Или ограничения 20 :)

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    В случае произвольного графа это точно так, ибо к этой задаче сводится задача существования гамильтонового пути. Неужели для полного графа тоже всё так плохо? Не могу с ходу доказать NP-сложность этой задачи.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Извиняюсь, я не заметил что граф полный. Тогда, действительно, ответ — A(n-2, k-2) или C(n, 2) * A(n-2, k-2), в зависимости от понимания условия.

      → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится +10 Проголосовать: не нравится

    Граф же полный. Простая цепь длины k в этом случае это количество способов выбрать промежуточные вершины цепи. Что-то типа C(n-2, k-2)
    UPD. Вершины надо упорядочить, так что это размещения, а не сочетания: A(n-2, k-2)

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да уж, про комбинаторику-то я и забыл. Спасибо!

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Все вышенаписаное относиться к неориентированному полному графу. Мне интересно, а для ориентированного это NP-полная задача?

→ Ответить