Рубрики

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

GATE

Обозначим через d минимальную степень вершины графа. Для всех плоских графов на n вершинах с d ≥ 3, какое из следующих утверждений ИСТИННО?
(A) В любом плоском вложении число граней не менее n / 2 + 2
(B) В любом плоском вложении число граней меньше n / 2 + 2
(C) Существует плоское вложение, в котором число граней меньше n / 2 + 2
(D) Существует плоское вложение, в котором число граней не больше n / (d + 1)

Ответ: (А)
Объяснение:

Euler's formula for planar graphs:

v − e + f = 2.

v → Number of vertices
e → Number of edges
f → Number of faces

Since degree of every vertex is at least 3, 
below is true from handshaking lemma (Sum of
degrees is twice the number of edges)

3v ≤ 2e
3v/2 ≤ e 
Putting these values in Euler's formula. 
v - 3v/2 + f ≥ 2 
f ≥ v/2 + 2

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

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

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

0.00 (0%) 0 votes