Графы и алгоритмы

К графу 2C₅ применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

(Отметьте один правильный вариант ответа.)

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

4(Верный ответ)

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

Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K₃?

Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C₄ ?

Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу P_n(без предварительной проверки четности степеней)?

Сколько листьев будет в дереве путей, построенном для графа K_4,4?

Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Поиск в ширину применяется к графу $P_3 \times P_3$ . Какой будет высота BFS-дерева?

Поиск в глубину применяется к графу $K_2 \times O_4$ . Какова будет высота DFS-дерева?