Что означает C (n - 1, 2) ребер в теории графов? - Математика
0 голосов
/ 04 мая

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

Это, вероятно, верно, но меня смущает запись о том, что C(n - 1, 2) означает?

C обычно представляет цикл, но явно не в этом случае. И та функция r, на которую они ссылаются, принимает 2 параметра, что довольно странно.

1 Ответ

1 голос
/ 04 мая

Это биномиальный коэффициент $n-1$, выберите $2$, то есть $$\binom{n-1}{2},$$, что составляет $$\frac{(n-1)(n-2)}{2}.$$ В общем, $C(n,k)$ является альтернативной нотацией, используемой для r биномиального коэффициента $\binom{n}{k}$, который определяется как $$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

...