Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 90

Сколько существует графов на n помеченных вершинах, которые имеют не менее (n 2 — 3n) / 2 ребер?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (D)
Объяснение:

Пусть будет общее число ребер графа, который должен быть сформирован, равным e, а общее число вершин — n .

Таким образом, общее количество способов построения графа, имеющих ровно e ребер и v вершин, определяется общим количеством способов, которыми мы можем выбрать e ребер среди v ребер.

т.е.

C (v, e)

Теперь здесь e = (n 2   — 3n) / 2 и v = n (n-1) / 2 (максимальное число ребер в простом графе) .

Таким образом, чтобы выбрать ребро, мы можем сделать это в C (v, (n 2   — 3н) / 2) способов.

Так как минимум нет. ребер, которые должны быть выбраны для графа (n 2   — 3n) / 2.

Таким образом, общее количество возможных графиков будет:

C (v, e) + C (v, e + 1) + C (v, e + 2) + …………… + C (v, v).

C (v, ve) + C (v, v- (e + 1)) + C (v, v- (e + 2)) + …………… + C (v, vv).

Поскольку v — e = n (n-1) / 2 — (n 2 — 3n) / 2 = n

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 90

0.00 (0%) 0 votes