На этом шаге рассмотрим формальную постановку задачи построения минимального остовного дерева заданного графа.

Взвешенный граф служит математической моделью широкого класса задач на нахождение минимального остовного дерева. Для примера рассмотрим граф с четырьмя вершинами, которые пронумерованы от 1 до 4 (рис. 1).

Рис.1. Полный граф

Пусть веса C[i, j] всех ребер графа равны 1.

Примерами минимального остовного дерева для данного графа могут быть его подграфы, показанные на рис. 2:

Рис.2. Минимальные остовные деревья

Если же веса ребер исходного графа не равны единицам, а заданы следующим образом:

то соответствующие остовные графы примут вид, показанный на рис. 3 (изменились веса некоторых входящих в остовные графы ребер):

Рис.3. Примеры остовных деревьев с весами

Теперь суммы весов, приведенных выше четырех деревьев, будут 3, 7, 7, 7 соответственно, и минимальное остовное дерево будет единственным (рис. 4):

Рис.4. Минимальное остовное дерево

Заметим также, что в остовном дереве для графа из N вершин всегда содержится N-l соединяющих их ребер.

Формально минимальное остовное дерево определяется следующим образом: пусть имеется связный неориентированный граф G=(V, E), где V — множество его вершин, а Е — множество его ребер. И пусть для каждого ребра графа (u, v) (соединяющего вершины u и v) задан его неотрицательный вес P(u, v). Задача нахождения минимального остовного дерева заключается в нахождении такого подмножества T ребер исходного графа, которое связывает все вершины графа G и — для которого суммарный вес всех ребер минимален.

На следующем шаге рассмотрим формулировку олимпиадной задачи.

Предыдущий шаг Содержание Следующий шаг