Алгоритмы: построение и анализ

<<- Назад к вопросам

Что известно про минимальное контролирующее множество в двудольном графе?

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

его мощность не меньше мощность максимального паросочетания(Верный ответ)

его мощность не больше мощность максимального паросочетания(Верный ответ)

его мощность может быть меньше мощности максимального паросочетания

его мощность может быть больше мощности максимального паросочетания

Похожие вопросы

Какова сложность алгоритма нахождения минимального контролирующего множества в двудольном графе?

Пусть в графе G пять разных минимальных покрывающих деревьев. Вова загодал K - одно из них. Пятя знает граф G но не знает какое минимальное покрывающее дерево, которое загадал Петя. Какие утверждения верны?

Нулевым позициям в графе игры Ним соответствуют

Если в графе степень всех вершин равна двум, то

Какое множество вершин называется контролирующим?

Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)

Пусть A и B два максимальных покрывающих дерева в графе G. Какое утверждение верно?

Пусть A и B два минимальных покрывающих дерева в графе G. Какое утверждение верно?