Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 4

Каков размер наименьшего MIS (максимального независимого набора) цепочки из девяти узлов?
(А) 5
(Б) 4
(С) 3
(D) 2

Ответ: (с)
Объяснение: Набор вершин называется независимым набором, так что никакие две вершины в наборе не являются смежными. Максимальный независимый набор (MIS) — это независимый набор, который не является подмножеством любого другого независимого набора.

Вопрос о самой маленькой MIS. Мы можем видеть на диаграмме ниже, три выделенные вершины (2-й, 5-й и 8-й) образуют максимальный независимый набор (не подмножество любой другой MIS) и наименьший MIS.

0----0----0----0----0----0----0----0----0

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

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

ВОРОТА | Gate IT 2008 | Вопрос 4

0.00 (0%) 0 votes