ВОРОТА | GATE-CS-2006 | Вопрос 72

2 ⁿ вершин графа G соответствуют всем подмножествам множества размера n при n> = 6. Две вершины графа G смежны тогда и только тогда, когда соответствующие множества пересекаются ровно в двух элементах.

Максимальная степень вершины в G:
(А) (н / 2) С2 * 2 ^{н / 2}
(Б) 2 ^н-2
(С) 2 ^н-3 * 3
(D) 2 ^н-1

Ответ: (с)
Пояснение: max _k (kC2 * 2 ^(n-k) ) = 3C2 * 2 ^(n-3) = 3 * 2 ^(n-3) .
Тест на этот вопрос

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65