Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 13

Минимальное количество цветов, достаточное для окраски вершин любого плоского графа, составляет _______________

[Этот Вопрос изначально был Вопросом Заполнить Пробелы]
(А) 1
(Б) 2
(С) 3
(D) 4

Ответ: (D)
Объяснение: Планарный граф — это граф на плоскости, в котором нет двух ребер, пересекающих друг друга.

Набор областей карты может быть представлен более абстрактно как неориентированный граф, который имеет вершину для каждой области и ребро для каждой пары областей, которые имеют граничный сегмент. Следовательно, здесь применяется теорема о четырех цветах.

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 13

0.00 (0%) 0 votes