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

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

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

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

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

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

Вопрос 1

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

  1. Простой граф
  2. Полный граф
  3. Ациклический граф
  4. Взвешенный граф
  5. без петель и кратных ребер
  6. между каждой парой вершин – ребро
  7. не содержит циклов
  8. каждому ребру сопоставлено число
Вопрос 2

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

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

Упорядочьте действия при анализе графа:

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

Укажите правильную последовательность операций при удалении вершины из графа:

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

Граф без петель и кратных ребер – это …

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

Матрица … – это матрица, которой задается граф, если строки соответствуют вершинам, а столбцы – ребрам

  1. смежности
  2. инцидентности
  3. весов
  4. достижимости
Вопрос 7

Задача о … привела к возникновению теории графов

  1. ханойских башнях
  2. семи мостах Кёнигсберга
  3. о восьми ферзях
  4. волке, козе и капусте
Вопрос 8

… граф содержит направленные ребра

  1. Полный
  2. Планарный
  3. Двудольный
  4. Ориентированный
Вопрос 9

Подмножество графа, содержащее часть его вершин и ребер, называется …

  1. подграф
  2. подграфом
Вопрос 10

Фамилия автора первой задачи, считающейся началом теории графов, – …

  1. Эйлер
Вопрос 11

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

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

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

  1. Простой путь
  2. Цикл
  3. Цепь
  4. Компонента связности
  5. путь без повторений вершин и ребер
  6. замкнутый путь без повторений вершин и ребер
  7. максимальный связный подграф
  8. путь без повторений ребер, но с возможными повторениями вершин
Вопрос 13

Расположите в правильном порядке шаги алгоритма BFS:

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

Расположите в правильном порядке этапы алгоритма DFS:

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

… всегда является связным

  1. Пустой граф
  2. Полный граф с n≥2 вершинами
  3. Граф с n вершинами и n–1 ребрами
  4. Двудольный граф
Вопрос 16

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

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

В простом пути …

  1. вершины и ребра никогда не повторяются
  2. все вершины могут повторяться
  3. все ребра могут повторяться
  4. ребра могут быть направленными
Вопрос 18

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

  1. замкнутый путь с повторяющимися дугами
  2. путь без направлений
  3. любой путь от вершины A к вершине B
  4. замкнутый путь с уникальными вершинами и дугами
Вопрос 19

Объект, состоящий из вершин и ребер, называется …

  1. граф
  2. графом
Вопрос 20

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

  1. цикл
  2. контур
  3. циклом
  4. контуром
Вопрос 21

Установите соответствие между алгоритмом и используемой структурой данных:

  1. Обход в глубину
  2. Обход в ширину
  3. Топологическая сортировка
  4. Обратный обход
  5. стек
  6. очередь
  7. стек / очередь
  8. постфиксный порядок
Вопрос 22

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

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

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

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

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

  1. инициализация массивов disc, low, visited
  2. рекурсивный обход графа (DFS)
  3. вычисление disc и low для вершин
  4. проверка условия low[v] > disc[u]
  5. добавление ребра (u,v) в список мостов при выполнении условия
Вопрос 25

Алгоритм BFS в невзвешенном графе гарантированно найдет …

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

Неверно, что при реализации алгоритма DFS с рекурсией требуется …

  1. массив посещенных
  2. очередь
  3. рекурсивный стек
  4. граф в виде списка смежности
Вопрос 27

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

  1. Алгоритм Крускала
  2. Топологическая сортировка
  3. BFS
  4. DFS
Вопрос 28

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

  1. если граф содержит цикл
  2. в неориентированном графе
  3. если граф – дерево
  4. если граф ацикличен
Вопрос 29

Структура данных, используемая в алгоритме обхода в ширину, называется …

  1. очередь
  2. очередью
Вопрос 30

Структура данных, которая используется при обходе графа в глубину, – это …

  1. стек
Вопрос 31

Установите соответствие между алгоритмами и их свойствами:

  1. Алгоритм Прима
  2. Алгоритм Крускала
  3. Поиск в глубину
  4. Поиск в ширину
  5. основан на приращении дерева
  6. использует сортировку ребер
  7. часто используется для обхода дерева
  8. использует очередь
Вопрос 32

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

  1. Лист
  2. Корень
  3. Лес
  4. Остовное дерево
  5. вершина степени 1
  6. вершина с нулевой степенью захода, в которую не ведут дуги
  7. набор непересекающихся деревьев
  8. подграф, содержащий все вершины исходного графа без циклов
Вопрос 33

Расположите этапы построения остовного дерева алгоритмом Краскала:

  1. создать множество деревьев из отдельных вершин (инициализация)
  2. сортировать ребра по возрастанию веса
  3. по очереди добавлять ребра, не образующие циклов
  4. объединять компоненты при добавлении ребра
  5. завершить построение, когда в дереве n − 1 ребер
Вопрос 34

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

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

Говоря о графе «дерево», можно утверждать, что …

  1. число ребер этого графа всегда больше числа вершин
  2. этот граф содержит цикл
  3. между любыми двумя вершинами этого графа существует единственный путь
  4. этот граф может быть несвязным
Вопрос 36

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

  1. Бинарное дерево
  2. Рекурсивное дерево
  3. Тернарное дерево
  4. Ациклический граф
Вопрос 37

Лес из k деревьев и n вершин содержит … ребер

  1. 2n − k
  2. n − 1
  3. n + k
  4. n − k
Вопрос 38

Алгоритм Крускала основывается на …

  1. расширении дерева от произвольного узла
  2. поиске в глубину
  3. сортировке ребер по весу
  4. обратном обходе дерева
Вопрос 39

… – это вершина дерева, не имеющая родителя

  1. Корень
Вопрос 40

… дерево – это дерево, где каждая вершина имеет не более двух потомков

  1. Бинарное
Вопрос 41

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

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

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

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

Упорядочьте шаги построения плоского представления графа:

  1. изобразить вершины
  2. провести ребра без пересечений
  3. обозначить грани
  4. проверить формулу Эйлера
  5. сохранить изображение
Вопрос 44

Упорядочьте шаги построения плоского вложения графа:

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

Один планарный граф может иметь …

  1. только одну плоскую укладку
  2. ровно две плоские укладки
  3. не более трех плоских укладок
  4. бесконечное множество плоских укладок
Вопрос 46

Гамма-цепь сегмента – это …

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

Допустимая грань сегмента – это …

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

Формула Эйлера для связного планарного графа – … (где X – количество вершин, Y – количество ребер, Г – число граней)

  1. X + Y = Г
  2. X − Y + Г = 2
  3. X + Y + Г = 2
  4. X − Г + Y = 2
Вопрос 49

Минимальное количество ребер, которые должны ограничивать грань в триангуляции, – …

  1. 3
  2. три
  3. 3 ребра
  4. три ребра
Вопрос 50

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

  1. Планарный
Вопрос 51

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

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

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

  1. Полуэйлеров граф
  2. Эйлеровыв граф
  3. Полугамильтонов граф
  4. Гамильтонов граф
  5. граф, в котором существует эйлеров путь
  6. граф, в котором существует эйлеров цикл
  7. граф, в котором существует гамильтонова цепь
  8. граф, в котором существует гамильтонов цикл
Вопрос 53

Упорядочите действия при проверке, содержит ли граф гамильтонов путь:

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

Упорядочьте этапы проверки того, является ли неориентированный граф эйлеровым:

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

Гамильтонов цикл – это …

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

Говоря о том, может ли дерево содержать гамильтонов цикл, можно утверждать, что дерево …

  1. всегда содержит гамильтонов цикл
  2. содержит гамильтонов цикл, только если оно полное
  3. содержит гамильтонов цикл только при четном числе вершин
  4. никогда не содержит гамильтонов цикл
Вопрос 57

Обязательное условие для существования эйлерова пути в неориентированном графе: …

  1. ровно две вершины имеют нечетную степень
  2. все вершины имеют четную степень
  3. граф содержит цикл
  4. в графе нет мостов
Вопрос 58

В … обязательно есть гамильтонов цикл

  1. любом дереве
  2. любом связном графе
  3. любом двудольном графе
  4. полном графе из трех и более вершин
Вопрос 59

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

  1. четная
  2. чётная
Вопрос 60

… путь – это путь в графе, который проходит по каждому ребру графа ровно один раз

  1. Эйлеров
Вопрос 61

Соотнесите алгоритмы с их ключевыми свойствами:

  1. Алгоритм Дейкстры
  2. Алгоритм Форда-Беллмана
  3. Алгоритм Флойда-Уоршелла
  4. Алгоритм А*
  5. работает только с неотрицательными весами
  6. обнаруживает отрицательные циклы
  7. находит пути между всеми парами вершин
  8. использует эвристику для ускорения поиска
Вопрос 62

Соотнесите структуру данных с ее применением в алгоритме Дейкстры:

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

Упорядочьте этапы проверки того, является ли неориентированный граф эйлеровым:

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

Упорядочьте шаги алгоритма Форда–Беллмана:

  1. инициализировать расстояния: 0 для стартовой вершины, ∞ для остальных
  2. для каждого ребра (u, v) выполнить релаксацию: если d[u] + w(u, v) < d[v], обновить d[v]
  3. повторить релаксацию n–1 раз (где n – число вершин)
  4. проверить наличие отрицательных циклов: если на n-й итерации происходит релаксация, цикл есть
  5. вернуть итоговые расстояния или сообщение об отрицательном цикле
Вопрос 65

Алгоритм Беллмана–Форда после основных итераций проверяет …

  1. связность графа
  2. количество ребер
  3. наличие отрицательных циклов
  4. симметричность графа
Вопрос 66

Алгоритм … можно применять при наличии отрицательных весов

  1. Прима
  2. Дейкстры
  3. Крускала
  4. Беллмана–Форда
Вопрос 67

Для алгоритма … требуется очередь с приоритетом

  1. Беллмана–Форда
  2. поиска в ширину
  3. Дейкстры
  4. поиска в глубину
Вопрос 68

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

  1. всегда прост
  2. всегда включает все вершины
  3. может включать цикл
  4. всегда существует
Вопрос 69

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

  1. Релаксация
Вопрос 70

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

  1. Взвешенный
Вопрос 71

Соотнесите величину и ее определение:

  1. Значение потока
  2. Пропускная способность
  3. Остаточная пропускная способность
  4. Увеличивающая цепь
  5. сумма потока из источника или в сток
  6. максимум возможного потока через ребро
  7. разность между пропускной способностью и текущим потоком
  8. путь, по которому можно увеличить поток
Вопрос 72

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

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

Упорядочьте этапы формирования транспортной сети:

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

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

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

При достижении тупика в алгоритме Форда–Фалкерсона …

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

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

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

Понятие «обратное ребро» применительно к остаточной сети обозначает …

  1. замыкание цикла
  2. потенциальное возвращение потока
  3. дублирующее ребро
  4. путь в другую компоненту
Вопрос 78

Если путь содержит ребро с нулевой остаточной емкостью, то …

  1. путь игнорируется
  2. поток уменьшается
  3. поток перенаправляется
  4. путь обрывается
Вопрос 79

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

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

Вершина, из которой начинает распространяться поток в транспортной сети, – это …

  1. исток
  2. источник
Вопрос 81

Установите соответствие прикладных задач и типов покрытия:

  1. Размещение камер наблюдения
  2. Оптимизация маршрутов мусоровозов
  3. Размещение базовых станций
  4. Обслуживание всех районов города
  5. вершинное покрытие
  6. реберное покрытие
  7. доминирующее множество
  8. покрытие множества
Вопрос 82

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

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

Упорядочьте шаги решения задачи о покрытии с использованием жадного алгоритма:

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

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

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

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

  1. дорогу
  2. город
  3. вес ребра
  4. стоимость маршрута
Вопрос 86

Реберное покрытие представляет собой множество ребер, …

  1. инцидентных всем вершинам
  2. покрывающее все другие ребра
  3. покрывающее все вершины
  4. которые имеют наибольший вес
Вопрос 87

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

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

Алгоритм Флойда–Уоршелла применим для …

  1. поиска кратчайшего пути между двумя вершинами
  2. построения остовного дерева
  3. нахождения кратчайших путей между всеми парами вершин
  4. топологической сортировки
Вопрос 89

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

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

… покрытие предполагает выбор минимального множества ребер, покрывающего все вершины графа

  1. Рёберное
  2. Реберное