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

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

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

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

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

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

Вопрос 1

Имеется полный неориентированный граф с 5 вершинами. Сколько ребер в таком графе?

  1. 5
  2. 10
  3. 15
Вопрос 2

Имеется граф с 4 вершинами (без петель). Сколько различных ориентированных дуг можно построить между этими вершинами?

  1. 8
  2. 12
  3. 16
Вопрос 3

В неориентированном графе из 8 вершин 4 вершины соединены в путь A–B–C–D, а остальные – изолированы. Сколько компонент связности в графе?

  1. 1
  2. 2
  3. 5
Вопрос 4

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

  1. 1
  2. 2
  3. 3
Вопрос 5

При обходе неориентированного графа вы построили остовное дерево. Какие ребра помогут найти фундаментальные циклы?

  1. Ребра, не вошедшие в дерево.
  2. Ребра, соединяющие листья.
  3. Ребра, исходящие из корня.
Вопрос 6

Граф представляет собой лабиринт. Что применить, чтоб найти кратчайший путь от входа к выходу?

  1. Использовать алгоритм DFS.
  2. Использовать алгоритм Крускала.
  3. Использовать алгоритм BFS.
Вопрос 7

Дано дерево из 10 вершин. Сколько ребер оно содержит?

  1. 8
  2. 9
  3. 10
Вопрос 8

В графе 12 вершин и 10 ребер. Является ли этот граф деревом?

  1. Да, этот граф является деревом.
  2. Этот граф не является деревом, если он связный.
  3. Нет, этот граф не является деревом.
Вопрос 9

У связного планарного графа 10 граней и 7 вершин. Сколько у этого графа ребер?

  1. 11
  2. 12
  3. 15
Вопрос 10

Имеется граф с 11 ребрами и 6 вершинами. Может ли этот граф быть планарным?

  1. Да, этот граф может быть планарным.
  2. Этот граф может быть планарным только при наличии треугольников.
  3. Нет, этот граф не может быть планарным.
Вопрос 11

В графе 6 вершин со степенями: 2, 2, 4, 4, 2, 2. Проверить, есть ли в этом графе эйлеров цикл?

  1. Да, в этом графе существует эйлеров цикл.
  2. Нет, в этом графе нет эйлерового цикла, но есть эйлеров путь.
  3. Определить, есть ли в этом графе эйлеров цикл, по имеющимся данным невозможно.
Вопрос 12

В графе 6 вершин со степенями: 3, 4, 5, 3, 4, 3. Является ли граф гамильтоновым?

  1. Да, граф является гамильтоновым.
  2. Нет, но граф содержит гамильтонов цикл.
  3. Нет, граф является эйлеровым графом.
Вопрос 13

На рисунке приведен ориентированный граф.  

  1. 2
  2. 5
  3. 6
  4. 7
Вопрос 14

Дана матрица смежности для графа с вершинами А, Б, В, Г соответственно:  

  1. 2
  2. 4
  3. 6
  4. 8
Вопрос 15

В транспортной сети ребро А→Б имеет пропускную способность 7, текущий поток по нему равен 3. Какова остаточная пропускная способность этого ребра?

  1. 3
  2. 4
  3. 7
Вопрос 16

В сети путь s→A→B→t имеет остаточные емкости: s→A = 3, A→B = 5, B→t = 4. Какой максимальный поток можно передать по этому пути?

  1. 3
  2. 4
  3. 5
Вопрос 17

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

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

Логистическая компания планирует доставку груза из города A в город D. Известны расстояния между городами: A–B = 5, A–C = 2, B–D = 4, C–D = 8. Какой маршрут обеспечивает минимальную суммарную стоимость доставки?

  1. A→C→D.
  2. A→B→D.
  3. A→B→C→D.