Question

Количество неориентированных графов с n вершинами равно(формула)

Answer 1

Эту формулу очень просто получить.

Всего в графе из $n$ вершин мы можем провести $C_n^2=\dfrac{n(n-1)}{2}$ ребер. Но, конечно, некоторые (или даже все эти) ребра могут отсутствовать. То есть мы для каждого потенциального ребра делаем выбор: действительно включать его в граф или нет.

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

Answer 2

Количество неориентированных графов с n вершинами можно выразить с помощью формулы:

2^(C(n, 2))

где C(n, 2) - число сочетаний из n по 2, или биномиальный коэффициент "n по 2". Это количество способов выбрать 2 вершины из n для построения ребра.

Выражение 2^(C(n, 2)) означает, что каждое ребро может присутствовать или отсутствовать в графе, то есть у каждого ребра есть 2 возможных состояния (присутствует или отсутствует), и для n(n-1)/2 ребер всего существует 2^(n(n-1)/2) комбинаций состояний.

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