Проверочный тест к предыдущим лекциям

1. Дан взвешенный граф. Все веса ребер отрицательны. За какое время и каким алгоритмом можно найти максимальный по весу путь из A в B?
2. За какое время можно найти остовное дерево графа, в котором максимальный вес ребра минимален?
3. Задача. Даны N точек на плоскости, нужно соединить какие-то из них отрезками, так чтобы получился связный граф. Нужно минимизировать суммарную длину отрезков. Какой алгоритм лучше импользовать: Краскала или Прима?
4. Для каких весов ребер можно модифицировать поиск в ширину?
1. -1, 0
2. 0, 1
3. 1, 2
4. -1, 0, 1
5. 0, 1, 2
5. Задача. Дано число 0. За один ход. Можно прибавлять 2, можно 3. Сколько различных способов получить число N? Видите ли вы в этой задаче граф? За сколько в этом графе можно найти число путей из 0 в N?