В окне печати выберите «Сохранить как PDF», чтобы сохранить копию на своём устройстве.
1Формулы и методы
Теория графов
Лемма о рукопожатиях
Σ deg(v) = 2|E|
Полные графы
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Регулярный граф
|E| = n·k/2
Дерево и лес
|E| = n − 1, |E| = n − c
Листья дерева
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Эйлер
цикл: все степени чётные; путь: ровно две нечётные степени
Гамильтоновы циклы в Kn
(n − 1)!/2
Обновление в алгоритме Дейкстры
d(v) = min(d(v), d(u) + w(u, v))
Маршруты длины L
(Mᴸ)ij
Метод
Запишите степень каждой вершины; сумма степеней равна удвоенному числу рёбер.
В задачах об эйлеровых путях проверьте, что граф связный, и посчитайте вершины нечётной степени.
Для деревьев используйте n − 1 ребро и лемму о рукопожатиях.
В алгоритме Дейкстры ведите таблицу предварительных расстояний и на каждом шаге фиксируйте нефиксированную вершину с наименьшим расстоянием.
Для минимального остовного дерева отсортируйте рёбра по весу и пропускайте каждое ребро, замыкающее цикл (Краскал), либо растите одно дерево из начальной вершины (Прим).
2Тренировочные задачи
1.Алгоритмы и сложностьСредняя
Какова амортизированная временная сложность добавления элемента в конец динамического массива, который удваивает свою ёмкость при заполнении?
AO(n²)
BO(1)
CO(n)
DO(log n)
2.Алгоритмы и сложностьСложная
Почему алгоритм Дейкстры может давать неверные результаты, если некоторые веса рёбер отрицательны?
AОн работает только на неориентированных графах
BНа каждом отрицательном ребре он зацикливается
CВершина фиксируется при извлечении, но позже отрицательное ребро ещё может дать ей более короткий путь
DОтрицательные числа нельзя хранить в очереди с приоритетом
3.Структуры данныхСредняя
В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?
AДвоичная куча рёбер
BОдин отсортированный массив вершин
CСписки смежности
DМатрица смежности
4.Структуры данныхСложная
Вставка ключа в АВЛ-дерево делает левое поддерево узла слишком высоким, причём новый ключ попал в левое поддерево его левого потомка (случай левый–левый). Какое исправление применяется?
AЛевый поворот в потомке, затем правый поворот в узле
BОдиночный левый поворот в несбалансированном узле
CОдиночный правый поворот в несбалансированном узле
DПерекрашивание узла и его потомка
5.Теория графовСредняя
Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.
|V| = 5|E| = 7
1Эйлеров цикл
2Эйлеров путь, не цикл
3ни то, ни другое
6.Теория графовСложная
Сколько существует замкнутых маршрутов длины 2, начинающихся и заканчивающихся в E? Маршрут может повторять вершины и рёбра. Обозначим это число N.
M = матрица смежностиL = 2
N =
3Растворы
1.Алгоритмы и сложность
Ответ: B · O(1)
Почему это ответ
Копирование всех элементов происходит только на степенях двойки; если распределить эти затраты на все добавления, средняя стоимость одного добавления постоянна.
Ответ
B · O(1)
2.Алгоритмы и сложность
Ответ: C · Вершина фиксируется при извлечении, но позже отрицательное ребро ещё может дать ей более короткий путь
Почему это ответ
Жадный шаг опирается на неотрицательные веса, чтобы извлечённые расстояния были окончательными; когда веса могут быть отрицательными, применяют Беллмана–Форда.
Ответ
C · Вершина фиксируется при извлечении, но позже отрицательное ребро ещё может дать ей более короткий путь
3.Структуры данных
Ответ: C · Списки смежности
Почему это ответ
Матрице понадобилось бы 1010 ячеек, почти все пустые; списки смежности хранят лишь около 400 000 записей о рёбрах.
Ответ
C · Списки смежности
4.Структуры данных
Ответ: C · Одиночный правый поворот в несбалансированном узле
Почему это ответ
В случае левый–левый один правый поворот поднимает левого потомка вверх и восстанавливает баланс; случаи зигзага требуют двойного поворота.
Ответ
C · Одиночный правый поворот в несбалансированном узле
5.Теория графов
Ответ: Эйлеров путь, не цикл
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Эйлеров путь начинается в одной нечётной вершине и заканчивается в другой.
6.Теория графов
Ответ: N = 3
Степени: степень вершины — это число рёбер, которые в ней сходятся. У каждого ребра два конца, поэтому степени в сумме дают удвоенное число рёбер: Σ deg(v) = 2|E| (лемма о рукопожатиях). Следовательно, число вершин нечётной степени чётно. У Kn имеется n(n − 1)/2 рёбер, у k-регулярного графа на n вершинах nk/2, а у дерева на n вершинах n − 1 ребро.