Исследуйте структуру графов и их применение в различных областях с помощью этого теста. Узнайте больше о вершинах, рёбрах, путях и циклах, а также о важных алгоритмах и свойствах графов. Проверьте свои знания и улучшите понимание теории графов.
1. Что такое вершина в графе?
a) Линия, соединяющая две точки
b) Точка, где сходятся линии
+c) Точка или узел в графе
2. Что такое ребро в графе?
a) Точка или узел
+b) Линия, соединяющая две вершины
c) Цикл в графе
3. Какой алгоритм используется для поиска кратчайшего пути в графе?
a) Алгоритм Дейкстры
b) Алгоритм Флойда-Уоршелла
+c) Оба вышеперечисленных
4. Что такое цикл в графе?
a) Путь, проходящий через все вершины
b) Путь, который начинается и заканчивается в одной вершине
+c) Путь, который начинается и заканчивается в одной вершине и не проходит через одну вершину дважды
5. Какой граф называется ориентированным?
a) Граф с направленными рёбрами
+b) Граф, в котором рёбра имеют направление
c) Граф без направленных рёбер
6. Что такое степень вершины в графе?
a) Количество рёбер, исходящих из вершины
b) Количество вершин, соединённых с данной вершиной
+c) Количество рёбер, инцидентных данной вершине
7. Какой алгоритм используется для поиска минимального остовного дерева?
a) Алгоритм Прима
b) Алгоритм Краскала
+c) Оба вышеперечисленных
8. Что такое связный граф?
a) Граф, в котором есть циклы
b) Граф, в котором есть рёбра
+c) Граф, в котором между любыми двумя вершинами существует путь
9. Что такое планарный граф?
a) Граф, который можно нарисовать на плоскости без пересечения рёбер
+b) Граф, который можно нарисовать на плоскости без пересечения рёбер
c) Граф, в котором все вершины имеют равную степень
10. Что такое эйлеров цикл?
a) Путь, проходящий через все вершины графа
b) Путь, который начинается и заканчивается в одной вершине
+c) Замкнутый путь, проходящий через каждое ребро графа ровно один раз
11. Какой граф называется полным?
a) Граф, в котором все вершины соединены рёбрами
+b) Граф, в котором каждая пара вершин соединена ребром
c) Граф, в котором нет циклов
12. Что такое изоморфизм графов?
a) Графы имеют одинаковое количество вершин
b) Графы имеют одинаковое количество рёбер
+c) Графы имеют одинаковую структуру и могут быть преобразованы друг в друга
13. Что такое двудольный граф?
a) Граф, в котором все вершины имеют равную степень
b) Граф, в котором есть циклы
+c) Граф, вершины которого можно разделить на два множества так, что каждое ребро соединяет вершины из разных множеств
14. Что такое гамильтонов цикл?
a) Путь, проходящий через все вершины графа
+b) Замкнутый путь, проходящий через каждую вершину графа ровно один раз
c) Путь, который начинается и заканчивается в одной вершине
15. Какой алгоритм используется для поиска всех путей в графе?
a) Алгоритм Дейкстры
b) Алгоритм Флойда-Уоршелла
+c) Алгоритм поиска в глубину (DFS)