задан 16 Июл '13 22:43

Нужна формула

(16 Июл '13 22:46) IviBring

Вершины занумерованы или нет?

(17 Июл '13 14:01) dmg3

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

(17 Июл '13 14:19) falcao
10|600 символов нужно символов осталось
2

Если под графом здесь подразумевается простой граф, не содержащий петель и кратных рёбер, а вершины считаются занумерованными, то таких (размеченных) графов имеется ровно $%2^{\frac{n(n-1)}2}$%.

Доказательство такое: рёбер в полном графе можно провести максимум $%\frac{n(n-1)}2$%, так как начало ребра выбирается $%n$% способами; при фиксированном начале конец ребра выбирается $%n-1$% способом, и в конце надо поделить на $%2$%, так как ребро неориентированное. Теперь занумеруем эти рёбра произвольным образом, и далее про каждое ребро последовательно решаем, проводить его в графе или не проводить. Это значит, что на каждом из шагов имеется $%2$% способа выбора, то есть в итоге получается $%2\cdot2\cdot\,\cdots\,\cdot2$%, где двойка берётся $%\frac{n(n-1)}2$% раз.

ссылка

отвечен 17 Июл '13 5:36

Спасибо большое!

(26 Июл '13 0:52) IviBring

А разве количество ребер простого графа не (n - 1)! ?

(9 Ноя '20 21:27) tr1ckster

@tr1ckster: факториал -- это огромное число, откуда так много рёбер возьмётся? Там начало ребра выбирается n способами, конец n-1 способом, и ещё делим на 2, так как AB и BA -- это одно и то же. У нас всего два этапа что-то задать, поэтому перемножаются два числа всего лишь.

Ответ (n-1)! получается, например, в задаче, сколькими способами n точек можно расположить по кругу.

(9 Ноя '20 22:12) falcao

А, все, согласен. Почему-то в тот момент я подумал, что факториал работает так: n! = n + (n - 1) + (n - 2) + ... + 1 :D

(10 Ноя '20 2:36) tr1ckster

Нет, факториал -- это произведение, а не сумма! Для суммы есть готовая формула (сумма членов арифметической прогрессии).

(10 Ноя '20 3:30) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×728

задан
16 Июл '13 22:43

показан
14476 раз

обновлен
10 Ноя '20 3:30

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

по почте:

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

по RSS:

Ответы

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

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