|
Дано число N. Требуется найти число двудольных графов на N вершинах в предположении, что ответ можно найти по рекурсивной формуле. Причём сложность алгоритма нахождения O(N^3). задан 31 Мар '16 4:13 
Overload
показано 5 из 8
показать еще 3
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
31 Мар '16 4:13
показан
1042 раза
обновлен
1 Апр '16 21:46
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Графы рассматриваются с точностью до изоморфизма, или как размеченные? То есть надо уточнить формулировку задачи.
Как размеченные.
Ну то есть что-то вроде следующего: Пусть даны номера вершин, а также ребра графа. Тогда мы будем считать граф двудольным, если проверка на двудольность подтвердит, что граф двудольный.
Так Вам надо проверить граф на двудольность (в этом случае применяется очень простой алгоритм раскраски в два цвета), или же надо найти число таких графов? Это две совсем разные задачи, они как-то плохо сочетаются.
Нет, надо найти число. Я просто описал то, когда мы считаем граф двудольным.
@Overload: хорошо, тогда давайте сделаем окончательное уточнение. Правильно ли я понимаю, что при N=2 у нас имеется 2 варианта, а при N=3, когда вершины пронумерованы, годятся все размеченные графы кроме треугольного, и ответом будет число 7 (один граф без рёбер, три с 1 ребром, и три с двумя рёбрами)?
Не совсем. Вот сама последовательность: https://oeis.org/A033995
@Overload: это значит, что Вам нужно подсчитать число двудольных графов с точностью до изоморфизма. Такие вещи, как правило, подсчитать очень сложно, и о простых рекуррентных формулах не может быть и речи. Для случая размеченных графов всё гораздо проще. Вот ссылка на статью, где найдена производящая функция, но она очень непростая.
Может быть, Вы имели в виду, что за время O(N^3) нужно вычислить N-й член данной последовательности?
Да, именно так. Сложность вычисления должна быть O(N^3)