Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 10

Пусть G — простой связный плоский граф с 13 вершинами и 19 ребрами. Тогда число граней в плоском вложении графа равно
(А) 6
(Б) 8
(С) 9
(D) 13

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

рисунок ниже.

Формула Эйлера: для любого многогранника, который не пересекается (подключенный планарный граф),

• Количество лиц (F)
• плюс количество вершин (угловых точек) (V)
• минус количество ребер (E)
, всегда равно 2. Это можно записать: F + V — E = 2.

Решение :

Здесь, как дано, F = ?, V = 13 и E = 19
-> F + 13-19 = 2
-> F = 8

Таким образом, ответ (B).

Это решение предоставлено Nirmal Bharadwaj

Мы можем применить формулу Эйлера плоских графов . Формула имеет вид v — e + f = 2.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 10

0.00 (0%) 0 votes