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

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

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

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

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

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

Вопрос 1

Установите соответствие между понятиями из теории графов и их определениями:

  1. Исток
  2. Сток
  3. Пропускная способность
  4. Поток
  5. вершина, из которой исходит поток
  6. вершина, в которую приходит поток
  7. максимально возможный поток по ребру
  8. передаваемое количество между вершинами
Вопрос 2

Упорядочьте этапы алгоритма Форда–Фалкерсона:

  1. инициализировать поток нулями
  2. построить остаточную сеть
  3. найти увеличивающий путь
  4. увеличить поток по найденному пути
  5. проверить наличие увеличивающего пути
Вопрос 3

При использовании алгоритма Форда–Фалкерсона на увеличивающем пути поток …

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

Такая характеристика, как …, влияет на возможность увеличения потока по пути

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

Такая структура, как …, используется для хранения остаточной сети

  1. множество
  2. очередь с приоритетом
  3. массив
  4. граф
Вопрос 6

Величина потока |f| определяется как …

  1. сумма длин всех путей
  2. суммарное количество вершин
  3. сумма потоков из истока
  4. максимальная степень вершины
Вопрос 7

При обратном направлении ребра в остаточной сети поток …

  1. усиливается
  2. блокируется
  3. исчезает
  4. возвращается
Вопрос 8

Чтобы определить минимальный разрез после нахождения максимального потока, нужно …

  1. найти все насыщенные ребра
  2. найти множество вершин, достижимых из истока в остаточной сети
  3. выбрать ребра с максимальной пропускной способностью
  4. найти все обратные ребра
Вопрос 9

… – это вершина, в которую поток должен прийти

  1. Сток
Вопрос 10

Алгоритм … – это фундаментальный метод нахождения максимального потока в транспортной сети, представленной ориентированным графом G = (X, Y), где X – множество вершин, а Y – множество дуг

  1. Форда–Фалкерсона
  2. Форда – Фалкерсона
  3. Форда-Фалкерсона
Вопрос 11

В транспортной сети пропускная способность ребра А→Б равна 12, поток – 5. Какова пропускная способность обратного ребра Б→А в остаточной сети?

  1. 5
  2. 7
  3. 12