Алгоритмы оптимизационных задач на графах

Что такое минимальное остовное дерево в графе?

• Самое длинное дерево, соединящее все вершины
• Дерево, содержащее все вершины, минимальной общей длины
• Дерево, содержащее все вершины с максимальной суммарной стоимостью
• Дерево с минимальным количеством рёбер

Какая алгоритмическая стратегия используется в алгоритме Крускала?

• Жадный подход, выбирающий рёбра по возрастанию веса
• Динамическое программирование
• Обход в глубину
• Обход в ширину

Что такое задача о коммивояжёре (Travelling Salesman Problem)?

• Задача нахождения кратчайшего пути, проходящего через все вершины и возвращающегося в начальную
• Задача поиска минимального остовного дерева
• Задача определения максимального остовного дерева
• Задача раскраски графа в минимальное число красок

В чем заключается основное отличие алгоритма Прима от алгоритма Крускала?

• Алгоритм Прима строит дерево, расширяя его из начальной вершины, а Крускал — сортируя рёбра по весу и добавляя их по очереди
• Прима работает только на ориентированных графах, а Крускал — на неориентированных
• Прима использует динамическое программирование, а Крускал — жадные методы
• Оба алгоритма одинаково работают в любых случаях без отличий

Что такое максимальный поток в сетевом графе?

• Максимальная сумма потоков, которая может быть пропущена через все рёбра
• Максимальный поток, который может быть пропущен из истока в сток без нарушения ограничений
• Минимальный поток, необходимый для прохождения через все вершины
• Значение потока на самом длинном пути

Что означает свойство корректности жадных алгоритмов?

• Гарантируют оптимальное решение для всех задач
• Обеспечивают оптимальность для специальных классов задач
• Обеспечивают быструю работу, но не обязательно оптимальность
• Гарантируют неправильное решение при некоторых условиях

Какая задача решается методом ветвей и границ?

• Оптимизация с ограничениями путём отсечения неэффективных веток поиска
• Поиск кратчайшего пути в графе
• Поиск минимального остовного дерева
• Определение цветовой раскраски графа

Что такое эффект ветвей в задачах оптимизации?

• Несоответствие между различными ветками поиска, ведущие к локальным минимумам
• Прирост стоимости при расширении ветки
• Проблема чрезмерной глубины дерева поиска
• Потеря эффективности при расширении ветки

Что такое задачa о кратчайшем пути?

• Определение пути с минимальной суммарной длиной между двумя вершинами
• Определение минимального остовного дерева
• Распределение ресурсов по графу по заданным узлам
• Поиск маршрута с максимальной вместимостью

Каким свойством обладает алгоритм Беллмана-Форда?

• Может работать с графами с отрицательными весами
• Обеспечивает поиск кратчайшего пути только в графах без отрицательных циклов
• Может обнаруживать отрицательные циклы
• Все вышеупомянутые

Что такое путь в графе?

• Последовательность рёбер, соединяющих вершины без повторений
• Последовательность рёбер, соединяющих вершины с возможностью повторений
• Последовательность вершин, соединённых рёбрами, встречающихся один раз
• Совокупность рёбер, соединяющих входные вершины с выходными

Что такое минимальный покрывающий набор рёбер?

• Меньшее множество рёбер, покрывающее все вершины графа
• Множество рёбер с минимальной суммарной стоимостью
• Множество рёбер, покрывающее все вершины без повторений
• Множество рёбер, создающее связный граф

Что характеризует задачу о кратчайших путях в графе?

• Поиск наикратчайшего маршрута между двумя заданными вершинами, возможно с учетом весов рёбер
• Приобретение минимальной стоимости перемещения между всеми вершинами
• Определение максимального пути между двумя вершинами
• Обеспечение связи всех вершин с минимальным количеством рёбер

На каком основании выбираются рёбра в алгоритме Крускала?

• Из-за их минимального веса
• В порядке убывания веса
• По возрастанию веса, чтобы обеспечить минимальную сумму
• В случайном порядке

Что такое алгоритм Форда-Беллмана?

• Алгоритм для поиска кратчайших путей, учитывающий отрицательные веса рёбер
• Алгоритм построения минимального остовного дерева
• Алгоритм поиска максимального потока
• Все вышеперечисленные

Что характерно для задач о минимизации затрат в графе?

• Минимизация суммарной стоимости выбранных рёбер
• Поиск максимального пути
• Определение обрезанных вершин
• Поиск путей с наибольшей вместимостью

Что является ключевым в жадных алгоритмах?

• Локальный оптимум на каждом шаге
• Глобальный поиск глобального оптимума
• Использование динамического программирования
• Обязательное исключение отрицательных весов

Что такое цикл в графе?

• Последовательность рёбер, возвращающаяся в исходную вершину
• Последовательность вершин, соединённых рёбрами без повторений
• Линейная цепь рёбер без возврата
• Непрерывный путь

Почему важно избегать циклов отрицательного веса в графах?

• Могут привести к бесконечным сокращениям пути
• Не позволяют алгоритмам определить оптимальное решение
• Могут вызвать ошибку при поиске кратчайшего пути
• Все вышеуказанное

Что такое минимальный остов в графе?

• Губерсант, содержащий все вершины и минимальное число рёбер
• Остров, соединяющий все вершины с минимальной суммарной стоимостью рёбер
• Цикл в графе с минимальной суммарной стоимостью рёбер
• Дерево, содержащее только рёбра с минимальной стоимостью

Как называется алгоритм поиска кратчайшего пути в графе с неотрицательными весами?

• Алгоритм Дейкстры
• Алгоритм Дейкстры
• Алгоритм Беллмана-Форда
• Алгоритм Форда-Беллмана

Что такое задача о минимальном остов в графе?

• Поиск минимальной цепи между двумя вершинами
• Поиск пути с максимальной пропускной способностью
• Нахождение остовного дерева с минимальной суммарной стоимостью рёбер
• Нахождение остовного дерева с минимальной суммарной стоимостью

Какое утверждение верно для алгоритма Крускала?

• Он использует жадный подход для построения остовного дерева
• Он ищет кратчайший путь между всеми вершинами
• Он работает только с ориентированными графами
• Он использует жадный подход для построения остовного дерева

На чем основан алгоритм Прима?

• На поиске кратчайших путей
• На жадной эвристике для построения минимального остовного дерева
• На жадной эвристике для построения минимального остовного дерева
• На динамическом программировании

Что такое поток в задаче о максимальном потоке?

• Количество материала, проходящего через ребро
• Общее количество путей в графе
• Общее количество вершин
• Количество единиц вещества, проходящего через потоковую сеть от истока к стоку

Что делает алгоритм Форда-Фалкерсона?

• Находит кратчайшее расстояние между двумя вершинами
• Находит минимальное остовное дерево
• Находит максимальный поток в сети
• Определяет наличие циклов в графе

Что такое устойчивое отображение в задаче о минимизации затрат?

• Раскраска графа
• Отображение, при котором суммарные затраты минимальны
• Обозначение минимальных путей
• Наибольшее покрытие графа

Что характеризует задачу о покрытии множества рёбер минимальным количеством?

• Задачу о минимальном покрытии множеств
• Задачу о минимизации затрат
• Задачу о минимальном покрытии рёбер
• Задачу о максимальном независимом множестве

Что такое задача о назначениях в графе?

• Нахождение максимального независимого множества
• Обеспечение минимальной стоимости назначения вершин
• Определение оптимального соответствия между двумя множествами
• Проход по всем вершинам графа

Что используют при решении задачи о максимальном по размерам паросочетании в двудольном графе?

• Алгоритм Куна-Мэккланд
• Алгоритм Эдмондса-Карпа
• Алгоритм Куна-Мэккланд
• Алгоритм Форда-Фалкерсона

Что такое критическая цепь в алгоритме поиска максимального потока?

• Цепь с минимальной пропускной способностью
• Цепь, которая соединяет исток и сток через все вершины
• Обратная цепь к потоку, увеличивающая его пропускную способность
• Цепь, содержащая максимальное число рёбер

Что из перечисленного является характеристикой жадных алгоритмов?

• Используют глобальную информацию о графе
• Обязательны к использованию динамического программирования
• Обеспечивают оптимальное решение во всех случаях
• Строят решение пошагово, выбирая на каждом шаге локально оптимальное решение

Что подразумевается под задачей о кратчайшем пути в графе?

• Нахождение пути с максимальной длиной
• Нахождение пути с минимальной суммарной стоимостью
• Нахождение пути с максимальной пропускной способностью
• Определение всех кратчайших путей между вершинами

Что такое резидуальная сеть в задачах о потоках?

• Граф с обратными рёбрами, представляющими возможные дополнительные потоки
• Граф, содержащий только рёбра, по которым поток уже прошёл
• Граф, в котором вес рёбер соответствует остаточной пропускной способности
• Обратный граф, отображающий возможные дополнения к текущему потоку

В чем заключается главная идея алгоритма Куна-Мэккланд для максимального паросочетания?

• Использование жадных выборов рёбер
• Генерация всех паросочетаний и выбор оптимального
• Поиск увеличивающих путей в графе
• Поиск увеличивающих путей в двудольном графе для расширения паросочетания

Что подразумевает задача о минимальной стоимости транспортной сети?

• Обеспечение максимального объема перевозок
• Минимизация суммарных затрат при транспортировке товаров
• Обеспечение сбалансированности источников и стоков
• Минимизация затрат при доставке товарных потоков в сеть

Что такое алгоритм Беллмана-Форда?

• Алгоритм поиска кратчайших путей при наличии отрицательных весов
• Алгоритм поиска кратчайших путей без отрицательных весов
• Алгоритм поиска кратчайших путей при наличии отрицательных весов
• Алгоритм поиска минимального остовного дерева

Что представляет собой задача о нахождении максимального независимого множества?

• Выбор множества вершин без рёбер между ними, максимальной по размеру
• Покрытие всех рёбер минимальным количеством вершин
• Построение максимальной цепи
• Выбор наибольшего по количеству вершин множества, в котором не соединённых рёбрами

Что такое факторизация графа по потокам?

• Декомпозиция графа на максимальные потоки
• Разбор графа на подграфы с фиксированным потоком
• Обработка графа в виде цепочек потоков
• Декомпозиция, которая помогает понять структуру потоков в сети

Анна

Исследования ученых о взаимосвязи ума и красоты говорят о том, что умные люди – красивые!

Задать вопрос

Представленная информация была полезной?

ДА

87.1%

НЕТ

12.9%

Проголосовало: 248

или напишите нам прямо сейчас:

Написать в MAXНаписать в TelegramНаписать в WhatsApp

Отзывы наших клиентов

1 2 ... 12 ►