Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 17

Пусть G — простой неориентированный планарный граф на 10 вершинах с 15 ребрами. Если G связный граф, то число ограниченных граней в любом вложении G на плоскости равно
(А) 3
(Б) 4
(С) 5
(D) 6

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

v - e + f = 2
v is number of vertices
e is number of edges
f is number of faces including bounded and unbounded

10 - 15 + f = 2
f = 7
There is always one unbounded face, so the number of bounded faces =  6

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

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

ВОРОТА | GATE CS 2012 | Вопрос 17

0.00 (0%) 0 votes