Исправления
Задача 1.
В графе 7 вершин и 9 ребер, следовательно, матрица инцидентности графа - матрица B(7(9):
Контрольная работа 3
Представьте графы и различными способами (по четыре для каждого графа).
Пронумеруем произвольно вершины и ребра графа
В графе 5 вершин, следовательно, матрица смежности графа - матрица A(5(5):
В графе 5вершин и 6 ребер, следовательно, матрица инцидентности графа - матрица B(5(6):
Составим структуру смежности графа G0:
Вершине 1 смежны вершины 2,3- 1: 2,3;
Вершине 2 смежны вершины 1,3- 2: 1,3;
Вершине 3 смежны вершины 1,2- 3: 1,2;
Вершине 4 смежна вершина 4 – 4: 4;
Вершине 5 смежна вершина 5 – 5: 5.
Список ребер графа G0: NR0=(1,1,2,3,4,5).
KR0=(2,3,3,2,4,5).
Пронумеруем произвольно вершины и ребра графа
В графе 7 вершин, следовательно, матрица смежности графа - матрица A(7(7):
В графе 7 вершин и 9 ребер, следовательно, матрица инцидентности графа - матрица B(7(9):
Составим структуру смежности графа G1:
Вершине 1 смежны вершины 2,4- 1: 2,4;
Вершине 2 смежны вершины 1,3,5- 2: 1,3,5;
Вершине 3 смежны вершины 2,4,5- 3: 2,4,5;
Вершине 4 смежны вершины 1,3- 4: 1,3;
Вершине 5 смежны вершины 2,3,6,7- 5: 2,3,6,7;
Вершине 6 смежны вершины 5,7- 6: 5,7;
Вершине 7 смежны вершины 5,6- 7: 5,65.
Список ребер графа G1: NR1=(1,2,1,4,2,3,2,5,4,3,3,5,5,7,5,6,7,6).
KR1=(2,1,4,1,3,2,5,2,3,4,5,3,7,5,6,5,6,7).
Запишите алгоритм и составьте программу нахождения диаметра и радиуса графа по матрице минимальных расстояний.
Матрицей минимальных расстояний D(n(n) графа G(X,V) называется матрица, элементы которой определяются по правилу:
di,j=
Для графа G=(X,V) будем называть диаметром графа G величину (максимальное из всех минимальных расстояний).
Пусть x – произвольная вершина из X. Величина будет называться максимальным удалением (эксцентриситетом) в графе G от вершины x (максимальное из всех минимальных расстояний для вершины x).
Радиусом графа G называется величина (минимальный из эксцентриситетов всех вершин).
Таким образом, задача нахождения радиуса и диаметра сводится к нахождению минимального и максимального эк