Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 8

Пусть G произвольный граф с n узлами и k компонентами. Если вершина удаляется из G, число компонентов в результирующем графе должно обязательно лежать между
(А) к и п
(B) k — 1 и k + 1
(С) k — 1 и n — 1
(D) k + 1 и n — k

Ответ: (с)
Объяснение: Минимум: удаленная вершина сама является отдельным связанным компонентом. Таким образом, удаление вершины создает компоненты k-1.

Максимум: возможно, что удаленная вершина отключит все компоненты. Например, удаленная вершина является центром звезды. Таким образом, удаление создает n-1 компонентов.

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

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

ВОРОТА | GATE-CS-2003 | Вопрос 8

0.00 (0%) 0 votes