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

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

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

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

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

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

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

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

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

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

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

Сколько ребер нужно добавить к наибольшему паросочетанию графа $K_{2,5} + C_9$ , чтобы получить наименьшее реберное покрытие этого графа?

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

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

Сколько ребер нужно удалить из наименьшего реберного покрытия графа $K_{4,6} + K_7$ , чтобы получить наибольшее паросочетание этого графа?

Сколько ребер имеет граф пересечений граней трехмерного куба?