Построить граф. Отметить его характеристики (связность, циклы, полнота). Построить матрицу смежности. Указать все степени вершины графа. Построить граф дополнения. Указать его характеристики. Степени вершин. Построить матрицы достижимости и расстояний.

Добавлена: 28.04.2026
Обновлена: 28.04.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория графов

Построить граф. Отметить его характеристики (связность, циклы, полнота). Построить матрицу смежности. Указать все степени вершины графа. Построить граф дополнения. Указать его характеристики. Степени вершин. Построить матрицы достижимости и расстояний.

Условие:

\begin{array}{l}V=\{1;2;3;4;5;6\}\ E=\{(1;2);(1;3);(1;5);(2;5);\ (3;5);(3;4);(4;5);(5;6)\}\end{array}

Построить граф. Отметить его характеристики (связность, циклы, полнота). Построить матрицу смежности. Указать все степени вершины графа. Построить граф дополнения. Указать его характеристики. Степени вершин. Построить матрицы достижимости и расстояний. Указать все эксцентриситеты, радиус, диаметр, центр графа. Построить диаметральный путь. (2 дерева) Построить дерево из центральной вершины с наименьшим номером. (использовать алгоритм поиска в ширину)

Решение:

Построение графа и его характеристик

Заданы вершины и ребра:
В = {1, 2, 3, 4, 5, 6}
E = {(1,2), (1,3), (1,5), (2,5), (3,5), (3,4), (4,5), (5,6)}

Из этого получаем следующие связи:
— Вершина 1 соединена с 2, 3 и
5.
— Вершина 2 соединена с 1 и
5.
— Вершина 3 соединена с 1, 5 и
4.
— Вершина 4 соединена с 3 и
5.
— Вершина 5 соединена с 1, 2, 3, 4 и
6.
— Вершина 6 соединена с
5.

Проверка связности:
Рассмотрим все вершины – через 5 (а также через 1...