Разработка алгоритма нахождения длины простого цикла в d-регулярном графе

введите здесь описание изображения

Я понимаю вопрос в целом, но не знаю, как разработать и проанализировать алгоритм в вопросе. Я думал применить какой-то алгоритм поиска по графу, например поиск в глубину / в ширину.

ОБНОВЛЕНИЕ: это то, что я пробовал, начиная с любого узла графа (назовите его N), посещать каждого из d соседей этого узла. Теперь, последний сосед N, которого мы только что посетили (назовем его L), посетит любого другого соседа L, который не является N?


algorithm graph-traversal graph-theory
person Mutating Algorithm    schedule 07.12.2015    source источник
comment
Я бы начал с добавления ссылки на обычный график (en.wikipedia.org/wiki/Regular_graph < / а>). Кроме того, что вы пробовали? Что произойдет, если вы начнете с узла и начнете случайным образом перемещаться по графу? Почему это не сработает - и как это исправить?   -  person shapiro yaacov    schedule 07.12.2015
comment
Вот несколько идей, которые могут быть (косвенно) полезными: в компоненте может быть не более n (n-1) / 2 ребер, а в лесу (совокупность деревьев) - не более n-1 ребер. В d-регулярном графе мы можем думать о каждой вершине, дающей d / 2 ребра в общее количество (поскольку каждое ребро инцидентно 2 вершинам).   -  person j_random_hacker    schedule 07.12.2015
comment
Что такое простой цикл длины N? Это список узлов, содержащий N записи. Поскольку это цикл, первый и последний узел одинаковы. Поскольку это простой цикл, все узлы между ними отличаются от первого и друг от друга. Итак, вам нужно найти маршруты N-1 long, где все узлы разные, а затем есть соединение от последнего узла к первому, замыкая цикл.   -  person biziclop    schedule 07.12.2015
comment
@biziclop Я думал об этом несколько минут, но все еще не могу придумать решение. Я понимаю, что вы имеете в виду под простым циклом.   -  person Mutating Algorithm    schedule 07.12.2015
comment
Я бы, наверное, начал с чего-нибудь простого, например, d=1. В этом случае проблема сводится к нахождению какого-либо цикла. Так что же происходит, когда d=2?   -  person biziclop    schedule 07.12.2015
comment
@biziclop: Я думаю, что вопрос заключается в том, чтобы попросить OP придумать какой-то алгоритм, который использует структуру d-regular, чтобы работать лучше, чем алгоритм грубой силы, который вы предлагаете в своем первом комментарии. Например. при d = 1 циклов быть не может; для d = 2 могут быть только (непересекающиеся) циклы.   -  person j_random_hacker    schedule 08.12.2015
comment
Если подумать об этом немного подробнее, то можно сказать, что алгоритм на самом деле во многих отношениях довольно прост (а также быстр в выполнении), но шаги, необходимые для доказательства того, что он всегда работает, сложны! Подсказка: есть 2 фазы. На первом этапе вы находите путь длиной n + 1 (вам нужно доказать, что алгоритм всегда может это сделать (подсказка: возврат с возвратом не требуется)); на втором этапе вы продолжаете расширять этот путь, пока должны (это включает в себя доказательство того, что вы всегда можете сделать либо одно из двух, и что этот процесс завершается).   -  person j_random_hacker    schedule 08.12.2015
comment
@j_random_hacker Да, я имел в виду это только как отправную точку, стиль карандаша и бумаги.   -  person biziclop    schedule 08.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Остальные уже намекали на возможное решение в комментариях, давайте уточним. Когда d<=1, решения будут немедленными (и зависят от вашего точного определения цикла), поэтому я предполагаю d>1.

Один из таких алгоритмов:

  1. Постройте путь, начинающийся в любой вершине V. Пока путь не станет длиной d, не допускайте вершин, которые вы уже посетили.
  2. Как только путь станет длиной d вершин, продолжайте добавлять вершины к пути, но теперь допускайте только вершины, отличные от последних d вершин пути.
  3. Когда вы добавляете вершину, которая уже использовалась в пути, остановитесь. Вы создаете результирующий цикл из сегмента пути, начинающегося и заканчивающегося в этой вершине.

И в (1), и в (2) существование такой вершины гарантируется тем, что G d-регулярна. При поиске добавляемой вершины мы исключаем только последние d вершины, а именно последнюю вершину (U) и ее d-1 предшественников. U имеет d соседей, поэтому должен быть доступен хотя бы один из них.

Алгоритм остановится из-за условия (3) и того факта, что G конечна.

Имеет смысл предпочесть уже посещенные вершины в (2), но это не меняет сложность наихудшего случая.

Это дает нам наихудшую сложность n*d, поскольку нам, возможно, придется посетить каждую вершину и проверить все ее ребра.

person voidengine    schedule 17.12.2015