Рубрики

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

Пусть G простой граф с 20 вершинами и 100 ребрами. Размер минимального покрытия вершин G равен 8. Тогда размер максимального независимого множества G равен
(А) 12
(Б) 8
(С) Менее 8
(D) более 12

Ответ: (А)
Объяснение: Справочная информация Объяснение:
Покрытие вершины — это множество S вершин графа, такое, что каждое ребро графа инцидентно хотя бы одной вершине S.
Независимый набор графа — это набор вершин, такой, что ни одна из вершин в этом наборе не имеет ребра, соединяющего их, то есть никакие две не являются смежными. Отдельная вершина является независимым множеством, но нас интересует максимальное независимое множество, то есть наибольшее множество, которое является независимым множеством.

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

Так что, если S — размер минимального покрытия вершин G (V, E), то размер
максимального независимого множества G есть | V | — С.

Решение:
размер минимального покрытия вершин = 8
размер максимального независимого набора = 20 — 8 = 12
Следовательно, правильный ответ (А).

Ссылки :
покрытие вершины
максимально независимый набор .

Это решение предоставлено Nitika Bansal.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes