|
Сколько существует графов с N вершинами и M ребрами? (обыкновенных графов) задан 29 Июн '14 2:00 
ssh |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
29 Июн '14 2:00
показан
2478 раз
обновлен
29 Июн '14 3:09
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Надо уточнить постановку вопроса. Если речь идёт о классификации графов с точностью до изоморфизма, то там возможны подсчёты только для малых значений. А если имеются в виду размеченные графы, то тогда всё достаточно просто.
Я думаю, что речь идет о числе графов с точностью до изоморфизма. Но, если не сложно, поясните для обоих случаев.
Для размеченных графов (когда все вершины пронумерованы) всё определяется количеством рёбер, соединяющих вершины с данными номерами. Тогда подсчёт производится совсем просто. Но если речь идёт вообще о числе попарно неизоморфных графов с заданным числом вершин, то это сложная задача, и в общем виде она решена только приближённо. См. здесь.