Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 23

Какое из следующих утверждений верно для каждого плоского графа на n вершинах?
(А) График связан
(B) граф эйлеров
(C) Граф имеет размер вершины не более 3n / 4
(D) График имеет независимый набор размеров не менее n / 3

Ответ: (с)
Объяснение: Планарный график — это график, который может быть нарисован на плане без пересечения пары ребер.

A) ЛОЖЬ: несвязный граф может быть плоским, поскольку он может быть нарисован на плоскости без пересечения ребер.

Б) ЛОЖЬ: Эйлерова диаграмма может быть или не быть плоской. Ненаправленный граф является эйлеровым, если все вершины имеют четную степень .

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

ВОРОТА | GATE CS 2008 | Вопрос 23

0.00 (0%) 0 votes