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

Материал из WikiGrapp
Версия от 13:54, 24 сентября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Алгоритм Краскала''' (''J.B.Kruskal'') - '''1.''' Алгоритм построения каркаса графа пу...)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Алгоритм Краскала (J.B.Kruskal) - 1. Алгоритм построения каркаса графа путем последовательного удаления в соответствии с некоторой упорядоченностью ребер графа без нарушения связности получаемой части графа. 2. Алгоритм построения каркаса наименьшего веса описанным выше методом, но с предварительным упорядочением ребер в порядке неубывания весов.

На основе А.К. созданы многочисленные модификации.

Литература

[Кристофидес],

[Евстигнеев-Касьянов/94]