Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

Пусть G — связный плоский граф с 10 вершинами. Если число ребер на каждой грани равно трем, то число ребер в G равно _______________.
(А) 24
(Б) 20
(С) 32
(D) 64

Ответ: (А)
Пояснение: Формула Эйлера гласит, что если конечный связный плоский граф рисуется на плоскости без каких-либо пересечений ребер, то

    v − e + f = 2.  
    v -> Number of vertices
    e -> Number of edges
    f -> Number of faces

As per the question 
v = 10
And number of edges on each face is three
Therefore, 2e = 3f  [Note that every edge is
                    shared by 2 faces]

Putting above values in v − e + f = 2
10 - e + 2e/3 = 2
e = 3*10 - 6 = 24

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

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

0.00 (0%) 0 votes