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

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

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

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

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

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

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

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

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

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

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

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

Дан граф

с множеством ребер

. Для каких из перечисленных ниже семейств $\Phi$ подмножеств множества

пара $(E,\Phi )$ является матроидом для любого графа

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

Чему равно число вершинного покрытия графа $P_3 \times P_4$ ?

В графе с весовой функцией

строится каркас с помощью алгоритма Крускала. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

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

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

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