Вопрос 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выделение компонент сильной связности✓ Правильный ответ
✓ Правильный ответ первоначальный обход графа (DFS) ; заполнение стека порядком завершения вершин ; транспонирование графа ; обход транспонированного графа в порядке стека ; выделение компонент сильной связности
Вопрос 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Топологическая сортировка
- 3BFS
- 4DFS
Вопрос 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 ребер
✓ Правильный ответ создать множество деревьев из отдельных вершин (инициализация) ; сортировать ребра по возрастанию веса ; по очереди добавлять ребра, не образующие циклов ; объединять компоненты при добавлении ребра ; завершить построение, когда в дереве n − 1 ребер
Вопрос 34
Упорядочьте шаги алгоритма Прима:
- 1инициализировать дерево с одной вершиной
- 2выбрать минимальное ребро, соединяющее дерево с новой вершиной
- 3добавить выбранное ребро и вершину в дерево
- 4обновить список ребер, соединяющих дерево с оставшимися вершинами
- 5повторять, пока все вершины не будут включены
Вопрос 35
Говоря о графе «дерево», можно утверждать, что …
- 1число ребер этого графа всегда больше числа вершин
- 2этот граф содержит цикл
- 3между любыми двумя вершинами этого графа существует единственный путь
- 4этот граф может быть несвязным
Вопрос 36Ответ открыт бесплатно
… – это двоичное дерево, в котором у каждой вершины есть не более двух потомков
- 1Бинарное дерево✓ Правильный ответ
- 2Рекурсивное дерево
- 3Тернарное дерево
- 4Ациклический граф
✓ Правильный ответ Бинарное дерево
Вопрос 37
Лес из k деревьев и n вершин содержит … ребер
- 12n − k
- 2n − 1
- 3n + k
- 4n − 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 – количество ребер, Г – число граней)
- 1X + Y = Г
- 2X − Y + Г = 2
- 3X + Y + Г = 2
- 4X − Г + Y = 2
Вопрос 49
Минимальное количество ребер, которые должны ограничивать грань в триангуляции, – …
- 13
- 2три
- 33 ребра
- 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Реберное✓ Правильный ответ
✓ Правильный ответ Рёберное ; Реберное
Вопрос 91
Имеется полный неориентированный граф с 5 вершинами.
Сколько ребер в таком графе?
- 15
- 210
- 315
Вопрос 92
Имеется граф с 4 вершинами (без петель).
Сколько различных ориентированных дуг можно построить между этими вершинами?
- 18
- 212
- 316
Вопрос 93Ответ открыт бесплатно
В неориентированном графе из 8 вершин 4 вершины соединены в путь A–B–C–D, а остальные – изолированы.
Сколько компонент связности в графе?
- 11
- 22
- 35✓ Правильный ответ
Вопрос 94
Имеется граф с 5 вершинами и двумя компонентами связности.
Какое наименьшее количество ребер необходимо добавить в этот граф, чтобы он стал связным?
- 11
- 22
- 33
Вопрос 95
При обходе неориентированного графа вы построили остовное дерево.
Какие ребра помогут найти фундаментальные циклы?
- 1Ребра, не вошедшие в дерево.
- 2Ребра, соединяющие листья.
- 3Ребра, исходящие из корня.
Вопрос 96Ответ открыт бесплатно
Граф представляет собой лабиринт.
Что применить, чтоб найти кратчайший путь от входа к выходу?
- 1Использовать алгоритм DFS.
- 2Использовать алгоритм Крускала.
- 3Использовать алгоритм BFS.✓ Правильный ответ
✓ Правильный ответ Использовать алгоритм BFS.
Вопрос 97
Дано дерево из 10 вершин.
Сколько ребер оно содержит?
- 18
- 29
- 310
Вопрос 98
В графе 12 вершин и 10 ребер.
Является ли этот граф деревом?
- 1Да, этот граф является деревом.
- 2Этот граф не является деревом, если он связный.
- 3Нет, этот граф не является деревом.
Вопрос 99
У связного планарного графа 10 граней и 7 вершин.
Сколько у этого графа ребер?
- 111
- 212
- 315
Вопрос 100Ответ открыт бесплатно
Имеется граф с 11 ребрами и 6 вершинами.
Может ли этот граф быть планарным?
- 1Да, этот граф может быть планарным.✓ Правильный ответ
- 2Этот граф может быть планарным только при наличии треугольников.
- 3Нет, этот граф не может быть планарным.
✓ Правильный ответ Да, этот граф может быть планарным.
Вопрос 101
В графе 6 вершин со степенями: 2, 2, 4, 4, 2, 2.
Проверить, есть ли в этом графе эйлеров цикл?
- 1Да, в этом графе существует эйлеров цикл.
- 2Нет, в этом графе нет эйлерового цикла, но есть эйлеров путь.
- 3Определить, есть ли в этом графе эйлеров цикл, по имеющимся данным невозможно.
Вопрос 102
В графе 6 вершин со степенями: 3, 4, 5, 3, 4, 3.
Является ли граф гамильтоновым?
- 1Да, граф является гамильтоновым.
- 2Нет, но граф содержит гамильтонов цикл.
- 3Нет, граф является эйлеровым графом.
Вопрос 103Ответ открыт бесплатно
На рисунке приведен ориентированный граф.
- 12
- 25
- 36✓ Правильный ответ
- 47
Вопрос 104
Дана матрица смежности для графа с вершинами А, Б, В, Г соответственно:
- 12
- 24
- 36
- 48
Вопрос 105
В транспортной сети ребро А→Б имеет пропускную способность 7, текущий поток по нему равен 3.
Какова остаточная пропускная способность этого ребра?
- 13
- 24
- 37
Вопрос 106Ответ открыт бесплатно
В сети путь s→A→B→t имеет остаточные емкости: s→A = 3, A→B = 5, B→t = 4.
Какой максимальный поток можно передать по этому пути?
- 13✓ Правильный ответ
- 24
- 35
Вопрос 107
Имеется задача оптимального маршрута курьера, который должен посетить все пункты.
Какую задачу теории графов в этом случае решают?
- 1Поиск эйлерова пути.
- 2Задачу о назначениях.
- 3Задачу коммивояжёра.
Вопрос 108
Логистическая компания планирует доставку груза из города A в город D. Известны расстояния между городами: A–B = 5, A–C = 2, B–D = 4, C–D = 8.
Какой маршрут обеспечивает минимальную суммарную стоимость доставки?
- 1A→C→D.
- 2A→B→D.
- 3A→B→C→D.
Вопрос 109
Граф, который используется для моделирования задач составления расписаний, – …
- 1двудольный граф
- 2дерево
- 3полный граф
- 4планарный граф
Вопрос 110Ответ открыт бесплатно
В задаче о назначениях минимизируется …
- 1длина пути
- 2стоимость назначений✓ Правильный ответ
- 3количество вершин
- 4время выполнения
✓ Правильный ответ стоимость назначений
Вопрос 111
Вершина в графе при моделировании расписания обозначает …
- 1ресурс
- 2задачу
- 3поток
- 4стоимость
Вопрос 112
… – это подход, который используется при решении задачи о минимальном покрытии вершин
- 1Динамическое программирование
- 2Поиск в глубину
- 3Жадный алгоритм
- 4Метод ветвей и границ
Вопрос 113Ответ открыт бесплатно
Чаще всего оптимизируется в задачах транспортировки такой параметр, как …
- 1расстояние
- 2скорость
- 3затраты✓ Правильный ответ
- 4пропускная способность
✓ Правильный ответ затраты
Вопрос 114
Задача коммивояжера – это задача …
- 1максимизации потока
- 2поиска остова
- 3поиска эйлерова пути
- 4поиска кратчайшего гамильтонова цикла
Вопрос 115
Задача, в которой требуется посетить каждый город один раз и вернуться в начальный, получила название задачи …
- 1коммивояжёра
- 2коммивояжера
- 3коммивояжёр
- 4коммивояжер
- 5о коммивояжёре, о коммивояжере
Вопрос 116Ответ открыт бесплатно
… покрытие – это набор такого минимального множества вершин графа, что каждое ребро графа инцидентно хотя бы одной вершине из этого множества
- 1Вершинное✓ Правильный ответ
✓ Правильный ответ Вершинное
Вопрос 117
В сети дорог необходимо найти маршрут, который позволит проехать по всем дорогам ровно один раз.
Какая задача в этом случае решается?
- 1Поиск эйлерова пути.
- 2Поиск минимального остовного дерева.
- 3Задача о назначениях.
Вопрос 118
… всегда содержит гамильтонов цикл
- 1Планарный граф
- 2Граф «дерево»
- 3Полный граф
- 4Эйлеров граф
Вопрос 119
Неверно что … может быть гамильтоновым
- 1несвязный граф
- 2граф с вершинами степени 1
- 3граф, удовлетворяющий теореме Оре,
- 4ориентированный граф с петлями
Вопрос 120Ответ открыт бесплатно
Граф является полуэйлеровым, если он …
- 1содержит эйлеров цикл
- 2содержит гамильтонов путь
- 3не содержит циклов
- 4содержит эйлеров путь✓ Правильный ответ
✓ Правильный ответ содержит эйлеров путь
Вопрос 121
Неверно что … может быть гамильтоновым
- 1полный граф с 5 вершинами
- 2граф «звезда» с 4 вершинами
- 3циклический граф с 6 вершинами
- 4граф, удовлетворяющий теореме Дирака
Вопрос 122
Неверно, что … является необходимым критерием для эйлерова цикла
- 1связность
- 2наличие у всех вершин четной степени
- 3наличие хотя бы одного цикла
- 4отсутствие петель
Вопрос 123Ответ открыт бесплатно
Полугамильтоновым называется граф …
- 1с гамильтоновым циклом
- 2с гамильтоновым путем, но без гамильтонового цикла✓ Правильный ответ
- 3в котором все вершины имеют степень 3
- 4без циклов
✓ Правильный ответ с гамильтоновым путем, но без гамильтонового цикла
Вопрос 124
Количество вершин нечетной степени, которое должно быть в графе, чтобы в нем существовал эйлеров путь, – …
- 12
- 2две
- 32 вершины
- 4две вершины
Вопрос 125
На рисунке представлен граф.
- 1Нет, этот граф не содержит гамильтонов цикл.
- 2Да, этот граф содержит гамильтонов цикл.
- 3По приведенному рисунку нельзя судить о том, содержит ли этот граф гамильтонов цикл или нет.
Вопрос 126Ответ открыт бесплатно
Теория графов изучает …
- 1дифференциальные уравнения
- 2структуры из вершин и ребер✓ Правильный ответ
- 3теорию вероятностей
- 4матричные вычисления
✓ Правильный ответ структуры из вершин и ребер
Вопрос 127
Граф, где ребра имеют направление, называется … графом
- 1неориентированным
- 2полным
- 3смешанным
- 4ориентированным
Вопрос 128
Степень вершины в неориентированном графе – это …
- 1количество петель
- 2длина самого длинного пути
- 3число вершин в графе
- 4число ребер, инцидентных вершине
Вопрос 129
Операция объединения двух вершин в одну – это …
- 1дополнение графа
- 2удаление ребра
- 3стягивание
- 4добавление вершины
Вопрос 130Ответ открыт бесплатно
Подграф, содержащий все вершины исходного графа, называется …
- 1порожденным
- 2изоморфным
- 3дополненным
- 4остовным✓ Правильный ответ
✓ Правильный ответ остовным
Вопрос 131
Количество вершин в графе Кёнигсбергских мостов – …
- 14
- 2четыре
- 34 вершины
- 4четыре вершины
Вопрос 132
Ребро, соединяющее вершину саму с собой, – это …
- 1петля
Вопрос 133Ответ открыт бесплатно
Тип графа, который допускает кратные ребра, – это …
- 1мультиграф✓ Правильный ответ
✓ Правильный ответ мультиграф
Вопрос 134
Имеется полный ориентированный граф с 4 вершинами (без петель).
Сколько различных путей длины 1 можно провести в таком графе?
- 16
- 28
- 312
Вопрос 135
Фундаментальный цикл определяет …
- 1цикл, образованный добавлением ребра к остовному дереву
- 2минимальный цикл в графе
- 3самый длинный цикл в графе
- 4эйлеров цикл
Вопрос 136Ответ открыт бесплатно
При обходе ориентированного графа в глубину обязательно …
- 1учитывать направление ребер✓ Правильный ответ
- 2игнорировать посещенные вершины
- 3использовать очередь
- 4удалять ребра после посещения
✓ Правильный ответ учитывать направление ребер
Вопрос 137
Неверно, что такой граф, как …, может быть двудольным
- 1цикл с 4 вершинами
- 2граф без ребер
- 3цикл с 3 вершинами
- 4дерево
Вопрос 138
Подграф, содержащий все вершины исходного графа и не содержащий циклов, называется …
- 1кликой
- 2остовным деревом
- 3компонентой связности
- 4циклом
Вопрос 139
Для поиска мостов в графе применяется алгоритм …
- 1BFS
- 2DFS
- 3Крускала
- 4Прима
Вопрос 140Ответ открыт бесплатно
Ребро, удаление которого увеличивает количество компонент связности графа, – это …
- 1мост✓ Правильный ответ
Вопрос 141
Граф, в котором вершины можно разделить на два множества так, чтобы ребра соединяли только вершины из разных множеств, – это … граф
- 1двудольный
Вопрос 142
Алгоритм … применяется для поиска компонент сильной связности в ориентированном графе
- 1Косарайю
Вопрос 143Ответ открыт бесплатно
Имеется граф задач с зависимостями.
Как проверить, возможно ли упорядочить их выполнение?
- 1Построить остовное дерево.
- 2Проверить на наличие цикла и выполнить топологическую сортировку.✓ Правильный ответ
- 3Применить DFS к неориентированной версии графа.
✓ Правильный ответ Проверить на наличие цикла и выполнить топологическую сортировку.
Вопрос 144
При использовании алгоритма Форда–Фалкерсона на увеличивающем пути поток …
- 1уменьшается
- 2обращается
- 3увеличивается
- 4удаляется
Вопрос 145
Такая характеристика, как …, влияет на возможность увеличения потока по пути
- 1направление ветра
- 2остаточная пропускная способность
- 3вес вершины
- 4количество инцидентных ребер
Вопрос 146Ответ открыт бесплатно
Такая структура, как …, используется для хранения остаточной сети
- 1множество
- 2очередь с приоритетом
- 3массив
- 4граф✓ Правильный ответ
Вопрос 147
Величина потока |f| определяется как …
- 1сумма длин всех путей
- 2суммарное количество вершин
- 3сумма потоков из истока
- 4максимальная степень вершины
Вопрос 148
Чтобы определить минимальный разрез после нахождения максимального потока, нужно …
- 1найти все насыщенные ребра
- 2найти множество вершин, достижимых из истока в остаточной сети
- 3выбрать ребра с максимальной пропускной способностью
- 4найти все обратные ребра
Вопрос 149
Алгоритм … – это фундаментальный метод нахождения максимального потока в транспортной сети, представленной ориентированным графом G = (X, Y), где X – множество вершин, а Y – множество дуг
- 1Форда–Фалкерсона
- 2Форда – Фалкерсона
- 3Форда-Фалкерсона
Вопрос 150Ответ открыт бесплатно
В транспортной сети пропускная способность ребра А→Б равна 12, поток – 5.
Какова пропускная способность обратного ребра Б→А в остаточной сети?
- 15✓ Правильный ответ
- 27
- 312
Вопрос 151
Говоря о графе «дерево», можно утверждать, что … (укажите 3 варианта ответа)
- 1дерево может содержать циклы
- 2это связный граф без циклов
- 3в дереве с n вершинами количество ребер равно n – 1
- 4между любыми двумя вершинами дерева существует ровно один путь
Вопрос 152
В бинарном дереве поиска …
- 1оба потомка равны родителю
- 2правый потомок всегда меньше родителя
- 3левый потомок всегда меньше родителя
- 4правый потомок всегда равен родителю
Вопрос 153Ответ открыт бесплатно
Минимальное остовное дерево …
- 1всегда единственно
- 2может не быть единственным✓ Правильный ответ
- 3содержит все возможные ребра графа
- 4имеет максимально возможную сумму весов ребер
✓ Правильный ответ может не быть единственным
Вопрос 154
В полном бинарном дереве …
- 1каждый узел имеет ровно два потомка
- 2листья находятся на одном уровне
- 3все внутренние узлы имеют одного потомка
- 4каждый узел имеет более двух потомков
Вопрос 155
В алгоритме Прима …
- 1строится максимальное остовное дерево
- 2все ребра сортируются по убыванию веса
- 3удаляются ребра, образующие циклы
- 4на каждом шаге добавляется минимальное ребро, соединяющее уже покрытую часть с непокрытой
Вопрос 156Ответ открыт бесплатно
Количество ребер в дереве с 10 вершинами – … ребер
- 19✓ Правильный ответ
- 2девять✓ Правильный ответ
✓ Правильный ответ 9 ; девять
Вопрос 157
Количество листьев в полном бинарном дереве высотой 3 – … листьев
- 18
- 2восемь
Вопрос 158
Дерево, где каждая вершина имеет не более двух потомков, называется … деревом
- 1бинарным
Вопрос 159
Имеется граф – лес из 4 деревьев и 20 вершин.
Сколько ребер в таком графе?
- 115
- 216
- 317
Вопрос 160Ответ открыт бесплатно
Соотнесите понятия из теории графов с их определениями:
- 1Планарные графы✓ Правильный ответ
- 2Грань✓ Правильный ответ
- 3Триангуляция✓ Правильный ответ
- 4Гомеоморфные графы✓ Правильный ответ
- 5графы, допускающие укладку без пересечений ребер✓ Правильный ответ
- 6область плоскости, ограниченная ребрами✓ Правильный ответ
- 7плоский граф, где каждая грань является треугольником✓ Правильный ответ
- 8графы, получаемые друг из друга операциями подразделения ребер✓ Правильный ответ
✓ Правильный ответ Планарные графы = графы, допускающие укладку без пересечений ребер ; Грань = область плоскости, ограниченная ребрами ; Триангуляция = плоский граф, где каждая грань является треугольником ; Гомеоморфные графы = графы, получаемые друг из друга операциями подразделения ребер
Вопрос 161
Для связного планарного графа с 8 вершинами максимальное количество ребер – …
- 112
- 216
- 318
- 424
Вопрос 162
Согласно теореме Понтрягина–Куратовского, минимальным непланарным является граф …
- 1K4
- 2K3,2
- 3K3,3
- 4«дерево»
Вопрос 163Ответ открыт бесплатно
Неверно, что планарный граф …
- 1характеризуется тем, что для него выполняется формула Эйлера
- 2не содержит подграфов, гомеоморфных K5
- 3характеризуется тем, что все его вершины имеют степень ≤ 5✓ Правильный ответ
- 4может быть изображен на сфере
✓ Правильный ответ характеризуется тем, что все его вершины имеют степень ≤ 5
Вопрос 164
Говоря о деревьях, можно утверждать, что эти графы …
- 1всегда имеют несколько граней
- 2могут быть непланарными
- 3имеют ровно одну грань при плоской укладке
- 4не подчиняются формуле Эйлера
Вопрос 165
Грань в планарном графе – это …
- 1множество вершин
- 2область плоскости, ограниченная ребрами
- 3подграф без циклов
- 4максимальное независимое множество
Вопрос 166Ответ открыт бесплатно
Количество граней, которое имеет дерево с 10 вершинами при плоской укладке, – …
- 1один✓ Правильный ответ
- 21✓ Правильный ответ
- 31 грань✓ Правильный ответ
- 4одна✓ Правильный ответ
- 5одна грань✓ Правильный ответ
✓ Правильный ответ один ; 1 ; 1 грань ; одна ; одна грань
Вопрос 167
Количество граней, которое имеет полный граф K₄ при планарной укладке, – …
- 14
- 2четыре
- 34 грани
- 4четыре грани
Вопрос 168
Имеется связный граф с 12 вершинами и 20 ребрами.
Какое максимальное количество граней может иметь плоское вложение этого графа?
- 19
- 210
- 311
Вопрос 169
Алгоритм обхода графа, который использует стек, – это алгоритм …
- 1BFS
- 2DFS
- 3Дейкстры
- 4Крускала
Вопрос 170Ответ открыт бесплатно
Операция упрощения графа путем объединения компонент сильной связности – это …
- 1транзитивное замыкание
- 2дополнение
- 3стягивание
- 4конденсация✓ Правильный ответ
✓ Правильный ответ конденсация
Вопрос 171
… – это граф, который всегда является ациклическим
- 1Полный граф
- 2Дерево
- 3Двудольный граф
- 4Ориентированный граф
Вопрос 172
… путь проходит через все вершины графа ровно один раз
- 1Гамильтонов
- 2Эйлеров
- 3Простой
- 4Полный
Вопрос 173Ответ открыт бесплатно
У графа с n вершинами и 0 ребрами – … компонент связности
- 10
- 21
- 3n✓ Правильный ответ
- 4n – 1
Вопрос 174
В полном графе с 5 вершинами – … ребер
- 110
- 2десять
Вопрос 175
Замкнутый путь, где все вершины (кроме начальной и конечной) и ребра уникальны, называется …
- 1цикл
- 2циклом
- 3контур
- 4контуром
Вопрос 176Ответ открыт бесплатно
Количество компонент связности у графа, состоящего из 3 изолированных вершин, равно …
- 13✓ Правильный ответ
- 2три✓ Правильный ответ
- 3трем✓ Правильный ответ
- 4трём✓ Правильный ответ
✓ Правильный ответ 3 ; три ; трем ; трём
Вопрос 177
В графе вершины A, B, C и D соединены ребрами (A–B), (B–C),
(C–A).
Сколько компонент связности у этого графа?
- 11
- 22
- 33
Вопрос 178
Соотнесите алгоритмы с их ключевыми свойствами:
- 1Алгоритм Дейкстры
- 2Алгоритм Форда–Беллмана
- 3Алгоритм Флойда–Уоршелла
- 4Алгоритм А*
- 5работает только с неотрицательными весами
- 6обнаруживает отрицательные циклы
- 7находит пути между всеми парами вершин
- 8использует эвристику для ускорения поиска
Вопрос 179
Упорядочьте шаги алгоритма Форда–Беллмана:
- 1инициализировать расстояния: 0 для стартовой вершины, ∞ для остальных
- 2для каждого ребра (u, v) выполнить релаксацию:
если d[u] + w(u, v) < d[v], обновить d[v]
- 3повторить релаксацию n – 1 раз (где n – число вершин)
- 4проверить наличие отрицательных циклов: если на n-й итерации происходит релаксация, цикл есть
- 5вернуть итоговые расстояния или сообщение об отрицательном цикле
Вопрос 180Ответ открыт бесплатно
Алгоритм … требует хранения всей матрицы расстояний
- 1Дейкстры
- 2Форда–Беллмана
- 3Флойда–Уоршелла✓ Правильный ответ
- 4Крускала
✓ Правильный ответ Флойда–Уоршелла
Вопрос 181
Если применить алгоритм Дейкстры к графу с отрицательными весами, …
- 1это всегда даст правильный результат
- 2это может дать неправильный результат
- 3алгоритм будет работать медленнее
- 4алгоритм прекратит работу с ошибкой
Вопрос 182
Алгоритм … наиболее эффективен для поиска кратчайшего пути из одной вершины в графе с неотрицательными весами
- 1Форда–Беллмана
- 2Флойда–Уоршелла
- 3Дейкстры
- 4Прима
Вопрос 183Ответ открыт бесплатно
Алгоритм … использует релаксацию ребер (укажите 2 варианта ответа)
- 1Флойд–Уоршелл
- 2Форда–Беллмана✓ Правильный ответ
- 3Дейкстры✓ Правильный ответ
- 4A*
✓ Правильный ответ Форда–Беллмана ; Дейкстры
Вопрос 184
Алгоритм … основан на динамическом программировании
- 1Дейкстры
- 2Форда–Беллмана
- 3Флойда–Уоршелла
Вопрос 185
… – это путь, сумма весов ребер которого минимальна
- 1Эйлеров путь
- 2Гамильтонов путь
- 3Кратчайший путь
- 4Минимальный остов
Вопрос 186
… граф – это граф, где каждому ребру присвоено числовое значение
- 1Взвешенный
Вопрос 187Ответ открыт бесплатно
На рисунке представлен ориентированный граф.
- 16
- 27✓ Правильный ответ
- 38
- 412