|
Доброго времени суток, подскажите пожалуйста, сколько имеется неориентированных графов с n вершинами, в которых допускаются петли? И сколько имеется ориентированных графов с n вершинами? В голове вертится формула 2n(n-1) задан 9 Ноя '20 1:26 
inna_2209
показано 5 из 9
показать еще 4
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
9 Ноя '20 1:26
показан
306 раз
обновлен
9 Ноя '20 4:03
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Если допускаются петли, то бесконечно много. Может быть одна петля, две, ... , "стопицот", ... :) Вопрос несколько нелепый.
Ориентированных графов с n вершинами также бесконечно много. Тут какая-то явная путаница. Может, речь об ориентированных рёбрах в таких графах? Тогда n(n-1), если без петель. Понятно ведь -- начло выбираем n способами, конец n-1 способом.
И первый вопрос, наверное, тоже был про рёбра в графе. Тогда ответ n(n+1)/2.
@falcao, я думаю, речь шла в обоих случаях про графы без атрибутов у ребер и дуг. То есть между двумя вершинами (возможно, совпадающими) может быть только одно ребро или одна дуга (в случае орграфа, естественно, может быть две дуги, направленные в разные стороны)
@haosfortum: даже если бы так было, задачу следовало сформулировать как следует. Вообще, количество простых графов на n вершинах -- это вещь очень сложная, такого спросить никто не мог.
@falcao да, действительно наверное подразумевалось в задании, что между вершинами может быть только одно ребро, но все же какая будет формула для определения числа графов, если для простого это 2^n(n-1)/2?
@falcao, думаю, граф имелся ввиду помеченный
@inna_2209, если я ничего не путаю, для учета существования петель нужно просто домножить на 2^n
@haosfortum, т.е. выйдет (2^n)^2? или же саму степень n(n-1)/2 умножить на 2^n?
@inna_2209: давайте сначала сформулируем условие как положено. Размеченные графы -- это совершенно отдельная задача. Если размеченный граф простой, то рёбер n(n-1)/2, и каждое или есть, или нет. Тогда ответ действительно 2^{n(n-1)/2}. Если можно добавлять петли к вершинам, но не более одной, то рёбер станет на n больше, и ответом будет 2^{n(n+1)/2}.
Не было сказано, что графы размеченные, а это важно. Не сказано и то, сколько петель разрешено добавлять к вершине. Если просто петли разрешены, то они в неограниченном количестве разрешены. В общем, надо следить за корректностью формулировок.
@inna_2209, не понимаю, как у Вас получилось (2^n)^2. Будет $%2^{n(n-1)/2}\cdot2^{n}$%