Для графа G, заданного матрицей весов: x1 x2 x3 x4 x5 x6 x7 x1 - 5 11 14 ∞ ∞ 8 x2 5 - 5 7 ∞ ∞ 8 x3 11 5 - 4 8 6 ∞ x4 14 7 4 - 7 ∞ 11 x5 ∞ ∞ 8 7 - 3 5 x6 ∞ ∞ 6 ∞ 3 - 6 x7 8 8 ∞ 11 5 6 - Построить минимальный по весу остов G' и найти его вес ω(G').

24 октября 2025
Высшая математика

Условие:

x1 x2 x3 x4 x5 x6 x7
x1 - 5 11 14 ∞ ∞ 8
x2 5 - 5 7 ∞ ∞ 8
x3 11 5 - 4 8 6 ∞
x4 14 7 4 - 7 ∞ 11
x5 ∞ ∞ 8 7 - 3 5
x6 ∞ ∞ 6 ∞ 3 - 6
x7 8 8 ∞ 11 5 6 -
Для графа G , заданного матрицей весов, построить минимальный по весу остов G' и найти его вес ω(G').

Решение:

Найдем минимальное по весу остовное дерево (МСТ) для графа G. Для этого воспользуемся алгоритмом Краскала, который состоит из следующих шагов: 1. Выпишем все ребра графа с их весами (учтем, что матрица симметричная, и ребра неориентированные): • Ребро (x1, x2) имеет вес 5 • Ребро (x1, x3) имеет вес 11 • Ребро (x1, x4) имеет вес 14 • Ребро (x1, x7) имеет вес 8 • Ребро (x2, x3) имеет вес 5 • Ребро (x2, x4) имеет вес 7 • Ребро (x2, x7) имеет вес 8 • Ребро (x3, x4) имеет вес 4 • Ребро (x3, x5) имеет вес 8 • Ребро (x3, x6) имеет вес 6 • Ребро (x4, x5) имеет вес 7...