0
1

Дано число N. Требуется найти число двудольных графов на N вершинах в предположении, что ответ можно найти по рекурсивной формуле. Причём сложность алгоритма нахождения O(N^3).

задан 31 Мар '16 4:13

Графы рассматриваются с точностью до изоморфизма, или как размеченные? То есть надо уточнить формулировку задачи.

(31 Мар '16 5:53) falcao

Как размеченные.

Ну то есть что-то вроде следующего: Пусть даны номера вершин, а также ребра графа. Тогда мы будем считать граф двудольным, если проверка на двудольность подтвердит, что граф двудольный.

(31 Мар '16 12:17) Overload

Так Вам надо проверить граф на двудольность (в этом случае применяется очень простой алгоритм раскраски в два цвета), или же надо найти число таких графов? Это две совсем разные задачи, они как-то плохо сочетаются.

(31 Мар '16 17:37) falcao

Нет, надо найти число. Я просто описал то, когда мы считаем граф двудольным.

(1 Апр '16 2:27) Overload

@Overload: хорошо, тогда давайте сделаем окончательное уточнение. Правильно ли я понимаю, что при N=2 у нас имеется 2 варианта, а при N=3, когда вершины пронумерованы, годятся все размеченные графы кроме треугольного, и ответом будет число 7 (один граф без рёбер, три с 1 ребром, и три с двумя рёбрами)?

(1 Апр '16 2:53) falcao

Не совсем. Вот сама последовательность: https://oeis.org/A033995

(1 Апр '16 16:04) Overload

@Overload: это значит, что Вам нужно подсчитать число двудольных графов с точностью до изоморфизма. Такие вещи, как правило, подсчитать очень сложно, и о простых рекуррентных формулах не может быть и речи. Для случая размеченных графов всё гораздо проще. Вот ссылка на статью, где найдена производящая функция, но она очень непростая.

Может быть, Вы имели в виду, что за время O(N^3) нужно вычислить N-й член данной последовательности?

(1 Апр '16 17:23) falcao

Да, именно так. Сложность вычисления должна быть O(N^3)

(1 Апр '16 21:46) Overload
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×379
×133
×78

задан
31 Мар '16 4:13

показан
434 раза

обновлен
1 Апр '16 21:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru