Главная /
Графы и алгоритмы /
Пусть [формула] - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
Пусть ![math]()
- список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
вопрос
- список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?Правильный ответ:
существует оптимальный каркас, содержащий ребро ![math]()
существует оптимальный каркас, содержащий оба ребра ![math]()
существует оптимальный каркас, содержащий все три ребра ![math]()
если ребра ![math]()
не образуют цикла, то существует оптимальный каркас, содержащий все эти ребра
не образуют цикла, то существует оптимальный каркас, содержащий все эти ребра Сложность вопроса
60
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
Экзамен прошёл на зачёт. спс
18 ноя 2016
Аноним
Какой человек ищет эти ответы интуит? Это же безумно легко
09 дек 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
- # Какие из следующих равенств выполняются для любых графов G1 и G2?
- # Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
- # Сколько имеется абстрактных двусвязных графов с 4 вершинами?
- # Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?