3.05.5. Задача о минимальном остове

Задача формулируется следующим образом: во взвешенном связном графе требуется найти остов минимального веса.

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

Существуют достаточно простые алгоритмы решения этой задачи.

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

1 шаг. Строим остовной подграф , где — пустой граф порядка , а — ребро графа минимального веса.

Далее, для .

2 шаг. Строим , где ребро имеет минимальный вес среди ребер, не входящих в и не составляющее циклов с ребрами подграфа .

Легко видеть, что граф является искомым остовом.

Аналогичную структуру имеет и следующий алгоритм.

Алгоритм Прима.

1 шаг. Строим — ребро графа минимального веса.

Далее, для .

2 шаг. Строим , где — ребро минимального веса, не входящее в и инцидентное ровно одной вершине подграфа .

Помимо задачи о минимальном остове рассматривается также задача максимальном остове, которая формулируется и решается аналогично.

< Предыдущая		Следующая >