Пути в неориентированных графах

Нам дан ненаправленный граф G = (V, E) и две вершины s, t ∈ V. Мы рассмотрим простые пути между s и t. Путь прост, если каждая вершина посещена не более одного раза.

Следующее в P или NP-завершено?

Существует ли эффективный алгоритм полиномиального времени для следующего?

«n» представляет количество вершин в графе «V»

  1. Существует ли простой путь от s до t длины не более n / 100?
  2. Существует ли простой путь от s до t длиной не менее n / 100?
  3. Существует ли простой путь от s до t длины ровно n / 100?
  4. Существуют ли два непересекающихся по краю пути от s до t? (Два пути называются ребро-непересекающимися, если они не имеют общего ребра.)

Мои мысли (пожалуйста, поправьте меня, если я ошибаюсь) Ваш вклад приветствуется.

  1. Я думаю, что могу запустить алгоритм Дейкстры, чтобы найти кратчайший путь между S и T за полиномиальное время. Так что вопрос 1 в П.
  2. Я думаю, что необходимо перечислить все простые пути от s до t. Я не знаю, каково будет время выполнения этого, но я думаю, что это будет хуже, чем полином.
  3. Аналогично 2 выше. Нет полиномиального алгоритма.
  4. Я не уверен. Я не знаю какого-либо эффективного (алгоритм поли-времени), чтобы найти несколько путей между двумя узлами, но это не значит, что они не существуют.
12.12.2008 07:21:35
«n» представляет количество вершин в графе V.
vinc456 12.12.2008 08:07:15
2 ОТВЕТА
РЕШЕНИЕ

Вы на правильном пути. Я написал еще одну статью о NP-complete, к которой я собираюсь отослать вас за некоторыми деталями, но помните, что в основном вам нужно сделать две вещи, чтобы доказать что-то NP-complete:

  1. Покажите проблему в НП
  2. Показать сокращение за полиномиальное время для задачи, которая уже известна как NP-полная.

Выполнить 1 довольно легко (если что-то ходя по графику «знает» все правильное решение следующего ребра, будет ли оно найти ответ за полиномиальное время?); Я бы серьезно подумал о проблеме «решения TSP», которую я описал в другой заметке.

1
23.05.2017 11:54:09
Я могу предположить, что если все проблемы либо P, либо NP-полны. Так что, если я не могу придумать алгоритм polytime, то могу предположить, что проблема NP-полная. Вы правы, но я надеюсь избежать сокращения, если это возможно.
vinc456 12.12.2008 08:01:05

Что я придумал:

  1. Как и вы сказали, используйте любой подходящий алгоритм SPP.
  2. Это самая длинная задача решения пути, которая является NP-Hard даже для невзвешенных графов.
  3. Для невзвешенных графиков для решения 2 достаточно линейного числа приложений, так что это также NP-Hard.
  4. Вы можете использовать алгоритмы максимального потока с единичной пропускной способностью, чтобы найти максимальное количество непересекающихся ребер.
0
8.01.2013 14:03:23