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

Предмет: Дискретная математика

Раздел: Теория графов

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

Минимальное остовное дерево можно построить с использованием алгоритма Краскала или Прима. Рассмотрим алгоритм Краскала для данного графа.

Алгоритм Краскала:

1. Отсортируем все рёбра графа по возрастанию их весов.
2. Начнём с пустого остовного дерева.
3. Последовательно добавляем рёбра, начиная с самых маленьких, при условии, что они не создают цикл в уже построенном дереве.

Рёбра в порядке возрастания их весов:

• (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)

Строим минимальное остовное дерево, добавляя рёбра по возрастанию весов:

• (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 \)

Итак, правильный ответ: второй вариант.