Графы Все темы

Теория графов - обширный раздел

• математического анализа

• линейной алгебры

• дискретной математики

• комбинаторики

Выберите все верные утверждения

• Графом называется система объектов (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

• Два ребра называются смежными, если они находятся в одной компоненте связности.

• Если у вершины есть петля, то её степень больше единицы.

• Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.

Сколько петель в данном графе? Укажите число

Сколько пар кратных рёбер в данном графе? Укажите число

Сколько компонент связности в данном графе

Граф на 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).

• Двудольный граф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части.

• Вершины двудольного графа можно покрасить в два цвета так, что любые две смежные вершины будут разного цвета.

• В двудольном графе все циклы имеют отрицательную длину.

Выберите все верные утверждения

• Простой цикл кратчайшей длины можно найти с помощью алгоритма обхода в глубину

• Простой цикл кратчайшей длины можно найти с помощью обхода в ширину

• Для нахождения цикла кратчайшей длины необходимо запустить обход графа из одной вершины

• Для нахождения цикла кратчайшей длины необходимо запустить обход графа из всех его вершин