Font size
WorksheetsГрафы Все темы
Total questions: 15
Worksheet time: 10mins
Теория графов - обширный раздел
математического анализа
линейной алгебры
дискретной математики
комбинаторики
Выберите все верные утверждения
Графом называется система объектов (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Два ребра называются смежными, если они находятся в одной компоненте связности.
Если у вершины есть петля, то её степень больше единицы.
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Сколько петель в данном графе? Укажите число
(a)
Сколько пар кратных рёбер в данном графе? Укажите число
(a)
Сколько компонент связности в данном графе
(a)
Граф на 10^5 вершин и 10^5 рёбер при ограничениях в 64 Мб можно хранить с помощью
Списка рёбер
vector<pair<int, int>> g(m)
Матрицы смежности
int a[n][n]
Списка смежности
vector<vector<int>> g(n)
Выберите все верные утверждения
DFS - dodo-first search
Поиск в глубину - рекурсивный алгоритм
Для обхода дерева в глубину обязательно нужно использовать булевый массив used
Поиск в глубину запускается в каждую вершину ровно 1 раз
Асимптотика покраски компонент связности графа
O(M + N)
O(N^2 + M)
O(N * M)
O(M * logN)
Выберите все верные утверждения
Покраска графа в два цвета имеет асимптотику
O(N * logN).
Двудольный граф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части.
Вершины двудольного графа можно покрасить в два цвета так, что любые две смежные вершины будут разного цвета.
В двудольном графе все циклы имеют отрицательную длину.
Выберите все верные утверждения
Простой цикл кратчайшей длины можно найти с помощью алгоритма обхода в глубину
Простой цикл кратчайшей длины можно найти с помощью обхода в ширину
Для нахождения цикла кратчайшей длины необходимо запустить обход графа из одной вершины
Для нахождения цикла кратчайшей длины необходимо запустить обход графа из всех его вершин
Топологическая сортировка корректно работает
на ориентированных графах
на неориентированных графах
Выберите все верные утверждения
BFS 0-1 можно запустить на неориентированных невзвешенных графах
Поиск в ширину позволяет находить все кратчайшие пути от заданной вершины
Классический BFS корректно работает на невзвешенных ориентированных и неориентированных графах
В любом дереве на n вершинах есть ровно n - 1 ребро
В алгоритме Флойда первый цикл перебирает
Стартовую вершину
Вершину, через которую будет проходить кратчайший путь
Конечную вершину
Первый цикл перебирает не вершину, а длину
BFS 0-1 работает за
O(N + M)
O(N^2 + M)
O(M)
O(N)
Дейкстра на разреженном графе работает за
O(N log N)
O(N log M)
O(M log N)
O(N + M)
