Представить заданный ориентированный граф матрицей смежности. Определить компоненты связности этого графа, а для каждого из таких компонентов – диаметр, радиус, центр и минимальный цикл Эйлера. Изобразить этот граф, выделив его компоненты связности и циклы Эйлера.
n = 8; p(1,2) = 1, p(1,7) = 2, p(3,2) = 4, p(3,5) = 2, p(4,1) = 1, p(4,3) = 4, p(5,6) = 3, p(6,4) = 2, p(6,7) = 4, p(7,8) = 2, p(8,1) = 3
Решение:
Составим матрицу смежности:
1 2 3 4 5 6 7 8
1 0 1 0 0 0 0 1 0
2 0 0 0 0 0 0 0 0
3 0 1 0 0 1 0 0 0
4 1 0 1 0 0 0 0 0
5 0 0 0 0 0 1 0 0
6 0 0 0 1 0 0 1 0
7 0 0 0 0 0 0 0 1
8 1 0 0 0 0 0 0 0
Найдем матрицу достижимости вершин орграфа:
1 2 3 4 5 6 7 8
1 1 1 0 0 0 0 1 1
2 0 0 0 0 0 0 0 0
3 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1
6 1 1 1 1 1 1 1 1
7 1 1 0 0 0 0 1 1
8 1 1 0 0 0 0 1 1
Построим матрицу контрдостижимости, транспонируя предыдущую:
1 2 3 4 5 6 7 8
1 1 0 1 1 1 1 1 1
2 1 0 1 1 1 1 1 1
3 0 0 1 1 1 1 0 0
4 0 0 1 1 1 1 0 0
5 0 0 1 1 1 1 0 0
6 0 0 1 1 1 1 0 0
7 1 0 1 1 1 1 1 1
8 1 0 1 1 1 1 1 1
Отсюда получаем матрицу сильных компонент связности орграфа:
1 2 3 4 5 6 7 8
1 1 0 0 0 0 0 1 1
2 0 0 0 0 0 0 0 0
3 0 0 1 1 1 1 0 0
4 0 0 1 1 1 1 0 0
5 0 0 1 1 1 1 0 0
6 0 0 1 1 1 1 0 0
7 1 0 0 0 0 0 1 1
8 1 0 0 0 0 0 1 1
Таким образом, данный орграф содержит сильные компоненты связности G1 = (1,7,8) и G2 = (3, 4, 5, 6).
Исходный граф выглядит так:
Первая компонента связности:
Видно, что подграф представляет собой эйлеров цикл, так как его дуги образуют путь, проходящий через каждое ребро графа ровно по одному разу. Расстояние от любой вершины до наиболее удаленной равно 2. Следовательно диаметр и радиус равны 2, а центром являются все вершины.
Вторая компонента связности:
Подграф также представляет собой эйлеров цикл. Расстояние от любой вершины до наиболее удаленной равно 3. Следовательно диаметр и радиус равны 3, а центром являются все вершины.
