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

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

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

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

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

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

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

Если под графом здесь подразумевается простой граф, не содержащий петель и кратных рёбер, а вершины считаются занумерованными, то таких (размеченных) графов имеется ровно $%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
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×338

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

показан
4984 раза

обновлен
26 Июл '13 0:52

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

по почте:

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

по RSS:

Ответы

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

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