Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 36

Пусть G — полный неориентированный граф на 6 вершинах. Если вершины группы G помечены, то число различных циклов длины 4 в G равно
(А) 15
(Б) 30
(С) 45
(D) 360

Ответ: (с)
Пояснение: может быть всего 6 C 4 способов выбрать 4 вершины из 6. Значение 6 C 4 равно 15.

Обратите внимание, что данный граф является полным, поэтому любые 4 вершины могут образовывать цикл.

Может быть 6 разных циклов с 4 вершинами. Например, рассмотрим 4 вершины как a, b, c и d. Три отдельных цикла

циклы должны быть такими
(а, б, в, д, а)
(а, б, г, в, а)
(а, с, б, д, а)
(a, c, d, b, a)
(а, д, б, в, а)
(a, d, c, b, a)

и

(a, b, c, d, a) и (a, d, c, b, a)
(a, b, d, c, a) и (a, c, d, b, a)
(a, c, b, d, a) и (a, d, b, c, a)
одинаковые циклы.

Таким образом, общее количество отдельных циклов (15 * 3) = 45.

** ПРИМЕЧАНИЕ **: В оригинальном вопросном документе GATE 45 вариант не предлагался. Вместо 45 было 90.

Тест на этот вопрос

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

ВОРОТА | GATE CS 2012 | Вопрос 36

0.00 (0%) 0 votes