Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 37

Каково количество вершин в неориентированном связном графе с 27 ребрами, 6 вершинами степени 2, 3 вершинами степени 4 и оставшимися степени 3?
(А) 10
(Б) 11
(С) 18
(D) 19

Ответ: (D)
Пояснение: Идея состоит в том, чтобы использовать лемму Handshaking : — В любом графе сумма всех степеней вершины равна удвоенному числу ребер.

Let x = Total Number of Vertices.

By Handshaking Lemma

6*2 + 3*4 + (x-9)*3 = 27*2

24 + (x-9)*3 = 54

x-9 = 10

x = 19 

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

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

ВОРОТА | GATE-IT-2004 | Вопрос 37

0.00 (0%) 0 votes