Рубрики

UGC-NET | UGC NET CS 2016 Июль — II | вопрос 2

Количество различных связующих деревьев в полном графе K 4 и двудольном графе K 2,2 имеет ______ и _______ соответственно.
(А) 14, 14
(Б) 16, 14
(С) 16, 4
(D) 14, 4

Ответ: (с)
Объяснение: Покрывающие деревья в полном графе равны n (n-2) (где n — это отсутствие сторон или регулярности в полном графе).
Таким образом, связующие деревья в полном графе K 4 будут 4 (4 — 2) .
т.е. 4 2 = 16.
Остовные деревья в двудольном графе K m, n равны m (n-1) * n (m-1) .
Таким образом, связующие деревья в K 2,2 будут 2 (2-1) * 2 (2-1) .
т.е. 2 1 * 2 1. = 4.
Таким образом, вариант (C) является правильным.
Тест на этот вопрос

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

UGC-NET | UGC NET CS 2016 Июль — II | вопрос 2

0.00 (0%) 0 votes