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

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

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

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

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

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

Вопрос 1

Соотнесите понятие из теории графов с областью его применения:

  1. Минимальное остовное дерево
  2. Топологическая сортировка
  3. Задача о назначениях
  4. Эйлеров путь
  5. оптимизация построения сети
  6. планирование задач с зависимостями
  7. распределение ресурсов
  8. оптимизация маршрутов по улицам
Вопрос 2

Упорядочьте шаги алгоритма Краскала:

  1. отсортировать ребра по весу
  2. пройти по ребрам в порядке возрастания
  3. добавить ребро, если оно не создает цикл
  4. объединить вершины в одно множество
  5. построить остов, содержащий |V|–1 ребро
Вопрос 3

Граф, который используется для моделирования задач составления расписаний, – …

  1. двудольный граф
  2. дерево
  3. полный граф
  4. планарный граф
Вопрос 4

В задаче о назначениях минимизируется …

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

Вершина в графе при моделировании расписания обозначает …

  1. ресурс
  2. задачу
  3. поток
  4. стоимость
Вопрос 6

… – это подход, который используется при решении задачи о минимальном покрытии вершин

  1. Динамическое программирование
  2. Поиск в глубину
  3. Жадный алгоритм
  4. Метод ветвей и границ
Вопрос 7

Чаще всего оптимизируется в задачах транспортировки такой параметр, как …

  1. расстояние
  2. скорость
  3. затраты
  4. пропускная способность
Вопрос 8

Задача коммивояжера – это задача …

  1. максимизации потока
  2. поиска остова
  3. поиска эйлерова пути
  4. поиска кратчайшего гамильтонова цикла
Вопрос 9

Задача, в которой требуется посетить каждый город один раз и вернуться в начальный, получила название задачи …

  1. коммивояжёра
  2. коммивояжера
  3. коммивояжёр
  4. коммивояжер
  5. о коммивояжёре, о коммивояжере
Вопрос 10

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

  1. Вершинное
Вопрос 11

В сети дорог необходимо найти маршрут, который позволит проехать по всем дорогам ровно один раз. Какая задача в этом случае решается?

  1. Поиск эйлерова пути.
  2. Поиск минимального остовного дерева.
  3. Задача о назначениях.