Перебор графов

[cyb12]

Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать? Какие есть параллельные алгоритмы?
Подскажите.

[rederblack]

cyb12 в сообщении #489821 писал(а):

Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать? Какие есть параллельные алгоритмы?
Подскажите.

Генетические алгоритмы. Тут http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf есть пример построения графа переходов. Посмотрите другие источники тоже http://is.ifmo.ru/genalg/. Такой способ можно сделать параллельным.

А так сложно еще что-то предложить. Для чего вам нужно перебирать все возможные графы? Граф должен решать какую-то задачу? Или нужно выдать все виды структур? Например, с помощью ГА можно решить задачу коммивояжёра.

[Maslov]

rederblack в сообщении #489846 писал(а):

Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать?

Погуглите "перечисление графов" -- может быть, найдете что-нибудь полезное.

(Оффтоп)

rederblack в сообщении #489846 писал(а):

Например, с помощью ГА можно решить задачу коммивояжёра.

Все зависит от того, какой смысл Вы вкладываете в слово "решить". ГА не позволяют в общем случае найти оптимальный маршрут, но довольно часто с их помощью можно за разумное время найти маршрут со стоимостью, близкой к минимальной.

[bin]

Генерация графов широко применяется во многих прикладных областях, например, в математической (компьютерной) химии. Сошлюсь на свою статью: М.Трофимов, Е.Смоленский, Изв.РАН, Сер.хим., 2005, N 9, 2166-2176. Там в приложениях приведен ряд алгоритмов для генерации и даны ссылки на их источники (например, много полезных алгоритмов было предложено Фараджевым). В принципе, сгенерировать все возможные графы, казалось бы, не трудно: взять очень большое число, уменьшать его на единицу, представлять результат в двоичном коде, цифрами из которого заполнять матрицу смежности соответствующего размера. Однако при такой генерации будут повторятся изоморфные графы. В статье была цель испытать новый алгоритм изоморфизма, поэтому повторы удалялись с помощью этого алгоритма, но бывают генераторы, которые генерируют поток графов с заданными свойствами. Кроме того, для некоторых задач совсем не нужно генерировать графы, а нужно только сосчитать, сколько будет каких-то определенных графов. Тут также есть полезные подходы.

Hope it helps!

[cyb12]

rederblack в сообщении #489846 писал(а):

Граф должен решать какую-то задачу?

Нужна именно структура графа. Тут немного странно.

2Maslov
Перечисление графов - это обычно вещи, связанные с производящими функциями, которые позволяют сосчитать число графов определенного типа.

(Оффтоп)

Там, кстати, столько всего найдено, вплоть до перечисления кактусов

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

Например, мне нужно перебрать все графы (не обязательно исключать все изоморфные) на $n$ вершинах. Конечно, их много. Даже очень. Пусть у меня есть $p$ процессоров. Если делать совсем "в лоб", то приходится фиксировать некоторые подграфы (не более чем $p$ способами) и давать каждому процессору перебирать графы со своим подграфом.
Можно ли проще?

[Maslov]

cyb12 в сообщении #490262 писал(а):

Если делать совсем "в лоб", то приходится фиксировать некоторые подграфы (не более чем $p$ способами) и давать каждому процессору перебирать графы со своим подграфом.
Можно ли проще?

Не надо привязываться к числу физических ядер. Даже в случае, когда количество параллельных веток алгоритма на два порядка больше количества процессоров, автоматическая диспетчеризация параллельных задач выполняется достаточно эффективно (в теме Язык программирования для математика проверяли на Erlang/C++/C#).