Определение и основные понятия графа

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

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

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

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

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

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

(a)  

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

(a)  

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

(a)  

Граф на 10^5 вершин и 10^5 рёбер при ограничениях в 64 Мб можно хранить с помощью

• Списка рёбер

  vector<pair<int, int>> g(m)

• Матрицы смежности

  int a[n][n]

• Списка смежности

  vector<vector<int>> g(n)

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

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

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

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

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

Топологическая сортировка корректно работает

• на ориентированных графах

• на неориентированных графах

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

• DFS - обход в глубину

• BFS - обход в глубину

• DFS - обход в ширину

• BFS - обход в ширину

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

• DFS - обход в глубину

• BFS - обход в глубину

• DFS - обход в ширину

• BFS - обход в ширину

Асимптотика алгоритма BFS и DFS