Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 3

Что из следующего является ИСТИННЫМ для любого простого связного неориентированного графа с более чем 2 вершинами?
(A) Нет двух вершин, имеющих одинаковую степень.
(B) По крайней мере две вершины имеют одинаковую степень.
(C) Как минимум три вершины имеют одинаковую степень.
(D) Все вершины имеют одинаковую степень.

Ответ: (Б)
Объяснение: Поскольку граф простой, не должно быть никаких петель и параллельных ребер.

Поскольку граф связен, степень любой вершины не может быть 0.

Следовательно, степень всех вершин должна быть от 1 до n-1. Так что степень как минимум двух вершин должна быть одинаковой.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2009 | Вопрос 3

0.00 (0%) 0 votes