Доброго времени суток, подскажите пожалуйста, сколько имеется неориентированных графов с n вершинами, в которых допускаются петли? И сколько имеется ориентированных графов с n вершинами? В голове вертится формула 2n(n-1)

задан 9 Ноя '20 1:26

Если допускаются петли, то бесконечно много. Может быть одна петля, две, ... , "стопицот", ... :) Вопрос несколько нелепый.

Ориентированных графов с n вершинами также бесконечно много. Тут какая-то явная путаница. Может, речь об ориентированных рёбрах в таких графах? Тогда n(n-1), если без петель. Понятно ведь -- начло выбираем n способами, конец n-1 способом.

И первый вопрос, наверное, тоже был про рёбра в графе. Тогда ответ n(n+1)/2.

(9 Ноя '20 2:11) falcao

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

(9 Ноя '20 3:25) haosfortum

@haosfortum: даже если бы так было, задачу следовало сформулировать как следует. Вообще, количество простых графов на n вершинах -- это вещь очень сложная, такого спросить никто не мог.

(9 Ноя '20 3:36) falcao

@falcao да, действительно наверное подразумевалось в задании, что между вершинами может быть только одно ребро, но все же какая будет формула для определения числа графов, если для простого это 2^n(n-1)/2?

(9 Ноя '20 3:43) inna_2209

@falcao, думаю, граф имелся ввиду помеченный

(9 Ноя '20 3:48) haosfortum

@inna_2209, если я ничего не путаю, для учета существования петель нужно просто домножить на 2^n

(9 Ноя '20 3:52) haosfortum

@haosfortum, т.е. выйдет (2^n)^2? или же саму степень n(n-1)/2 умножить на 2^n?

(9 Ноя '20 3:59) inna_2209

@inna_2209: давайте сначала сформулируем условие как положено. Размеченные графы -- это совершенно отдельная задача. Если размеченный граф простой, то рёбер n(n-1)/2, и каждое или есть, или нет. Тогда ответ действительно 2^{n(n-1)/2}. Если можно добавлять петли к вершинам, но не более одной, то рёбер станет на n больше, и ответом будет 2^{n(n+1)/2}.

Не было сказано, что графы размеченные, а это важно. Не сказано и то, сколько петель разрешено добавлять к вершине. Если просто петли разрешены, то они в неограниченном количестве разрешены. В общем, надо следить за корректностью формулировок.

(9 Ноя '20 4:01) falcao

@inna_2209, не понимаю, как у Вас получилось (2^n)^2. Будет $%2^{n(n-1)/2}\cdot2^{n}$%

(9 Ноя '20 4:03) haosfortum
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×646

задан
9 Ноя '20 1:26

показан
306 раз

обновлен
9 Ноя '20 4:03

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

по почте:

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

по RSS:

Ответы

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

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