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

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

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

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

добавление новой вершины и ребер, соединяющих ее со всеми "старыми" вершинами(Верный ответ)

удаление ребра

добавление нового ребра

удаление вершины(Верный ответ)

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

Какое наименьшее число ребер нужно добавить к графу K_3,3, чтобы превратить его в хордальный?

Какие из следующих графов изоморфны графу $\overline {C_5 }$ ?

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

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

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

Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?

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

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

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

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