Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 38

Рассмотрим набор U из 23 различных соединений в химической лаборатории. Существует подмножество S из U из 9 соединений, каждое из которых реагирует ровно с 3 соединениями U. Рассмотрим следующие утверждения:

I.  Each compound in U \ S reacts with an odd number of compounds.
II.  At least one compound in U \ S reacts with an odd number of compounds.
III.  Each compound in U \ S reacts with an even number of compounds. 

Какое из приведенных выше утверждений ВСЕГДА ИСТИННО?

(А) только я
(Б) Только II
(С) только III
(D) нет

Ответ: (Б)
Пояснение: Ответ B. Это вопрос теории графов.

«/» — операция установки разности. То же, что и U — S.

Так как U универсальное множество, U / S даст дополнение S = S '
Пусть S содержит соединения с номерами {1,2,3… 8, 9}, поэтому U / S содержит соединения {10, 11, 12…. 22, 23}

Считайте эти соединения вершинами графа.
Ребро ч / б двух вершин указывает на то, что соединения реагируют друг с другом.

Этот график не имеет множественных краевых причин, что не имеет смысла.
Направленных граней нет, потому что если одно соединение реагирует с другим, это также означает, что и другое реагирует с ним. Один край представляет собой реакцию ч / б обоих.
У него НЕТ Петель, потому что соединение не реагирует само с собой.

Следовательно, граф — это простой неориентированный граф.

Мы знаем, что «неориентированный граф имеет четное число вершин нечетной степени»

9 вершин этого графика имеют степень 3 (нечетная степень), потому что 9 соединений реагируют с 3 другими соединениями.
Следовательно, должна быть как минимум еще 1 вершина, которая должна иметь нечетную степень.
Это дополнительное соединение должно принадлежать U / S, поскольку 9 соединений в S уже учтены.
Это означает, что утверждение II в этом вопросе — ИСТИНА.

Другие 2 утверждения являются ложными.
Утверждение III. Учтите, что все 9 соединений в S реагируют с теми же 3 соединениями в U / S, что и {20, 21, 22}, следовательно, все соединения в U / S реагируют либо с нулем, либо с 9 соединениями, но не с четным числом.
Точно так же утверждение I может быть доказано неправильно, визуализируя график.

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

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 38

0.00 (0%) 0 votes