Пути в неориентированных графах - PullRequest
Новая
       10

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

2 голосов
/ 12 декабря 2008

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

Следуют ли следующие данные в P или NP-complete?

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

"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. Я не уверен. Я не знаю ни одного эффективного (алгоритма поли-времени) для поиска нескольких путей между двумя узлами, но это не значит, что их не существует.

Ответы [ 2 ]

1 голос
/ 12 декабря 2008

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

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

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

0 голосов
/ 08 января 2013

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

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