Алгоритм Краскала — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''Алгоритм Краскала''' (''J.B.Kruskal'') - '''1.''' Алгоритм построения каркаса графа пу...)
 
Строка 1: Строка 1:
'''Алгоритм Краскала''' (''J.B.Kruskal'') -  
+
'''Алгоритм Краскала''' ([[J.B.Kruskal|''J.B.Kruskal'']]) -  
'''1.''' Алгоритм построения каркаса графа путем
+
'''1.''' [[Алгоритм|Алгоритм]] построения [[каркас|каркаса]] [[граф|графа]] путем
 
последовательного удаления в соответствии с некоторой
 
последовательного удаления в соответствии с некоторой
упорядоченностью ребер графа без нарушения связности
+
упорядоченностью [[ребро|ребер]] графа без нарушения связности
 
получаемой части графа. '''2.''' Алгоритм построения каркаса
 
получаемой части графа. '''2.''' Алгоритм построения каркаса
 
наименьшего веса описанным выше методом, но с предварительным
 
наименьшего веса описанным выше методом, но с предварительным

Версия 15:09, 24 сентября 2009

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

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

Литература

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

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