2. На представленном графе найдите: а) минимальный остов дерева, б) найдите кратчайший путь от начальной точки Х1 до всех остальных точек.

Решение:

а) Минимальный остов дерева — это подграф данного графа, который является деревом, соединяет все вершины графа и имеет минимальную сумму весов ребер.

Для графа, представленного на изображении, можно построить минимальный остов дерева, используя алгоритм Прима или Краскала. В данном случае выберем ребра с наименьшим весом, избегая циклов:

1. Ребро X1-X2 (вес 7)
2. Ребро X1-X7 (вес 17)
3. Ребро X3-X7 (вес 19)
4. Ребро X3-X4 (вес 13)
5. Ребро X3-X5 (вес 23)
6. Ребро X7-X6 (вес 3)

Суммарный вес минимального остова дерева: 7 + 17 + 19 + 13 + 23 + 3 = 82

б) Кратчайшие пути от начальной точки X1 до всех остальных точек можно найти с помощью алгоритма Дейкстры.

1. X1 -> X1: 0
2. X1 -> X2: 7
3. X1 -> X7: 17
4. X1 -> X3: X1-> X7 -> X3: 17 + 19 = 36
5. X1 -> X6: X1 -> X7 -> X6: 17 + 3 = 20
6. X1 -> X4: X1 -> X7 -> X3 -> X4: 17 + 19 + 13 = 49
7. X1 -> X5: X1 -> X7 -> X3 -> X5: 17 + 19 + 23 = 59

Ответ: а) 82, б) X1-X1: 0; X1-X2: 7; X1-X7: 17; X1-X3: 36; X1-X6: 20; X1-X4: 49; X1-X5: 59