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

1. Правда ли, что 3n² = Θ(logN^{2logN/loglogN})?
2. Даны 3 условия: отсутствие отрицательных ребер, отсутствие отрицательных циклов, все веса единичные
1. Какое из 3-х условий нужно Декйстре?
2. Какое из 3-х условий нужно Форду-Беллману?
3. Какое из 3-х условий нужно Поиску в ширину?
3. За сколько работает Форд-Беллман с очередью на графе с единичными весами ребер?
4. Сколько памяти в битах нужно для хранения матрицы смежности ориентированного графа из N вершин?
5. Можно ли с помощью алгоритма Дейстры определить, есть ли в графе отрицательный цикл? как?
6. Можно ли с помощью алгоритма Форда-Беллмана определить, есть ли в графе отрицательный цикл? как?