Построение минимального остовного дерева для заданного графа

Условие:

Для заданного на рисунке графа построить минимальное остовное дерево.

Решение:

Предмет: Дискретная математика Раздел: Теория графов Задание: Построение минимального остовного дерева для заданного графа. Минимальное остовное дерево можно построить с использованием алгоритма Краскала или Прима. Рассмотрим алгоритм Краскала для данного графа. **Алгоритм Краскала:** 1. Отсортируем все рёбра графа по возрастанию их весов. 2. Начнём с пустого остовного дерева. 3. Последовательно добавляем рёбра, начиная с самых маленьких, при условии, что они не создают цикл в уже построенном дереве. 1. Рёбра в порядке возрастания их весов: (X6X7, 2), (X4X6, 3), (X3X4, 3), (X3X5, 3), (X2X4, 4), (X5X6, 5), (X2X3, 6), (X4X5, 6), (X4X7, 6), (X1X2, 7), (X1X5, 8), (X1X6, 10), (X2X7, 10), (X2X6, 11), (X1X7, 15). 2. Строим минимальное остовное дерево, добавляя рёбра по возрастанию весов: - (X6X7, 2) - (X4X6, 3) - (X3X4, 3) - (X3X5, 3) - (X2X4, 4) - (X5X6, 5) - (X1X5, 8) Таким образом, минимальное остовное дерево состоит из ребер: \[ X6X7, X4X6, X3X4, X3X5, X2X4, X5X6, X1X5 \] Теперь проверим предложенные варианты ответов и выберем соответствующий: - Первый вариант: X1X5, X5X8, X5X6, X4X6, X3X4, X2X4, X4X7 - Второй вариант: X1X5, X3X5, X5X6, X4X6, X3X4, X2X4, X4X7 - Третий вариант: X1X5, X3X5, X5X6, X4X6, X3X4, X2X4, X2X7, X6X7 - Четвертый вариант: X1X5, X3X5, X5X6, X4X6, X3X4, X3X5, X3X6, X4X7 Подходящий вариант ответа: Второй: \( X1X5, X3X5, X5X6, X4X6, X3X4, X2X4, X4X7 \) Итак, правильный ответ: второй вариант.