Главная /
Графы и алгоритмы /
Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
вопросПравильный ответ:
степени вершин не превосходят 2
нет циклов нечетной длины
каждая компонента связности - цепь
каждая компонента связности - цикл четной длины или цепь.
Сложность вопроса
61
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
просто спасибо
18 июн 2020
Аноним
Какой человек находит эти вопросы по интуит? Это же совсем для даунов
25 июн 2016
Аноним
Экзамен сдан на зачёт. Спасибо за ответы
20 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
- # Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
-
#
Сколько ребер нужно удалить из наименьшего реберного покрытия графа
![math]()
, чтобы получить наибольшее паросочетание этого графа?
- # В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
- # Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
, чтобы получить наибольшее паросочетание этого графа?