Test LR 10

Что называется остовным деревом?

• Пустой граф

• Случайный набор вершин графа

• Связный подграф без циклов, содержащий все вершины исходного графа

• Полный граф без вершин

Как формулируется задача о минимальном остове?

• Найти все циклы в графе

• Найти самый длинный путь в графе

• Найти связный подграф без циклов с минимальной суммой весов ребер

• Найти подграф с наименьшим количеством вершин

Какие основные алгоритмы известны?

• Алгоритмы Крускала, Прима, Борувка

• Квадратичный алгоритм

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

• Алгоритмы поиска в глубину и ширину

Область применения алгоритмов построения минимального остова?

• Графический дизайн

• Медицина

• Транспорт

• Телекоммуникации

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

• Краскал - случайный выбор ребер, Прим - случайный выбор вершин

• Краскал - поиск минимального остова, Прим - поиск кратчайшего пути

• Краскал - поиск всех циклов, Прим - поиск всех вершин

• Краскал - поиск кратчайшего пути, Прим - поиск минимального остова

Сколько вершин в графе в программе из задания 1?

• 3

• 6

• 4

• 5

Сколько вершин в графе в программе из задания 2?

• 3

• 4

• 5

• 6

Какой алгоритм используется в программе из задания 1?

• Алгоритм Дейкстры

• Алгоритм Борувка

• Алгоритм Прима

• Алгоритм Крускала

Какой алгоритм используется в программе из задания 2?

• Алгоритм Борувка

• Алгоритм Дейкстры

• Алгоритм Прима

• Алгоритм Крускала