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