АиСД-2. 2024-2025. ПЗ-Тест №18. Графы. Повторение

Выбираем самую интересную задачу из теории графов

• Минимальный остов

• Кратчайший путь

• Максимальный поток

• Максимальное паросочетание

• Раскраска!

Какая структура данных используется при обходе графа в ширину?

• стек

• список

• очередь

• бинарная куча

Неориентированный граф G содержит n вершин. Элементы, стоящие на главной диагонали его матрицы смежности равно 0, а другие — 1. Выберите верное утверждение.

• Граф G не имеет минимального остова

• Граф G имеет единственный минимальный остов с весом n – 1

• Граф G имеет множество минимальных остовов с весами n – 1

• Граф G имеет множество минимальных остовов с различноыми весами

Сколько промежуточных вершин содержит кратчайший путь из вершины а в вершину e на этом графе?

• 2

• 0

• 1

• 3

• кратчайшего пути нет

Пусть G — это ориентированный граф, в котором вершины представлены числами от 1 до 100. Дуга (i, j) принадлежит G, если j = i + 1 или j = 3⋅i. Чему равно минимальное количество дуг на пути из вершины 1 в вершину 100?

• 4

• 7

• 23

• 99

Сложность базового алгоритма Форда-Фалкерсона для поиска максимального потока зависит от исходных пропускных способностей ребер.

• Да!

• Нет!

Максимальное паросочетание в двудольном графе...

• может покрывать не все вершины

• может являться наибольшим

• может являться полным

• всегда является полным

• всегда покрывает все вершины