Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 62

Упорядоченный n-кортеж (d1, d2,…, dn) с d1> = d2> = ⋯> = dn называется графическим, если существует простой неориентированный граф с n вершинами, имеющими степени d1, d2,…, dn соответственно. Какой из следующих 6 кортежей НЕ является графическим?
(А) (1, 1, 1, 1, 1, 1)
(В) (2, 2, 2, 2, 2, 2)
(С) (3, 3, 3, 1, 0, 0)
(D) (3, 2, 1, 1, 1, 0)

Ответ: (с)
Объяснение: Требуемый график невозможен с заданным набором степеней (3, 3, 3, 1, 0, 0). Используя этот 6-кортеж, сформированный граф будет представлять собой непересекающийся неориентированный граф, в котором две вершины графа не должны быть связаны с какой-либо другой вершиной (т. Е. Степень будет равна 0 для обеих вершин) графа. А для остальных 4 вершин граф должен удовлетворять степеням (3, 3, 3, 1).

Давайте посмотрим на это с помощью логической структуры графа: скажем, вершины, помеченные как, должны иметь свою степень соответственно.

Теперь E и F не должны быть связаны с какой-либо вершиной графа. А A, B, C и D должны иметь свою степень соответственно. Теперь, чтобы выполнить требования A, B и C, узел D никогда не сможет получить свою степень как 1. Его степень также станет равной 3. Это показано на диаграмме выше. Кортеж Hence не является графическим.

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

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

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 62

0.00 (0%) 0 votes