Если под графом здесь подразумевается простой граф, не содержащий петель и кратных рёбер, а вершины считаются занумерованными, то таких (размеченных) графов имеется ровно $%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 falcao Спасибо большое!
(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
|
Нужна формула
Вершины занумерованы или нет?
@aapetrov3: если графы рассматривать с точностью до изоморфизма, то получается заведомо сложная задача, которую в общем виде вряд ли корректно было бы предлагать (разве что для небольших значений $%N$%). Там ответ известен лишь асимптотически. Коль скоро ставится вопрос о формуле, то должно иметься в виду число размеченных графов.