Тесты СинергияАртём Хелп
Артём Help онлайнПолучить расчёт
Бесплатно оценим сроки и стоимостьОтправить задание в Telegram
Теория графов.dor_БАК_25-122-Б

Теория графов.dor_БАК_25-122-Б — вариант 3

Просмотрите все вопросы и варианты бесплатно. Правильные ответы скрыты и открываются только после получения доступа.

11 вопросов Вариант 3 Доступ 7 дней
Содержание теста

Вопросы и варианты

Без отметок и подсказок к правильным ответам

Вопрос 1

Соотнесите понятия из теории графов с их характеристиками:

  1. Мост
  2. Точка сочленения
  3. Двудольный граф
  4. Остовное дерево
  5. ребро, удаление которого увеличивает число компонент связности
  6. вершина, удаление которой увеличивает число компонент связности
  7. граф, раскрашиваемый в два цвета
  8. подграф, содержащий все вершины без циклов
Вопрос 2

Упорядочьте этапы алгоритма Косарайю:

  1. первоначальный обход графа (DFS)
  2. заполнение стека порядком завершения вершин
  3. транспонирование графа
  4. обход транспонированного графа в порядке стека
  5. выделение компонент сильной связности
Вопрос 3

Фундаментальный цикл определяет …

  1. цикл, образованный добавлением ребра к остовному дереву
  2. минимальный цикл в графе
  3. самый длинный цикл в графе
  4. эйлеров цикл
Вопрос 4

При обходе ориентированного графа в глубину обязательно …

  1. учитывать направление ребер
  2. игнорировать посещенные вершины
  3. использовать очередь
  4. удалять ребра после посещения
Вопрос 5

Неверно, что такой граф, как …, может быть двудольным

  1. цикл с 4 вершинами
  2. граф без ребер
  3. цикл с 3 вершинами
  4. дерево
Вопрос 6

Подграф, содержащий все вершины исходного графа и не содержащий циклов, называется …

  1. кликой
  2. остовным деревом
  3. компонентой связности
  4. циклом
Вопрос 7

Для поиска мостов в графе применяется алгоритм …

  1. BFS
  2. DFS
  3. Крускала
  4. Прима
Вопрос 8

Ребро, удаление которого увеличивает количество компонент связности графа, – это …

  1. мост
Вопрос 9

Граф, в котором вершины можно разделить на два множества так, чтобы ребра соединяли только вершины из разных множеств, – это … граф

  1. двудольный
Вопрос 10

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

  1. Косарайю
Вопрос 11

Имеется граф задач с зависимостями. Как проверить, возможно ли упорядочить их выполнение?

  1. Построить остовное дерево.
  2. Проверить на наличие цикла и выполнить топологическую сортировку.
  3. Применить DFS к неориентированной версии графа.